查询语句QL的语义分析和实现计算机与信息科学系
论文摘要：本文是基于数据库、编译原理、数据结构、程序设计等理论知识，主要是运用语法制导翻译原理，对数据定义语言中的查询语句进行语义分析与实现。语义分析是在自主知识产权数据库第四层上，为上层提供函数接口。本文实现对查询语句在进行语法分析的同时，进行语义分析，包括类型检查，执行语义子动作等。语义检查无误后，经分析可以得到表名和相应的列名，用栈来实现布尔表达式的求值等，布尔表达式的计算结果，用以检查条件是否成立，为事务处理提供函数接口，以便进行正确的查询。本文实现的是对简单QL语句的语义的分析，其中文中的部分算法是通用的。如果扩充QL语句的文法定义，并且在语法分析阶段采用LR分析法，增加相应的产生式，可实现更加复杂的查询语句的语义分析。
关键词：自主知识产权数据库，语法制导翻译，语义分析
Semantic Analysis and Realization of the Search Language QL Weifeng Gao (Dept. of Computer and Information Science, Southwest Forestry College, Kunming, Yunan, 650224, China)
Abstract: This paper is based on theories knowledge of the database, compiler implementation, data construction and program design. It mainly makes use of the syntax phrasing system with translation principle to realize the semantic analysis of the search language QL. The semantic analysis is the fourth layer in the model of Independence Intelligent Property Right Database. It provides function interface to the upper level. The paper has been realized that syntax analysis proceed at the same time with semantic analysis , including the type-checking, carrying out semantic actions. Language righteousness checked without any error, we can get table name and the corresponding fields names. The paper adopts the stack to realize calculating the logic expressions type. Through the value of the logic expressions, we can check whether conditions in the QL establish or not. And we pass the result to the tranction disposal layer which can deal with the right search. This paper realized the semantic analysis of the simple QL .Parts of algorithm which this paper designed is in general use. If we expand the definition of grammars to QL ,add the produce expressions and adopt the LR syntax analysis, it can realize the semantic analysis of the complex QL.
Key words: Independence Intelligent Property Right Database, Syntax Phrasing System with Translation Principle, Semantic Analysis
目 录1 前言 12 概述 32.3 研究的意义 42.4 国内外研究现状及发展趋势 42.5 研究的内容 63 语义分析的理论依据 73.1 数据库设计背景 73.2 SQL 83.3 编译程序及语义分析 103.4 程序设计知识背景 134 系统设计 154.1 概要设计 154.2 功能设计 154.3 接口设计 165 实现 185.1 实现环境 185.2 分析出表名和列名的设计与实现 185.3 表达式计算的设计与实现 205.4 单表和多表查询的设计 216 总结与展望 236.1 总结 236.2 展望 23参考文献 25指导教师简介 26致 谢 27附 录 442
查询语句QL的语义分析和实现1 前言伴随着网络的日益发展，每天需要处理的数据更是呈指数级别增长，建立高效良好的数据库管理系统的重要性已被提上日程。数据库管理系统是一个能有效建立和管理大量数据的强大工具，并且能安全长期地保存这些数据以供使用。数据库管理系统无处不在，尤其被应用于维护商业内部记录，在网络上为顾客存储和查询数据提供方便服务，以及支持很多其他商业处理。自主知识产权数据库是以市场上常见的数据库管理系统为基础，功能相似的数据库系统。由于数据库软件的开发需要巨大的资金和研发力量的投入，再加上国内的技术和制度等有待完善，自己开发数据库系统软件的难度较大，因此长期以来，国内市场的绝大部分市场份额一直由Oracle、SQL Server、DB2、SYBASE等国外产品所占据。但无论是从国家信息安全，还是从国家软件产业发展的角度考虑，数据库软件的国产化都有其十分重要的意义。所以开发自主知识产权库对自己和对国家都有好处，对自己可以提高开发大型软件的能力，综合运用所学知识，充分了解和掌握先进技术，培养团队精神；如果开发成功，对国家将是一个巨大的贡献。自主知识产权数据库的框架共七层，涉及编译原理、数据库、程序设计等多方面的知识，语法分析和语义分析在第四层。能够进行正确的语义分析，合理而且高效的语法制导翻译，从而进行语义检查，是为上层SQL语句提供函数式接口的关键。因此本文研究数据查询语句的语义分析具有十分的必要性和重要的意义。本文是基于自主知识产权数据库数据定义语言的词法分析、语法定义规则、语法分析的工作原理，在充分运用编译原理中的语义分析，语法制导翻译的理论知识，综合运用数据结构的基础上，定义优先关系表，确定运算符之间的优先关系，用栈的形式实现对条件表达式的计算；设计各模块接口参数的约定形式，并以Visual C++6.0为开发平台，对自主知识产权数据库中的查询语句的语义分析进行设计与实现。主要完成了以下工作：首先根据QL文法定义，采用语法制导翻译方法，在语法分析的同时进行语义分析，侦查和报告QL语句中的语义错误等，包括类型匹配，边界溢出检查等。其次，在语义检查同时，执行语义子动作。在算法上主要是实行语法制导的翻译，本文主要实现对条件表达式的翻译以及计算。将条件表达式翻译成易于计算的形式，如：{0}='d' && {3}<=5 && (!{5}=9)，在{i}中，i为数据库中表的列名的索引值。并利用表达式的计算结果来检查查询条件是否成立，为事务处理模块提供函数接口，以便进行正确的查询。再者，若进行语法分析的同时，语义检查正确时，筛选出查询所需的元素（表名和相应的列名）；并基于本文所设计的接口参数传递方式，将查询条件的翻译结果和分析出来的表名和相应的列名传递给事务处理模块。若语义检查错误时，给予提示，并将错误信息传递给上一层。本文完成了SQL语言中的简单查询语句QL的语义分析。在此基础上，若扩充QL语句的文法定义，增加相应的产生式，可实现更加复杂的查询。其中可采用LR分析法，这样文法限制少，错误定位准确，效率较高，易于自动生成。
查询语句QL的语义分析和实现2 概述2.1 研究背景数据库技术从诞生到现在，在不到半个世纪的时间里，形成了坚实的理论基础、成熟的商业产品和广泛的应用领域，吸引越来越多的研究者加入。数据库的诞生和发展给计算机信息管理带来了一场巨大的革命。三十多年来，国内外已经开发建设了成千上万个数据库，它已成为企业、部门乃至个人日常工作、生产和生活的基础设施。二十世纪九十年代，随着基于PC的客户/服务器计算模式和企业软件包的广泛采用，数据管理的变革基本完成。数据管理不再仅仅是存储和管理数据，而转变成用户所需要的各种数据管理的方式。Internet的异军突起以及XML语言的出现，给数据库系统的发展开辟了一片新的天地，而自主知识产权数据库随之诞生。数据库管理系统（Database Manage System，简称DBMS）DBMS所提供的语言用于对数据库进行操作，称为数据库语言（Database Language）。如今广泛使用是结构化查询语言（Structured Query Language，简称SQL），评价一个DBMS成功的一个关键就是它支持SQL的程度，而一个高效安全的SQL编译器又是优秀数据库的核心和基础之一。因此在自主知识产权数据库的设计中引入了语义分析。2.2 研究的目的数据的查询语言（Query Language，简称QL）是SQL的一个组成部分，它用于对数据进行查询。本文根据自主知识产权数据库设计的总体框架，把词法分析产生的单词序列分解成各类语法短语，通过对数据查询语言的语义分析，进行语法制导翻译，从而实现语义检查，为上层提供SQL语句的函数式接口。编译程序它读入用某种语言（源语言）编写的程序并将其翻译成与之等价的用另一种语言（目标语言）编写的一个程序。作为这个翻译过程的一个重要组成部分，编译器能够向用户报告被编译的源程序中出现的错误。语义分析则是编译的第三个阶段，它的主要任务是审查源程序有无语义错误，进行语法制导翻译，为代码生成阶段收集类型信息。语义法分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作符和操作数，它的一个重要组成部分是类型检查。类型检查负责检验每个操作数是否满足源语言的说明。2.3 研究的意义集团用户信息化建设的巨额投资中会有相当一部分是用以建设供自己内部使用的数据库，这被称为是In-House系统。自用数据库是非常重要的，特别是那些与自己业务密切相关的工作数据库。这些数据库建设是一个很繁重的过程，需要的技术也会越来越高，有很多数据库建设不仅需要外部的专家，还需要外部的数据库支持。由于很多机构很难有足够的人才来胜任这件事，筹钱容易，筹备人力和技术难，所以数据库的外包业必将红火起来，特别是在信息化建设发展到一定程度之后，大量的机构内部网出现，必然会带来大量数据库外包的需求。所以自主知识产权数据库的研究具有十分重要的意义，如果自主知识产权数据库研究成功，将带来巨大的经济效益和社会效益。语义分析本题目来源于自主知识产权数据库项目中的一个模块。通过进行自主知识产权数据库之查询语句QL的语义分析与实现，在掌握了编译原理基本理论的基础上，学习编译器的设计思想，加深对编译原理的理解,使数据库及编程方面的知识得以应用，针对编译过程中的重点和难点进行编程实践；独立完成一定工作量的程序设计，用以检验大学四年专业知识的学习情况。2.4 国内外研究现状及发展趋势一个国家数据库产业的发展状况，在很大程度反映了该国信息技术和信息产业的发展水平。在Internet出现以前，数据库产业可以说是发展最快的信息产业，而Internet的发展又给数据库产业注入了新的活力，使传统的数据库产业向着Internet服务的方向发展。在当今世界上，处在数据库产业前列的是以美、欧、日为代表的发达国家。传统数据库系统按数据模型的分类见图 2 1图 2 1 传统数据库系统按数据模型的分类关系型数据库是当今数据库发展的主流，它提供了关系操作的特点和功能要求。其操作是高度非过程化的，用户不需要指出特殊的存取路径，路径的选择由DBMS的优化机制来完成。而网络数据库作为一种主要的电子资源，其独特的优势在网络环境下日益突显。随着计算机、通信网络与信息技术的不断发展，未来几年网络数据库将继续呈现出良好的发展势头，如目前的XML数据库等，将成为图书馆发展电子馆藏、开展电子信息服务的重要资源与基础。我国的数据库研发经过“八五”和“九五”期间的努力，已经形成了具有一定规模的研究和开发力量。但在支持互联网应用、海量数据管理、安全性支持、系统可扩展性等方面仍显薄弱。在促进数据库的发展和掌握核心技术方面，我国从上世纪80年代以来已进行了深入的理论研究和实际系统的研制，现已有多个产品及原型系统。国家863计划重点支持的东软集团有限公司研制的数据库管理系统OpenBASE、武汉华工达梦数据库有限公司的DM数据库、北京人大金仓信息技术有限公司研制的通用数据库管理系统KingbaseES和北京神舟航天软件公司研制的OSCAR对象关系型数据库等都是国产数据库的代表。与此同时，作为语义分析母体的编译程序自20世纪50年代早期诞生起也经历了一个发展过程：50年代中期，FORTRAN高级语言的编译系统开发成功；50年代末期，编译程序的自动生成工具产生；60年代，利用自展技术来构造编译程序。随着并行技术和并行语言的发展，处理并行语言的并行编译技术，将串行程序转换成并行程序的自动并行编译技术也正在深入研究之中。另外嵌入式应用迅速增长的需求，推动了交叉编译技术的发展.还有系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。第一个编译器出现在20世纪50年代早期，FORTRAN等一批高级语言极大优化了代码生成，并遥遥领先于它所处的时代。时至今日，新语言的数量不断翻番，人们开始需要专业的编译程序，同时程序设计方法中新的类型也在发展，重点越来越多地从“如何编译”向“编译成什么”转移。与此同时，数据库管理系统亦经历了30多年的发展演变，发展成了一门内容丰富的学科，形成了总量达数百亿美元的一个软件产业。关系型数据库依然是当今主流，但随着新技术的不断开发与互联网的飞速发展，Web型、嵌入型、数据仓库、联机分析等崭新数据库技术全面开花。评价一个数据库成功的关键之一就是它支持SQL的程度，而一个高效安全的SQL编译器则是优秀数据库的核心和基础。国内在编译这方面起步较晚，至今没有出过一款执行效率高的编译器。2.5 研究的内容本文随后将在第三章介绍数据库设计、数据查询语言、编译原理以及语义分析的相关理论知识；在第四章对QL语义分析的相关设计，包括功能设计，接口方式的设计等；最后在第五章以Visual C++6.0为开发工具，Visual C++为开发语言，完成QL语义分析的程序实现。本文的内容是对QL查询语句的语义分析及实现。QL语句的查询是很复杂的，要对其进行正确的编译，需要做很多的工作。语义分析主要是运用语法制导翻译方法，侦查和报告查询语句中的语义错误等，包括类型匹配，边界溢出检查等。语法制导翻译方法既可以用来产生各种中间代码，也可以用来直接产生机器指令，甚至还可用来对源程序进行解释执行，执行语义子动作。但在整个过程中核心问题是：根据QL文法定义，进行语法分析的同时进行语义分析，实现语义检查，执行语义子动作。在算法上主要是实行语法制导的翻译，尤其是对条件表达式的翻译。
查询语句QL的语义分析和实现3 语义分析的理论依据3.1 数据库设计背景数据库的设计是指对于一个给定的应用环境，构造出最优的数据库模式，建立数据库及其应用系统，有效的存储数据，满足用户的信息要求和处理要求。数据设计中需求分析阶段综合各个用户的应用需求；在概念设计阶段形成独立于机器特点、独立于各个DBMS产品的概念模式，用E—R图来描述。在逻辑设计阶段将E—R图转换成具体的数据库产品支持的数据模型如关系模型，形成数据库的逻辑模式。然后根据用户处理的要求，安全性的考虑，在基本表的基础上再建立必要的视图形成数据的外模式。在物理设计阶段根据DBMS特点和处理的需要，进行物理存储安排，设计索引，形成数据库的内模式。数据库技术已被认为是“计算机和信息科学增长最迅速的领域之一“。它很快发展成为实践上和理论上都相当重要且相当成熟的领域之一，它是计算机软件方面的一个独立分支，目前还在发展之中。数据库系统，从根本上说不过是计算机化的记录保持系统，也就是说，它的总目的是存储和产生所需要的有用信息。数据，是数据库系统中集中存储的一批数据集合——即数据库。它是数据库系统的工作对象。用户，存在一组使用数据库的用户，即指存储、维护、和检索数据的各类请求。数据库系统中主要有三类用户：终端用户、应用程序员和数据库管理员。在文件系统中，用户对其所使用的数据文件的物理组织和存储细节全要进行安排和处理，这给用户带来很大不便。而数据库系统的目标之一就是要解决这个问题。数据库系统把对“存储数据”的管理、维护和使用的复杂性都转嫁给DBMS身上。因此，DBMS是一种非常复杂的、综合性的、在数据库系统中对数据进行管理的大型系统软件，它是数据库系统的核心组成部分，在操作系统（OS）支持下工作。而自主知识产权数据库是综合运用数据库基础知识，编译原理，操作系统原理，程序设计语言等知识设计的，其总体设计框架见图 3 1
图 3 1 自主知识产权数据库总体设计框架3.2 SQL3.2.1 SQL语言概况早在20世纪70年代,IBM公司San Jose 研究中心研制了一个关系DBMS原型系统System R。System R在发展关系数据库技术方面做了一系列重要的、创造性的贡献。其中之一，就是发展了一种非过程关系数据库语言，当时称之为SEQUEL(Structured English Query Language)。1981年，在System R的基础上，IBM公司推出商品化的关系DBMS SQL/IBM的DB2、SQL/400、QMF等DBMS产品中，而且也广泛地用于许多非IBM公司的DBMS产品中，例如ORACLE、Unify、Sybase、dBASE Ⅳ、Ingres、Rdb等。SQL之所以取得成功，除了商业上的原因外，语言本身接近英语自然语言，易学易用，受到用户的欢迎，也是一个很重要的因素(王能斌，2000)。从1982年开始，美国国家标准协会(ANSI)即着手SQL的标准化工作。SQL已从开始时比较简单的数据库语言，逐步发展成为功能比较齐全、内容比较复杂的数据库语言。随着数据库技术的发展和数据库功能的增强，原有的功能要保持兼容，新的功能要增加，这种发展趋势似乎是不可避免的。目前，各个DBMS厂商都自称采用SQL语言，但完全按ISO标准实现的并不多。IBM公司实际上以其DB2的SQL作为IBM的标准。其他厂商所实现的SQL，由于历史的原因，也有不少差异。但总的倾向是向国际标准靠拢，与DB2 SQL保持兼容。SQL语言和基于SQL的关系是计算机工业最重要的基础技术之一。在过去的20年里，SQL己经从最初的商业应用发展成为一种计算机产品，其服务市场部分每年达数百亿美元，SQL成为当今标准的计算机数据库语言。现在，支持SQL的数据库产品数以百计，运行于从大型机到PC机再到便携式计算机的整个计算机系统上。SQL是一种组织、管理和检索计算机数据库存储的数据的工具。SQL是结构化查询语言（Structured Query Language ）缩写。正如它的名称所暗示的，SQL是一种计算机语言，可以用它与数据库交互。事实上，SQL使用的是一个特殊类型的数据库，即关系数据库。3.2.2 SQL的特点(1)综合统一：非关系模型的数据语言分为模式定义语言和数据操纵语言，其缺点是，当要修改模式时，必须停止现有数据库的运行，转储数据，修改模式编译后再重装数据库。SQL是集数据定义、数据操纵和数据控制功能与一体，语言风格统一，可独立完成数据库生命周期的所有活动(陈平等,2004)。(2)高度非过程化：非关系数据模型的数据操纵语言是面向过程的，若要完成某项请求时，必须指定存储路径；而SQL语言是高度非过程化语言，当进行数据操作时，只要指出“做什么”，无须指出“怎么做”，存储路径对用户来说是透明的，提高了数据的独立性(陈平等,2004)。(3)面向集合的操作方式：非关系数据模型采用的是面向记录的操作方式，操作对象是一条记录。而SQL语言采用面向集合的操作方式，其操作对象、查找结果可以是元组的集合(陈平等,2004)。(4)两种使用方式：第一种方式，用户可以在终端键盘上键入SQL命令，对数据库进行操作，故称之为自含式语言；第二种方式，将SQL语言嵌入到高级语言程序中，所以又是嵌入式语言(陈平等,2004)。(5)语言简洁、易学易用：SQL语言功能极强，完成核心功能只用了9个动词，包括如下4类(陈平等,2004)。① 数据查询：SELECT。② 数据定义：CREATE、DROP、ALTER。③ 数据操纵：INSERT、UPDATE、DELETE。④ 数据控制：GRANT、REVORK。3.2.3 SQL数据定义SQL的数据操纵功能包括SELECT（查询）、INSERT(插入)、DELETE（删除）和UPDATE（修改）。其中数据查询是数据库的核心操作，它的语句格式如下：SELECT [ALL|DISTINCT] <目标列表达式> [，<目标列表达式>]FROM <表名或视图名> [，<表名或视图名>] [WHERE <条件表达式>] [GROUP BY <列名1> [HAVING <条件表达式>]] [ORDER BY <列名2> [ASC|DESC]]SQL查询中的子句顺序为：SELECT、FROM、WHERE、GROUP BY、HAVING和ORDER BY。其中SELECT、FROM是必须的，WHERE、GROUP BY、HAVING和ORDER BY是可选的，并且HANING子句只能与GROUP BY搭配起来使用。利用（＋）、（－）、（*）、（/）和集函数可以构造表达式，用于在SELECT子句中查询表中未存储但可以导出的结果。（王能斌，2000）本文的QL语义分析只针对于简单查询：它使用语法制导翻译原理直接进行语义分析，语义检查无误后得到表名和相应的列名，运用逻辑表达式求值对条件进行判断。3.3 编译程序及语义分析3.3.1 什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。比如，汇编程序是一个翻译程序，它把汇编语言程序翻译成机器语言程序。如果源语言是像FORTRAN，PASCALA或C那样的高级语言，目标语言是像汇编语言或机器语言那样的低级语言，则这种翻译程序称作编译程序。如果把把编译程序看成一个“黑盒子”，它所执行的转换工作可以用图 3 2来说明(吕映芝等,1998)。
查询语句QL的语义分析和实现3.3.2 编译过程概述编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，图 3 3给出了一个编译过程的各个阶段，这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。图 3 3中将编译过程划分成了词法分析、语法分析、中间代码生成，代码优化和目标代码生成六个阶段。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理(吕映芝等,1998)。
图 3 3 编译过程3.3.3 语义分析A. 什么是语义分析所谓语义分析，就是确定程序是否有意义的，分析程序的含义，并做出相应的处理。语义分析（Syntax analysis）是编译过程的一个逻辑阶段，在整个编译过程中处于第三阶段，语义分析就是语义信息的翻译与计算，而语义信息的翻译与计算与被翻译过程的最终含义或语义密切相关。使用语法制导翻译进行语义处理，而语法制导翻译方法，直观上说就是为每个产生式配上一个翻译子程序（语义动作或语义子程序），并且在语法分析的同时执行这些子程序，语义动作是给产生式赋予具体意义的手段。B. 为什么要语义分析阶段?– 逻辑结构清楚；利于不同目标机上实现同一种语言；– 利于进行与机器无关的优化,这些内部形式也能用于解释。C. 语义分析任务（1） 审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义，即审查类型并报告错误，包括：类型检查： 运算数类型一致性检查： 名字声明与引用控制流检查： 转移目标名字检查： 作用域（2） 如果静态语义正确，根据语法结构分析其含义，并用某种机器内部表示形式表示出来，或者直接生成目标指令。简单地说，就是分析语法结构含义，表示成中间语言或生成目标指令。D. 类型检查的分类和内容（1） 类型检查可以分为动态和静态两种。动态检查在运行时刻完成。功效很低。但是如果语言允许动态确定类型，动态检查是必须的。静态检查在编译时刻完成。静态检查是高效的。如果一个语言能够保证所有经过静态检查之后，程序没有运行时刻的类型错误，则称为强类型的。（2） 类型检查的内容包括：（a） 表达式的类型检查，主要的工作是检查参与运算的操作数是否可以进行相应操作。（b） 语句的类型检查，要包括：赋值语句类型的相容性，控制表达式的结果类型检查。而在C语言中，赋值类型相容性在表达式部分处理。（c） 函数的类型检查，简化了的函数调用语法为E::=E(E)；类型检查所需要做的工作是：检查参数是否符合条件，并且确定函数结果的类型。E::= E1(E2) {E.type = if E2.type=s and E1.type=s®t then t else type_error}当函数有多个参数的时候，需要检查多个参数的类型。实际的翻译方案还需要考虑类型的相容性问题。3.4 程序设计知识背景程序设计方法经历了过程化程序设计（procedural programming）、结构化程序设计(structured programming)、面向对象程序设计（object-oriented programming）几个阶段。过程化程序设计是在一个数据集合上进行的一系列操作；而结构化程序设计方法提供了系统的组织这些过程和能够处理大量数据的有效手段。面向对象程序设计语言的特征表现在：（1） 封装和数据隐藏C++通过增加一种新的数据类型“类”定义对象来支持封装和数据隐藏。类作为一种类型，描述了众多对象共同的特性（ 由数据和行为组成）。类作为一个封装实体，可以完整使用，其内部的成员可以被隐藏起来。（2） 继承与重用C++通过继承来支持重用并产生新的子类，称为派生类。（3） 多态性多态性是另一个与类层次有关的重要概念，即公共消息可以发送给父类对象和所有的子类对象。多态性允许每个子对象以适合自己的形式来响应消息，来支持“不同类型有各自的响应”的思想，以达到提高已有代码的可扩允性的目的。Visual C++6.0概述：Windows应用程序开发系统Visual C++6.0是Visual Studio98(Visual Studio 6.0)家族的成员之一，起源于Microsoft C/C++，是当前Windows 应用开发系统中与Windows平台本身最具有亲缘关系的开发平台。Visual C++主要的特点是支持可视化编程和支持面向对象的编程技术，它提供了大量的可视化编程的工具，如App Wizard和Calls Wizard等。此外可使用Actives技术，支持Internet编程，支持ODBC数据编程等。基于以上特点，所以我选择Visual C++6.0 作为开发的工具。
查询语句QL的语义分析和实现4 系统设计4.1 概要设计语义分析的主要任务是，根据语法结构检查是否有语义错误，分析其含义，并用某种机器内部表示形式表示出来，或者直接生成目标指令。简单地说，就是分析语法结构含义，表示成中间语言或生成目标指令，然后使用汇编语言等，语义处理例如：变量的存储分配；表达式的求值；语句的翻译（中间代码的生成）常见的中间语言表示形式有逆波兰式、三元式、四元式和树形。本文的语义分析是在综合编译原理、程序设计，结合自主知识产权数据库等有关知识的基础上，直接使用语法制导翻译来处理的。在进行语法分析的同时，进行语义分析，包括进行语义检查和语义处理，其中语义检查主要有类型匹配，边界是否溢出，运算、维数等，语义检查无误后，忽略显示中间语言或代码的形式，直接执行语义子动作，为上层SQL语句提供函数式接口，最主要的是对条件的翻译，对逻辑表达式的计算。4.2 功能设计根据概要设计，要实现的功能如图 4 1具体实现的功能如下：（1） 在语法分析正确接受后，进行源程序进行语义检查，包括类型、运算、维数、越界等，如果有类型不匹配等错误，给出提示；如果语义正确，进行语法制导翻译，执行语义子动作。（2） 对查询语句进行语义分析时，能正确分析出表名和列名，为正确的查询提供条件。（3） 对条件翻译时，尤其要合理正确的解决逻辑表达式的计算问题，其中逻辑表达式只有字段名、常数（数字、字符串等）、运算符构成；实现Condition(x)函数，对记录x来说，计算出函数值是0或1。（4） 对同一个表能对不同的条件进行正确的翻译，实现不同的表不同条件的正确翻译。（5） 在翻译的过程中，实现对条件的优化，如条件中含有关键字，就能实现优化。（6） 实现对单表和多表的查询。 图 4 1 语义分析流程图4.3 接口设计4.3.1 用户接口用户要输入需要查询的语句，如果符合定义的语法结构，语义分析正确，将给出正确的查询结果。4.3.2 内部接口内部接口参数形式约定如图 4 2根据图 4 2接口参数具体为：（1）第五层向第四层传递词法分析表；（2）第三层向第四层传递数据库表列名的索引值（用一维数组表示）；（3）语义检查无误后，分析出表名和相应的列名，并对条件判断是真或假，为第三层提供函数接口。 图 4 2 接口参数图4.3.3 外部接口本系统同外界的所有接口的安排包括软件与硬件之间的接口：windows2000以上及相应的设备，本系统与各种支持的软件之间的接口关系：必须可以支持Visual C++6.0的运行。 5 实现5.1 实现环境程序的开发环境是Visual C++6.0，它不仅是一个重要C++编译器，它还提供了一套综合的开发工具和良好的可视化编程环境。在这个环境下，用户可以简便快捷地对C和C++应用程序进行各种操作，例如建立、打开、保存、编辑、编译、链结、和调试等。C++语言的特征体现在C++程序设计语言在C语言的“增强”方面：C语言的扩充，面向对象的机制—封装和数据隐藏、继承与重用、多态。它提供指针的应用。实现环境如图 5 1所示: 图 5 1 程序实现环境5.2 分析出表名和列名的设计与实现定义一个表结构，包括：表的名称，该表所有相关的列名，及列数。其中表结构：Struct Tables{char *TabName; //表名，char *ColNames[MAX]; //该表所有相关的列名，int iColCount; //列数 };分析后与词法分析表中的单词比较，如果语义检查无误，将得到所要结果，如图 5 2。图 5 2 表名、列名结果图语义检查错误，不合定义的语法的如：select table.name,table.agefrom table where age>=34 and table.sex= 结果见图 5 3： 图 5 3 语义检查错误，不合语法的结果图
查询语句QL的语义分析和实现5.3 表达式计算的设计与实现5.3.1 表示布尔表达式的方法程序设计语言中的布尔表达式有两个作用。一是计算逻辑值，二是用做改变控制流语句中的条件表达式。计算布尔表达式的值有两种办法， 第一种办法，如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。例如，用数1表示true，用0表示false。那么布尔表达式1 or(not 0 and 0)or 0的计算过程是：1 or(not 0 and 0)or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=1另一种计算方法是采取某种优化措施，只计算部分表达式，用控制流，即用程序中的位置来表示布尔表达式的值，用这种方式实现控制流语句的布尔表达式尤其方便。5.3.2 布尔表达式求值算法在进行语义分析，对Where 后面的条件进行语法制导翻译时，直接用布尔运算符替换，既and&&，or||，not！；当接口约定后，直接用表中列的索引值代替列名，如：{0}='d' and {3}<=5 and (not {5}=9)。计算布尔表达式时可以先拆分每个表达式，逐个求值。如果从左到右依次扫描求值时，算法如下：设立两个栈：运算符号w栈和运算分量a栈，步骤如下：（1） 从左到右扫描布尔表达式，遇到运算分量，则运算分量入a栈，继续本步。否则遇到运算符，则进行下一步，即转（2）；（2） 检查w栈内有无元素，若没有，则当前运算符进w栈，转（1），否则进行（3）；（3） 比较运算符的优先级别，若当前运算符的优先级别大于w栈顶的运算符的优先级别，则当前运算符进w栈，转（1），否则进行（4）；（4） 根据w栈栈顶运算符的性质（单目或多目运算符），在a栈顶取一个或两个分量，进行计算，并把结果T送入a栈，转（2），重复上述过程，直至结束。部分程序见附录。5.3.3 如何判断逻辑运算符优先级别先定义一个优先级别表，表里包含了运算符及其优先级别的对应关系，包括大于、小于、等于，输入运算符即可得到其运算级别进行运算优先判断。优先级别如下图 5 4：图 5 4 优先级别图5.4 单表和多表查询的设计对单表和多表的查询，均使用函数，具体如下：（应增加查询的具体实现）（1）单表：bool CheckCondition(string aryColData[],Type aryColType[],string sCondition){…}其中：数组aryColData[]，存放表中列名的索引值；数组aryColType[]，存放数据类型；sCondition，为条件表达式；条件经语法制导翻译为数值形式，如：{0}='d' && {3}<=5 && (!{5}=9){i}中i表示列值，与 tp 和 ary 的索引值相对应，表示相关列（2）在单表的基础上，实现多表。多表：bool CheckCondition(string Arraylist[],Type[] aryColType,string sCondition){…}其中：Arraylist 为数组矩阵，每个元素Item 包括String data[], type Type[], 各个Item里数组长度未必相等； aryColType[],存放数据类型； sCondition为条件表达式。单表和多表若要根据数据类型进行更多控制，则可使用 aryColType以判断日期、字符等类型。
6 总结与展望6.1 总结本文基于自主知识产权数据库数据定义语言的词法分析、语法定义规则、语法分析的工作原理，充分运用编译原理中的语义分析，语法制导翻译的理论知识，综合运用数据结构的基础上。在Visual C++6.0开发平台上对自主知识产权数据库中的查询语句的语义分析进行设计与实现。在进行语法分析的同时，通过语法制导翻译，实现语义分析，主要实现的功能有：接口参数约定，传入后，能正确的进行替换，翻译成易于计算的形式，如：{0}='d' && {3}<=5 && (!{5}=9)。语义正确时，经分析后能够正确显示表名和相应的列名；错误时，给予提示。布尔表达式的计算结果，用以检查条件是否成立，为事务处理提供函数接口，以便进行正确的查询。本文只是对数据查询语句作初探，是对SQL语言中的查询语句进行简单的语义分析所以不是太完善，不能达到理想的效果。对函数、语句的类型检查不能实现，只能对简单的类型匹配进行检查，如：数据类型匹配，越界等。对SQL语句中多表查询，函数的引用，还不能正确的判断是否正确，不能进行正确的语义分析。当SQL语句的语法出错时分析器只能直接跳出显示语法错误，但不能给用户以详细的信息，告诉用户是什么原因，造成了不能接受这条语句。本文在产生式的文件输入时，必须要输入正确，否则计算结果就会出错。如果要修改产生式，只有在程序目录中将产生式文件删除后，并且更改产生式条数后，才可以正确运行。终结符和非终结符的个数是限定的。在各个算法中循环次数比较多。所以运算效率不是太高。本文来源于自主知识产权数据库项目中的一个模块。在掌握了编译原理基本理论的基础上，通过进行自主知识产权数据库之查询语句QL的语义分析与实现，学习了编译器的设计思想，加深了对编译原理的理解，使数据库及编程方面的知识得以充分应用，针对编译过程中的重点和难点进行了编程实践；独立完成了一定工作量的程序设计，检验了大学四年专业知识的学习情况，已经达到目的。6.2 展望虽然能对简单的数据查询语句能进行语义分析了，但还有很多可以完善的工作。主要在以下几点：（1） 要实现多表查询，就要更改词法分析表的结构，当时定义的结构是一维数组，只能进行单表查询；（2） 要能够进行完全的类型检查，包括函数的检查，语句和表达式的检查，就要扩充语法结构函数的定义，表达式的定义等；（3） 增加终结符和非终结符的定义，以便能实现更多的查询语句，而不是只能进行简单的查询；（4） 对程序进行优化，以便提高运算效率，由于在语法分析阶段采用LL(1)分析法，分析能力有限，要扩充其分析能力，至少在语法分析阶段采用LR分析法。（5） 对复杂语句的查询，要考虑对文法左递归的消除。（6） 对查询优化时，要在词法结构中对关键字进行定义。如果时间允许，对以上存在需要改进的地方，不仅能提出设计的思想和改进的方法，而且能在实践中实现。希望能在以后的工作中，完成比较复杂的查询语句语义分析，在进行比较大的设计和实现时，考虑的更全面。
查询语句QL的语义分析和实现参考文献[1] （美）James R ． Groff 著；章小莉，宁欣，汪永好等译．SQL完全手册．北京：电子工业出版社，2003.7．[2] (美) Robert Sheldon 著；黄开枝，冉晓旻译．SQL实用教程．北京：清华大学出版社，2004.2[3] 霍林，吴中福．编译技术课程设计与上机指导．重庆：重庆大学出版社，2001.9．[4] 吕映芝，张素琴，蒋维杜等．编译原理．清华大学出版社，1998．1．[5] 何炎祥，李飞，李宁，等．编译原理及其习题解答．武汉：武汉大学出版社，1998．[6] 陈意云 ．编译原理和技术．合肥：中国科学技术大学出版社，2003．1．[7] 夏云龙．最新Visual C++使用手册．北京：电子出版社，2005．1．[8] (美)克力吉尔（Kriegel ,A.）著；陈冰等译．北京：电子工业出版社，2003.9．[9] 邝硕，张清辉，方树昌，等．数据库原理及应用.华南理工大学出版社,1990．[10] 肖军摸.程序设计语言编译方法．大连理工大学出版社．2000．[11] 严蔚敏,吴伟民,数据结构（C语言版）.清华大学出版社,2003.[12] Jeffrey D．Ullman Jennifer Widom．数据库系统基础教程.机出版社．2000．[13] Pittman T, Peters J．The are of Compiler design theory and practice ．USA :Prentice –Hall ,1992．[14] Augusto Sampaio, An Algebraic Approach to Compiler Design,World Scientific Publishing Co ． Pte.Ltd, 1997．[15] Compliers Principles techniques and Tools, Alfred V.Aho,Ravi Sethi Jeffrey D.Ullman, China Machine Press 2004[16] Holub A I.Compilers Design in C.Englewood Cliffs.New Jersy,Prentice-Hall,1990[17] Pittman T,Peters J.The are of Complier design theory and practice.USA:Prentice-Hall,1992[18] Date C J.An Introduction to Database System(Ed.6).Addison-Wesley,1995
指导教师简介张，女，硕士，副教授。曾参与云南省信息网络开发技术专项计划项目“基于安全操作系统平台的PKI网络信息安全软件系统”的研发工作，参加了云南省自然科学基金资助项目“基于网络信息安全的椭圆曲线密码算法研究”。参加了云南大学理（工）科校级项目“支持软件构件演化的配置管理研究与应用”。在《计算机工程》、《计算机应用》和《计算机应用研究》等期刊上发表论文8篇。参与了计算机99、计算机2000和计算机2001共三届本科毕业论文的指导工作。 致 谢在此我衷心的感谢张老师和赵老师。两位老师对提出的问题都认真对待，不厌其烦的给予详细解答。在理论方面张雁老师给予了全力的帮助，在算法设计方面得到了赵家刚老师的指导。除此之外，感谢狄光智老师教会我基本的论文排版技术，还有就是我们班同学的帮助。有了他们细心指导和帮助，我的论文才得以顺利完成。同时也感谢计科系所有老师对我四年的教导。
查询语句QL的语义分析和实现 布尔表达式求值计算的部分程序：typedef struct{ int *base; int *top; int stacksize;}s_stack;//定义一个操作数栈typedef struct{ char *base; char *top; int stacksize;}f_stack;//定义一个运算符栈static char youxian[6][6]= { {'>','>','<','<','>','>'},{'>','>','<','<','>','>'}, {'>','>','>','<','>','>'},{'<','<','<','<','=','>'}, {'>','>','>','>','>','>'},{'<','<','<','<','<','='} };//算符间的优先关系int in(char c){ switch(c) { case '&&': return 0; case '||': return 1; case '!': return 2; case '(': return 3; case ')': return 4; case '#':return 5; default:return 9; }}void s_push(s_stack *s,int e){ if(s->top-s->base>=s->stacksize) { //栈满增加存储空间 s->base=(int *)realloc(s->base,(s->stacksize+stackincrement1)*sizeof(int)); if(!s->base) exit(0);//存储分配失败 s->top=s->base+s->stacksize; s->stacksize+=stackincrement1; } *s->top=e; s->top++; }void f_push(f_stack *f,char e){ if(f->top-f->base>=f->stacksize) { f->base=(char *)realloc(f->base,(f->stacksize+stackincrement2)*sizeof(char)); if(!f->base) exit (0); f->top=f->base+f->stacksize; f->stacksize+=stackincrement2; } *f->top=e;f->top++; }int s_gettop(s_stack *s){ //取栈顶元素 s->top--; return *s->top;}char f_gettop(f_stack *f){ f->top--; return *f->top;}char pduan(f_stack *f,char c)//判断优先{ int m,n; char w; m=in(c); w=*(f->top-1);www.lwfree.cnp,char* r,char q){ switch(r) { case '&&': return q&&p; case '||': return q||p; case '!': return !q,!p; }} int yunsuan(char p,char r,){ switch(r) { case '!': return !p; }}
