【SQL开源代码栏目提醒】:文章导读:在新的一年中,各位网友都进入紧张的学习或是工作阶段。
网学会员整理了SQL开源代码-数据库查询语言SQL的语法分析及实现 - 毕业设计的相关内容供大家参考,祝大家在新的一年里工作和学习顺利!
中文摘要 近年来商用数据库系统不断发展,除了不断完善的大型数据库管理软件Oracle、DB2、SQL Server外,面向中小型企业的数据库也层出不穷,其中又以开放源
代码的MySql最为流行。
但是国内尚且没有自己的数据库系统管理软件,作为计算机专业的学生,学习、掌握数据库系统的实现方法在理论研究和实际应用中都有很大意义。
本文从编译原理入手,在研究编译过程及相关知识的基础上,研究了数据库查询语言SQL从底层数据结构到上层语法分析的实现过程。
对SQL语言实现的几个重要方面做了详细的论述,包括:数据库中表的存储结构以及其提供的相应的上层接口,用索引文件和数据文件实现存储结构,并用c语言编写接口程序;应用正则表达式、有穷自动机、上下文无关文法的相应知识进行SOL语言词法、语法分析,并且利用了词法分析工具Lex和语法分析工具Yacc,提高了工作效率并且保证了生成的语法分析器的正确性。
为了介绍Lex、Yacc的使用,还阐述了一个简单的过程语言实现的方法和过程,并且为非过程语言SQL的实现提供了良好的基础。
关键词:数据库、编译程序、SQL语言、Lex,Yacc ABSTRACT The commercial database management soRware is developing quicldy all theseyears recently,including Oracle)DB2,SQL Server;,the middle and small databasemanagement software is also very popular,Postgresql and MySql being the mostfavorable one.However,in China there still remains the situation that we do not haveOI.U”own database management soft-ware.As a student of Computer Science,to lesmand inaster the technique in the realization of a database management system issignificant both in research and appliance values. This article is based 011 the principle of compiler.Atter considered the processand theories ofthe complier,the article realized a basic 8tnloture used in DBMS and aSQL syntax analyzer鹊well.There are important aspects in this article as follow:theimplementation of data store structure and the interface it provides to the upperdataba.≤e system.The data structure is realized by using all index file and a data file,while the interface is coded with C language;Use the theory of lexical analysismodule and semantic analysis module and then 1瑚the tools Lex and Yacc to realizethe SQL!;yIltRX analyzer,which is 11lore efficiency and c趾be mole correct duringcoding,In order to demonstrate the use of Lex and Yacc,the article also show theprocess of generating a仃aditional procedure language.And that give a good practicalreference for the SQL syntax analyzer.KEY WORDS:Database,Compiler,SQL,LEX,YACC 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得鑫窒盘茔或其他教育机构的学位或证书而使用过的材料。
与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。
学位论文作者签名:蓥寓 签字日期:加,年≥月彬日 学位论文版权使用授权书 本学位论文作者完全了解鑫生盘鲎有关保留、使用学位论文的规定。
特授权鑫壅盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。
同意学校向国家有关部门或机构送交论文的复印件和磁盘。
(保密的学位论文在解密后适用本授权说明)学位论文作者签名:耥 导师躲避浪幽致签字日期:≯一f年2月7,日 签字日期:≯一f年≥月≯)日 第一章概述 第一章概述1.1数据库管理系统简介 数据库来自于已经发展了数十年的知识和技术,这些知识和技术蕴藏在被称作数据库管理系统的专业化软件中,该软件也被称作DBMs【l】。
数据库技术的出现正是为了满足人们对管理庞大的信息资源并加以有效的利用的需求。
本质上讲数据库是信息的集合,通过数据库技术人们可以方便、高效、安全的管理庞大、复杂、多样的数据。
这种数据的集合可以在存储媒质中存在很长时间。
数据库管理软件需要提供如下的功能:●允许用户使用专门的数据定义语言∞DL)建立新的数据库,并说明它们的逻 辑结构。
·使用合适的数据操纵语言(DML),为用户提供查询和更新数据库中数据的能 力〔2】。
●支持超大的数据容量,数据的长时间存储,防止对数据意外的或非授权的访 问。
·控制多个用户对数据的立即存取,不允许用户间操作的相互影响。
1.2数据库系统研究目的和意义 从八十年代以来擞据库技术在商业领域的巨大成功刺激了其它领域对数据库技术需求的迅速增长,包罗万象的信息日益膨胀以及这些信息为人们日常工作、决策带来的便利更加在无形中奠定了数据库在当今信息社会的重要地位。
另外,数据库管理系统和操作系统是信息管理的核心软件,现在我们国家无论在理论上还是在技术上与国外产品都有一定的差距。
随着国际形势的复杂化,研制和开发自己的核心软件有了比以往更加重要的意义,特别是作为信息管理的核心软件一数据库系统软件。
虽然新一代的数据库技术已经渐渐成为数据库研究领域的热点,但是实际应用中还是关系数据库占据了主导的地位。
正因为这样,基于关系数据库的数据查询语言SQL的实现对于实现自己的数据库管理软件来说也至关重要。
编译的原理与技术,在80年代初已经发展的比较完备了。
但是我国90年代 第一章概述后才生产自己的芯片,开始做自己的编译器。
那时还没有因特网,学习国外的技术受到很大局限,整体水平与国际上有较大差距。
现在随着信息时代的来临,研究制作自己的编译器已经变得相当迫切。
现今编写编译器一般应用工具LEX和YACC〔3〕,在Unix操作系统下,分别有Bison和FLex可以供选择,在Window¥XP下则有Parser Generator。
本文的主要目的也是由底层到上层,逐步的分析实现SQL语言的分析程序。
1.3本文研究内容及结构 本文首先讨论了为实现上层SQL语言数据库系统需要提供的底层接口。
通过一个数据库表的存储结构的简单的模拟,来描述出数据库底层的存储结构相关方面的问题,并且用c语言实现了对相应的索引文件和数据文件操作的接口描述。
这样就有了简单的接口可以为将来生成的SQL语言语法分析结果所调用。
然后,为了使用词法、语法分析工具,在Windows操作系统下进行了ParserGenerator软件相应的配置,并且介绍了词法分析工具Lex和语法分析工具Yacc的使用方法。
其次,分析了面向过程语言的实现方法,通过应用Lex词法分析,并利用Yaec语法分析,生成函数指针堆栈,不仅熟悉了Lex、Yacc在实现程序设计语言中的应用,也为分析SQL语言提供了良好的实现基础。
最后,结合SQL语言规范中最复杂也最具有代表性的Select语句进行语法分析,通过对Select语句的分析,阐述了对于非过程语言SQL的分析方法,而SQL语畜中其余语句的处理方法与Select语句的处理方法大致相同。
第二章数据库中的数据存储 第二章数据库中的数据存储 数据库中的数据怎么存储在磁盘上是一个数据库系统需要决定的最重要的技术之一。
因为好的数据存储结构可以使得数据库系统的性能有很大的提高。
当访问的数据量很大的时候,把所有数据均写入主存储器是不可能的,所以决定怎样存储以及怎样在主存和外存之间调用数据是非常重要的。
随着底层数据存储方式的确定,数据库系统为上层的SQL语句分析结果提供了各种接口,使得¥QL语言的实现并不依赖于底层的存储方式。
当然为了调试方便,并且可以进行简单操作的演示,本文中不仅给出了一个合理的但却是相对简单的数据存储结构,而且还给出了实现简单接口的所有源
代码。
2.1数据库系统表文件结构 为了使问题相对比较简化,但是又不失数据库系统的一般特点,这里采用如下的数据库存储结构。
首先以表为单位,一个数据库表包含了两个部分,一个索引部分,一个数据部分。
其中索引文件为表名加后缀.idx,而数据文件为表名加后缀.dat。
其总体结构如图2.1 第二章数据库中的数据存储索引文件结构t r………………一。
救据文件。
; I 图2-1索引、数据文件结构2.1.1索引文件组成 索引文件存储了表中各项的关键字值,以便于查询,并且还存储了对数据文件中对应数据项的偏移地址。
有很多方法可以组织索引文件,最常用的是B.树和hash表〔4】,这里采用了定长的hash表,当然也有很多种方法来解决hash表冲突问题,这里采用的是链表方法。
在这里使用固定大小的散列表作为索引是一个妥协。
当每个散列链均不太长时,这个方法能保证快速地查找。
我们的目的是能够快速地查找任意一个关键字,同时又不使用太复杂的数据结构,如B树或动态可扩充散列表。
动态可扩充散列表的优点是能保证仅用两次磁盘操作就能找到数据记录。
B树能够用关键字的顺序来遍历数据库。
数据库中的数据大多是以字节为最小的存储方法,虽然对于小的字段将一个字节分成多个bits来存储不同的内容可以提高存储空间的利用,但是随着现在存储器价格的下降,这一做法是费力的并且对系统性能没有显著提高,这里就直接采用了字符串流来存储索引和数据,这样不仅方便编程实现,而且在调试的时候也能够更直观的检查存储数据的情况。
在存储的时候规定有且只有一个关键字用于索引,虽然实际中常常可以存在多个索引以便提高查询效率,但是具体到技术 第二章数据库中的数据存储上,和仅有一个索引没有太大的差别,比如可以用多个索引文件来实现。
所以上述的假设对系统的初步构建是可行的。
2.1.2数据文件组成 数据文件并不是按照索引文件的顺序存储的,事实上查找数据的时候总是先根据关键字在索引文件中找到对应数据项在数据文件中的偏移,再根据偏移去查找相应的数据。
这里为了方便查看,在数据文件中,每一条数据记录的最后都加上了换行符号。
这样数据文件看起来就更方便一些,尽管不要换行符号可以使得每一条记录都节省2字节的大小,但是考虑到调试的方便,这里还是加入了相应的程序来输出换行。
2.1.3程序效果 下面结合一个具体的数据库表的两个文件来说明各部分的意义: DB+cl=db_open(”c:\\testTable”.O CREATE); db_a州d,”cailei”,”this is the first data”,DB_INSERT); db_store(cl,”wuweiming”,’’beta data”,DB_INSERT); db_store(cl,”zhangli锄矿,”another would be fine”,DB_INSERT); db_store(吐’恤岫g印dong”,”he is a cheaper”,DB_INSERT); db._close(c1); 上面的程序产生如下的文件: tesfrable.idx 0 89 63 39 0 12cailei:0:22 0 15wuweiming:24:9 0 17zhangliang:35:21 18 18huangpudong:58:15 testTable.dat this is the first data beta data another would be fine heisacheaper 索引文件的第一行为0 89 63 39分别为空闲链表指针(0),第一个散列 第二章数据库中的数据存储表指针(89),第二个散列表指针(63)和第三个散列表指针(39),这里只用到三个散列表,对于实际数据库而言,采用hash表查询应该拥有更多得散列表,这样可以减少匹配冲突,从而减少每个散列表的长度,进而提高数据库查询、插入效率。
每个散列表指针有4位,这样可以查到0-9999偏移的数据,在数据量不是很大的情况下应该已经足够。
这后的各行显示的是索引记录,比如第二行O12cailei:0:22,其中0表示此记录是其所在散列表的最后一项记录,紧跟的12是此条索引记录剩余的长度(包括了换行符)。
然后是记录的关键字此条记录的关键字为eailei,最后两个用:分开的部分,第一个是数据文件中对应数据项的偏移,第二个是数据项的长度。
数据文件顺序记录了相应的每条记录的内容,在每条记录的结尾都有回车和换行符(0DOA)。
2.2底层与上层接口 SQL语言包含了数据定义语言∞DL)、数据操纵语言(DML)和数据控制语言(DCL)。
这里的接口主要针对DDL和DML来操作,因为DCL更主要的集中于对数据完整性、安全性等方面的考虑,虽然在一个完整的数据库系统中十分重要,可是在核心的实现中为了减化问题,逐步深入,所以在基本的数据库底层接口中没有相对应的函数。
DB’db_opvn(const char’pathname.int oflag) 是数据库表的创建以及选择函数,pathname为表所在的目录加表名,函数中会自动打开相应的.idx文件和.dat文件,但是必须保证两个文件在相同的目录下,否则发生错误。
oflag说明打开表的方式,为O CREATE说明此函数新建一个数据库表;为O WRITE说明将要对打开的数据库表进行更新、插入等写操作;为O READ说明将要对打开的数据库表进行查询等读操作。
void db_close(DB+db) 每次操作完数据库表的时候都应该在最后释放文件流指针,并且释放内存相应的块,此工作由db_dose函数完成。
int db_store(DB+db.const char+key,consl char+data,int flag) 是存储、更新数据库表中各项的函数,按照关键字key在索引文件中查找到相应的数据在数据文件中的位置,然后根据flag的值来进行插入或者更新,当 第二章数据库中的数据存储flag值为DB_INSERT时,将dala中的内容插入表中,并按相应的步骤修改索引文件和数据文件:当flag值为DB_REPLACE时,查找到key所对应的纪录并且将纪录内容更换为data中的内容,然后修改索引文件和数据文件的对应部分。
int db_delete(DB+db,const char+key) 是删除数据库表中特定记录的函数,首先按照关键字key来查找相应的记录,然后在索引文件中删除索引,并作相应的文件结构的调整,然后在数据文件中把对应的记录项删除。
char*db._fetch(DB‘曲,eonst char.key) 是取特定记录的函数,根据关键字key在索引文件中查找对应项的记录位置,然后根据结果返回数据文件中找到对应的项内容,并且把内容返回。
有了以上的函数,基本的SQL语言就可以调用相应的底层接口函数了。
这不仅方便了对SQL语言编译器的调试工作,而且也可以直观的检查到数据库表的索引文件和数据文件的结构。
当执行: db store(a,”alpha”,’‘alpha data”,DB_INSERT); db_store(cl,’。
beta”,”beta data is ok”,DB_INSERT); 后索引文件和记录文件如下: testTable.idx O 89137116 0 12eailei:O:22 0 15wuweiming:24:9 0 17zhangliang:35:21 18 18huanglmdong:58:15 39 12alpha:75:lO 63 1lbeta:87:15 testTable.dat this is the first data beta data a∞therⅥ侧d be fine heisacheaper alpha data betadataisok 第二章数据库中的数据存储 接着执行 db_delete(cL”zhangliang”); db_delete(cl,”huangpudong”); 后索引文件和记录文件如下: testTable.idx 89 18137116 0 12c,ailei:0:22 0 15wuweiming:24:9 0 17 :35:21 63 18 :58:15 39 12alpha:75:10 O llbeta:87:15 testTable.&at this is the first data beta data alpha data betadatais ok2.3进一步探讨 当然由于真正的数据库系统需要考虑的问题远远多于文中提到的方面,因而上述函数也有很大的局限性,比如只能对于关键字来查找、更新以及删除;如果想要对表中任意的字段进行操作,虽然理论上更加简单,但是无疑需要更多的操作,而且当测试数据量不够多的时候仍然没有办法看出效率问题,但是当数据足够多的时候,又需要考虑存储结构,以及内存外存间数据交换等具体的底层问题。
而本文的主要目的在于生成SQL语言的语法分析器。
所以对于具体的底层实现就从简处理了。
不可否认的是,这样的简化处理虽然和实际有一定的差距,但是其内核结构已经足以反映数据库系统的基本功能,并且通过合理地扩展可以有效地推广到更复杂的结构。
对于复杂的结构,要考虑更细致,更复杂的问题,简要的做一个概念性的说明如下: 第二章数据库中的数据存储 现实中的DBMS系统还应该考虑如何有效的处理非常大量的数据。
包括计算机系统是如何存储和管理非常大量的数据的,用何种表示方式和数据结构是对有效处理此类数据的最佳支持。
因此相应的应该考虑到存储器的性能、价格,并考察数据在主存储器与辅存储器乃至三级存储器之间移动的模式以及模式对于涉及大量数据算法的效率。
间断性读写错误的处理,以及造成数据不可读写的“磁盘崩溃”的处理。
更为详细和全面的内容可以参阅参考文献中相应的资料。
第三章LexYacc应用介绍 第三章Lex Yacc应用介绍 Lex和Yacc都是在20世纪70年代由贝尔实验室开发的〔5】。
Yacc的开发早于Lex,它是由StephenC.Johnson开发的。
为了与Yacc一起工作,MikeLesk和Eric Schmidt开发了Lex。
自第7版UNIX以来,Lex和Yacc已经成为标准的UNⅨ实用程序。
自由软件基金会的GNU工程组发布了Bison,即Yacc的替代品,Bison是由RobertCorbett和Richard Stalhnan编写的【6】。
同样的在BSD和GNU工程组还发布了FLex(快速词法分析生成器,Fast Lexical Analyzer Generator),FLex最终是由JefPoskanzer编写的,Vem Paxson和Van Jacobson又对它进行了重大的 。
改善【7】。
但是无论如何,Bison、FLex都是UNIX操作系统下的
开源软件,由于UNIX系统的库函数和Windows下的还是有所差别的,所以在Windows下选择使用软件parser generator来代替UNIX下传统的Yacc、Lex软件,Parser Generator提供了自己的Lex、Yacc实现,并且采用了相应的Windows库函数,它不仅将Lex和Yacc集成到了一个编译系统环境中,而且还提供了对应的面向对象的词法分析和语法分析的类,使得用户也可以根据需要生成相应的对象来进行词法、语法分析。
下面就介绍一下在Windows操作系统中如何配置Parser GeneratortS〕以便其集成到vC++6.0编程环境中,这样生成的“c++)程序
代码可以直接编译、连接、执行,而且还可以利用vC-H16.0环境进行调试工作。
3.1配置Parser Generator 首先安装ParserGenerator到计算机中的某个目录下,这里用”用户安装目录、”为准,以后凡是碰到需要到相应安装目录下配置的时候都以”用户安装目录\”开始。
安装完成后在”用户安装目录、,’下生成的几个目录如下; BⅡ吼 此目录下为可运行的Yacc、Lex编译器执行文件ALex.c】【e、AYacc.懿e以及Parser Generator的集成环境,可以直接在继承环境中调用ALex.既e和AYacc.c,【e来完成从.1和.Y文件生成.c文件的过程。
INCLUDE\此目录下包含了ParserGenerator需要用到的所有编译.1和.Y文件所需要用到的头文件,包含了ALex和AYacc所用到的所有内部函数,也包含了 第三章Lex Yacc应用介绍面向对象的Yacc、Lex类的声明。
. Lm、 此目录下包含了3个子目录(BORLAND\MSDEV、MSVCA)分别对应了流行的c十+语言编译器,为了使得Parser Generator可以集成于不同的c编译环境,其中BORLAND对应了相应的Bodand C_H编译器,MSDEV对应了vC.阡的编译环境,而MSVC对应着其他的编译环境如GCC等。
SOURCE\此目录下为Parser Generator的源
代码,因为在声明中ParserGenerator的库函数和Yacc、Lex标准中定义的有一定的差距,所以在用ParserGenerator生成词法、语法分析器的时候仍然需要不时地参考相应的函数原型。
然后在Vc++6.0环境中作如下配置 只需要在v口斗6.0环境中做一次就可以的配置 “工具”菜单.、’”选择”选项.>’’目录”选项卡.>在”显示目录为”下拉菜单中选择”include files”的路径中添加”用户安装目录\玳CLUDE’’ 同样在”显示目录为”下拉菜单中选择’’library files”的路径中添加”用户安装目录\Lm、MSDE、p 最后在”显示目录为”下拉菜单中选择”80uroe files’’的路径中添加”用户安装目录\sOURCE,’ 以上的配置只需在vc++6.0环境中做一次即可,但后面的配置在每个Yacc、Lex T程中都需要配置 在每个工程中选择”工程”菜单->,’设置”选项.>’,卅,’选项卡.>”预处理程序定义”后面加上”。
YⅥ)EBUG”。
然后选择”setting for’’下拉选项中的’’debug’’选项->在”link’’选项卡->,’对象\库模块”后面加上”ytd.1ib” 最后选择然后选择”setting for’’下拉选项中的’’release’’选项->在’’link’’选项卡-、,对象、库模块”后面加上”y1.1ib” 这样,一个Yacc、Lex T程就配置完成了,可以将用Parser Generator编译生成的.c文件添加到工程当中,然后就可以应用VC-H6.0编译环境去编译、连接,调试程序了。
3.2使用Lex Lex属于GNU内部的工具,它通常都是gcc的附带工具.如果使用Linux操作系统,那么肯定系统本身就有Lex和Yace,不过Yacc的名字变成了bison〔9〕,而Lex变成了fLex。
Lex可以通过一个输入文件,然后生成扫描器的C源
代码. 分析正则表达式的方法是,从正则表达式到NFA,再到DFA〔10〕,应用Lex 第三章LcxYacc应用介绍我们只需要把相应的正则表达式输入,然后Lcx就能够为我们自己生成DFA,然后生成源
代码。
3.2.1正则表达式 正则表达式的定义如下: 1.基本正则表达式由一个单字符o/(其中口在正规字符的字母表乞中),以及元字符占或元字符≯组成。
在第1种情况下,工@)2缸);在第2种情况下,工@)2p);在第3种情况下,三(妒)2{}。
2.715格式的表达式:其中,和j均是正则表达式。
在这种情况下,L(rIJ)=L(r)U£O)。
3.IS格式的表达式:其中,和J是正则表达式。
在这种情况下,以rs)=工(r)£O). 4.r.格式的表达式:其中,是正则表达式。
在这种情况下,L(r+)2工(r)’。
5.(,)格式的表达式:其中r是正则表达式。
在这种情况下,L((,))2三(,),因此,括号并不改变语言,它们只调整运算的优先权。
对于将正则表达式转换成相应的NFA方法如下:对于基本的正则表达式如图3-1所示: 图3-1基本正则表达式到DFA对于正则表达式中选择7Is、连接憎、重复一的DFA表达分别示于图3-2 第三章Lex Yacc应用介绍 图3-2选择、连接、重复到DFA3.2.2 Lex程序格式 事实上,在Lex中书写正则表达式相当方便,因为Lex的规范中为用户定义了书写正则表达式所有常用的符号,并且还增加了许多可以提高效率的符号D1〕。
具体含义如表3.1所示: 表3-1 Lex中应用的符号 匹配除换行符(‘‘、n,,)外的任何单个字符 匹配前面表达式的零个或多个拷贝 ● 口 匹配方括号中的任意字符的字符类。
除了识别以’V开始的转义序列 外,其他的字符在方括号中没有特殊的含义。
作为正则表达式的第一个字符匹配行的开头。
也可用于方括号中的否定。
¥ 作为正则表达式的最后一个字符匹配行的结尾 {) 当括号中包含一个或2个数字时,表示前面模式被允许匹配的次数 | 用.
上一篇:
谈SQL注入攻击的种类及其防范措施
下一篇:
临床前药物安全性评价中毒性病理学新技术的应用