（计算机软件与理论专业论文）数据库查询语言sql的语法分析及实现.pdf

中文摘要 近年来商用数据库系统不断发展，除了不断完善的大型数据库管理软件 o r a c l e 、d b 2 、s q ls e r v e r 外，面向中小型企业的数据库也层出不穷，其中又以 开放源代码的m y s q l 最为流行。但是国内尚且没有自己的数据库系统管理软件， 作为计算机专业的学生，学习、掌握数据库系统的实现方法在理论研究和实际应 用中都有很大意义。 本文从编译原理入手，在研究编译过程及相关知识的基础上，研究了数据库 查询语言s q l 从底层数据结构到上层语法分析的实现过程。对s q l 语言实现的几 个重要方面做了详细的论述，包括：数据库中表的存储结构以及其提供的相应的 上层接口，用索引文件和数据文件实现存储结构，并用c 语言编写接口程序；应 用正则表达式、有穷自动机、上下文无关文法的相应知识进行s o l 语言词法、语 法分析，并且利用了词法分析工具l e x 和语法分析工具y a c c ，提高了工作效率 并且保证了生成的语法分析器的正确性。为了介绍l e x 、y a c c 的使用，还阐述了 一个简单的过程语言实现的方法和过程，并且为非过程语言s q l 的实现提供了良 好的基础。 关键词：数据库、编译程序、s q l 语言、l e x ，y a c c a b s t r a c t t h ec o m m e r c i a ld a t a b a s em a n a g e m e n ts o r w a r ei sd e v e l o p i n gq u i c l d ya l lt h e s e y e a r sr e c e n t l y , i n c l u d i n go r a c l e ) d b 2 ，s q ls e r v e r ；, t h em i d d l ea n ds m a l ld a t a b a s e m a n a g e m e n ts o f t w a r ei sa l s ov e r yp o p u l a r , p o s t g r e s q la n dm y s q lb e i n gt h em o s t f a v o r a b l eo n e h o w e v e r , i nc h i n at h e r es t i l lr e m a i n st h es i t u a t i o nt h a tw ed on o th a v e o i u o w nd a t a b a s em a n a g e m e n ts o f t - w a r e a sas t u d e n to fc o m p u t e rs c i e n c e , t ol e s m a n di n a s t e rt h et e c h n i q u ei nt h er e a l i z a t i o no fad a t a b a s em a n a g e m e n ts y s t e mi s s i g n i f i c a n tb o t hi nr e s e a r c ha n da p p l i a n c ev a l u e s t h i sa r t i c l ei sb a s e d0 1 1t h ep r i n c i p l eo fc o m p i l e r a t t e rc o n s i d e r e dt h ep r o c e s s a n dt h e o r i e so f t h ec o m p l i e r , t h ea r t i c l er e a l i z e dab a s i c8 t n l o t u r eu s e di nd b m sa n da s q ls y n t a xa n a l y z e r 鹊w e l l t h e r ea r ei m p o r t a n ta s p e c t si nt h i sa r t i c l ea sf o l l o w ：t h e i m p l e m e n t a t i o no fd a t as t o r es t r u c t u r ea n dt h e i n t e r f a c ei tp r o v i d e st ot h eu p p e r d a t a b a es y s t e m t h ed a t as t r u c t u r ei sr e a l i z e db y u s i n ga l li n d e xf i l ea n dad a t af i l e , w h i l et h ei n t e r f a c ei sc o d e dw i t hcl a n g u a g e ；u s et h et h e o r yo fl e x i c a la n a l y s i s m o d u l ea n ds e m a n t i ca n a l y s i sm o d u l ea n dt h e n1 瑚t h et o o l sl e xa n dy a c ct or e a l i z e t h es q l ! ；y i l t r xa n a l y z e r , w h i c hi s1 1 l o r ee f f i c i e n c ya n dc 趾b em o l ec o r r e c td u r i n g c o d i n g , i no r d e rt od e m o n s t r a t et h eu s eo fl e xa n dy a c c ，t h ea r t i c l ea l s os h o wt h e p r o c e s so fg e n e r a t i n ga 仃a d i t i o n a lp r o c e d u r el a n g u a g e a n dt h a tg i v eag o o dp r a c t i c a l r e f e r e n c ef o rt h es q l s y n t a xa n a l y z e r k e y w o r d s ：d a t a b a s e ，c o m p i l e r , s q l ，l e x ，y a c c 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫窒盘茔或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：蓥寓签字日期：加，年月彬日 学位论文版权使用授权书 本学位论文作者完全了解鑫生盘鲎有关保留、使用学位论文的规定。 特授权鑫壅盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：耥 签字日期：一f 年2 月7 ，日 导师躲避浪幽致 签字日期：一f 年月) 日 第一章概述 1 1 数据库管理系统简介 第一章概述 数据库来自于已经发展了数十年的知识和技术，这些知识和技术蕴藏在被称 作数据库管理系统的专业化软件中，该软件也被称作d b m s 【l 】。数据库技术的出 现正是为了满足人们对管理庞大的信息资源并加以有效的利用的需求。本质上讲 数据库是信息的集合，通过数据库技术人们可以方便、高效、安全的管理庞大、 复杂、多样的数据。这种数据的集合可以在存储媒质中存在很长时间。数据库管 理软件需要提供如下的功能： 允许用户使用专门的数据定义语言d l ) 建立新的数据库，并说明它们的逻 辑结构。 使用合适的数据操纵语言( d m l ) ，为用户提供查询和更新数据库中数据的能 力 2 】。 支持超大的数据容量，数据的长时间存储，防止对数据意外的或非授权的访 问。 控制多个用户对数据的立即存取，不允许用户间操作的相互影响。 1 2 数据库系统研究目的和意义 从八十年代以来擞据库技术在商业领域的巨大成功刺激了其它领域对数据 库技术需求的迅速增长，包罗万象的信息日益膨胀以及这些信息为人们日常工 作、决策带来的便利更加在无形中奠定了数据库在当今信息社会的重要地位。 另外，数据库管理系统和操作系统是信息管理的核心软件，现在我们国家无 论在理论上还是在技术上与国外产品都有一定的差距。随着国际形势的复杂化， 研制和开发自己的核心软件有了比以往更加重要的意义，特别是作为信息管理的 核心软件一数据库系统软件。 虽然新一代的数据库技术已经渐渐成为数据库研究领域的热点，但是实际应 用中还是关系数据库占据了主导的地位。正因为这样，基于关系数据库的数据查 询语言s q l 的实现对于实现自己的数据库管理软件来说也至关重要。 编译的原理与技术，在8 0 年代初已经发展的比较完备了。但是我国9 0 年代 第一章概述 后才生产自己的芯片，开始做自己的编译器。那时还没有因特网，学习国外的技 术受到很大局限，整体水平与国际上有较大差距。现在随着信息时代的来临，研 究制作自己的编译器已经变得相当迫切。现今编写编译器一般应用工具l e x 和 y a c c 3 ，在u n i x 操作系统下，分别有b i s o n 和f l e x 可以供选择，在w i n d o w $ x p 下则有p a r s e rg e n e r a t o r 。本文的主要目的也是由底层到上层，逐步的分析实现 s q l 语言的分析程序。 1 3 本文研究内容及结构 本文首先讨论了为实现上层s q l 语言数据库系统需要提供的底层接口。通 过一个数据库表的存储结构的简单的模拟，来描述出数据库底层的存储结构相关 方面的问题，并且用c 语言实现了对相应的索引文件和数据文件操作的接口描 述。这样就有了简单的接口可以为将来生成的s q l 语言语法分析结果所调用。 然后，为了使用词法、语法分析工具，在w i n d o w s 操作系统下进行了p a r s e r g e n e r a t o r 软件相应的配置，并且介绍了词法分析工具l e x 和语法分析工具y a c c 的使用方法。 其次，分析了面向过程语言的实现方法，通过应用l e x 词法分析，并利用 y a e c 语法分析，生成函数指针堆栈，不仅熟悉了l e x 、y a c c 在实现程序设计语 言中的应用，也为分析s q l 语言提供了良好的实现基础。 最后，结合s q l 语言规范中最复杂也最具有代表性的s e l e c t 语句进行语法 分析，通过对s e l e c t 语句的分析，阐述了对于非过程语言s q l 的分析方法，而 s q l 语畜中其余语句的处理方法与s e l e c t 语句的处理方法大致相同。 第二章数据库中的数据存储 第二章数据库中的数据存储 数据库中的数据怎么存储在磁盘上是一个数据库系统需要决定的最重要的 技术之一。因为好的数据存储结构可以使得数据库系统的性能有很大的提高。当 访问的数据量很大的时候，把所有数据均写入主存储器是不可能的，所以决定怎 样存储以及怎样在主存和外存之间调用数据是非常重要的。 随着底层数据存储方式的确定，数据库系统为上层的s q l 语句分析结果提 供了各种接口，使得$ q l 语言的实现并不依赖于底层的存储方式。当然为了调 试方便，并且可以进行简单操作的演示，本文中不仅给出了一个合理的但却是相 对简单的数据存储结构，而且还给出了实现简单接口的所有源代码。 2 1 数据库系统表文件结构 为了使问题相对比较简化，但是又不失数据库系统的一般特点，这里采用如 下的数据库存储结构。首先以表为单位，一个数据库表包含了两个部分，一个索 引部分，一个数据部分。其中索引文件为表名加后缀i d x ，而数据文件为表名加 后缀d a t 。其总体结构如图2 1 第二章数据库中的数据存储 索引文件结构t r 一。 救据文件。 ； i 2 1 1 索引文件组成 图2 - 1 索引、数据文件结构 索引文件存储了表中各项的关键字值，以便于查询，并且还存储了对数据文 件中对应数据项的偏移地址。有很多方法可以组织索引文件，最常用的是b 树 和h a s h 表 4 】，这里采用了定长的h a s h 表，当然也有很多种方法来解决h a s h 表冲 突问题，这里采用的是链表方法。在这里使用固定大小的散列表作为索引是一个 妥协。当每个散列链均不太长时，这个方法能保证快速地查找。我们的目的是能 够快速地查找任意一个关键字，同时又不使用太复杂的数据结构，如b 树或动 态可扩充散列表。动态可扩充散列表的优点是能保证仅用两次磁盘操作就能找到 数据记录。b 树能够用关键字的顺序来遍历数据库。 数据库中的数据大多是以字节为最小的存储方法，虽然对于小的字段将一个 字节分成多个b i t s 来存储不同的内容可以提高存储空间的利用，但是随着现在存 储器价格的下降，这一做法是费力的并且对系统性能没有显著提高，这里就直接 采用了字符串流来存储索引和数据，这样不仅方便编程实现，而且在调试的时候 也能够更直观的检查存储数据的情况。在存储的时候规定有且只有一个关键字用 于索引，虽然实际中常常可以存在多个索引以便提高查询效率，但是具体到技术 第二章数据库中的数据存储 上，和仅有一个索引没有太大的差别，比如可以用多个索引文件来实现。所以上 述的假设对系统的初步构建是可行的。 2 1 2 数据文件组成 数据文件并不是按照索引文件的顺序存储的，事实上查找数据的时候总是先 根据关键字在索引文件中找到对应数据项在数据文件中的偏移，再根据偏移去查 找相应的数据。这里为了方便查看，在数据文件中，每一条数据记录的最后都加 上了换行符号。这样数据文件看起来就更方便一些，尽管不要换行符号可以使得 每一条记录都节省2 字节的大小，但是考虑到调试的方便，这里还是加入了相应 的程序来输出换行。 2 1 3 程序效果 下面结合一个具体的数据库表的两个文件来说明各部分的意义： d b + c l = d b _ o p e n ( ”c ：t e s t t a b l e ”oc r e a t e ) ； d b _ a 州d ，”c a i l e i ”，”t h i si st h ef i r s td a t a ，d b _ i n s e r t ) ； d b _ s t o r e ( c l ，”w u w e i m i n g ”， b e t ad a t a ，d b _ i n s e r t ) ； d b _ s t o r e ( c l ，”z h a n g l i 锄矿，”a n o t h e rw o u l d b ef i n e ”，d b _ i n s e r t ) ； d b _ s t o r e ( 吐恤岫g 印d o n g ”， h ei sac h e a p e r ”，d b _ i n s e r t ) ； d b _ c l o s e ( c 1 ) ； 上面的程序产生如下的文件： t e s f r a b l e i d x 08 96 33 9 01 2 c a i l e i ：0 ：2 2 0 1 5 w u w e i m i n g ：2 4 ：9 0 1 7 z h a n g l i a n g ：3 5 ：2 1 1 8 1 8 h u a n g p u d o n g ：5 8 ：1 5 t e s t t a b l e d a t t h i si st h ef i r s td a t a b e t ad a t a a n o t h e rw o u l db ef i n e h e i s a c h e a p e r 索引文件的第一行为08 9 6 33 9 分别为空闲链表指针( 0 ) ，第一个散列 第二章数据库中的数据存储 表指针( 8 9 ) ，第二个散列表指针( 6 3 ) 和第三个散列表指针( 3 9 ) ，这里只用到三个散 列表，对于实际数据库而言，采用h a s h 表查询应该拥有更多得散列表，这样可 以减少匹配冲突，从而减少每个散列表的长度，进而提高数据库查询、插入效率。 每个散列表指针有4 位，这样可以查到0 - 9 9 9 9 偏移的数据，在数据量不是很大 的情况下应该已经足够。这后的各行显示的是索引记录，比如第二行o 1 2 c a i l e i ：0 ：2 2 ，其中0 表示此记录是其所在散列表的最后一项记录，紧跟的1 2 是 此条索引记录剩余的长度( 包括了换行符) 。然后是记录的关键字此条记录的关键 字为e a i l e i ，最后两个用：分开的部分，第一个是数据文件中对应数据项的偏移， 第二个是数据项的长度。 数据文件顺序记录了相应的每条记录的内容，在每条记录的结尾都有回车和 换行符( 0 d o a ) 。 2 2 底层与上层接口 s q l 语言包含了数据定义语言d l ) 、数据操纵语言( d m l ) 和数据控制语言 ( d c l ) 。这里的接口主要针对d d l 和d m l 来操作，因为d c l 更主要的集中于 对数据完整性、安全性等方面的考虑，虽然在一个完整的数据库系统中十分重要， 可是在核心的实现中为了减化问题，逐步深入，所以在基本的数据库底层接口中 没有相对应的函数。 d b d b _ o p v n ( c o n s tc h a r p a t h n a m e i n to f l a g ) 是数据库表的创建以及选择函数，p a t h n a m e 为表所在的目录加表名，函数 中会自动打开相应的i d x 文件和d a t 文件，但是必须保证两个文件在相同的目录 下，否则发生错误。o f l a g 说明打开表的方式，为oc r e a t e 说明此函数新建一 个数据库表；为ow r i t e 说明将要对打开的数据库表进行更新、插入等写操作； 为or e a d 说明将要对打开的数据库表进行查询等读操作。 v o i dd b _ c l o s e ( d b + d b ) 每次操作完数据库表的时候都应该在最后释放文件流指针，并且释放内存相 应的块，此工作由d b _ d o s e 函数完成。 i n td b _ s t o r e ( d b + d b c o n s tc h a r + k e y , c o n s lc h a r + d a t a , i n tf l a g ) 是存储、更新数据库表中各项的函数，按照关键字k e y 在索引文件中查找到 相应的数据在数据文件中的位置，然后根据f l a g 的值来进行插入或者更新，当 第二章数据库中的数据存储 f l a g 值为d b _ i n s e r t 时，将d a l a 中的内容插入表中，并按相应的步骤修改索引 文件和数据文件：当f l a g 值为d b _ r e p l a c e 时，查找到k e y 所对应的纪录并且 将纪录内容更换为d a t a 中的内容，然后修改索引文件和数据文件的对应部分。 i n td b _ d e l e t e ( d b + d b ，c o n s tc h a r + k e y ) 是删除数据库表中特定记录的函数，首先按照关键字k e y 来查找相应的记 录，然后在索引文件中删除索引，并作相应的文件结构的调整，然后在数据文件 中把对应的记录项删除。 c h a r * d b _ f e t c h ( d b 曲，e o n s tc h a r k e y ) 是取特定记录的函数，根据关键字k e y 在索引文件中查找对应项的记录位 置，然后根据结果返回数据文件中找到对应的项内容，并且把内容返回。 有了以上的函数，基本的s q l 语言就可以调用相应的底层接口函数了。这 不仅方便了对s q l 语言编译器的调试工作，而且也可以直观的检查到数据库表 的索引文件和数据文件的结构。当执行： d bs t o r e ( a ，”a l p h a ，a l p h ad a t a ”，d b _ i n s e r t ) ； d b _ s t o r e ( c l ，。b e t a ”， b e t ad a t ai so k ”，d b _ i n s e r t ) ； 后索引文件和记录文件如下： t e s t t a b l e i d x o8 9 1 3 7 1 1 6 01 2 e a i l e i ：o ：2 2 0 1 5 w u w e i m i n g ：2 4 ：9 0 1 7 z h a n g l i a n g ：3 5 ：2 1 1 8 1 8 h u a n g l m d o n g ：5 8 ：1 5 3 9 1 2 a l p h a ：7 5 ：l o 6 31 l b e t a ：8 7 ：1 5 t e s t t a b l e d a t t h i si st h ef i r s td a t a b e t ad a t a a t h e r 侧db ef i n e h e i s a c h e a p e r a l p h ad a t a b e t a d a t a i s o k 第二章数据库中的数据存储 接着执行 d b _ d e l e t e ( c l ”z h a n g l i a n g ) ； d b _ d e l e t e ( c l ，”h u a n g p u d o n g ”) ； 后索引文件和记录文件如下： t e s t t a b l e i d x 8 91 8 1 3 7 1 1 6 01 2 c , a i l e i ：0 ：2 2 0 1 5 w u w e i m i n g ：2 4 ：9 01 7 ：3 5 ：2 1 6 31 8：5 8 ：1 5 3 9 1 2 a l p h a ：7 5 ：1 0 ol l b e t a ：8 7 ：1 5 t e s t t a b l e & a t t h i si st h ef i r s td a t a b e t a d a t a a l p h ad a t a b e t a d a t a i so k 2 3 进一步探讨 当然由于真正的数据库系统需要考虑的问题远远多于文中提到的方面，因而 上述函数也有很大的局限性，比如只能对于关键字来查找、更新以及删除；如果 想要对表中任意的字段进行操作，虽然理论上更加简单，但是无疑需要更多的操 作，而且当测试数据量不够多的时候仍然没有办法看出效率问题，但是当数据足 够多的时候，又需要考虑存储结构，以及内存外存间数据交换等具体的底层问题。 而本文的主要目的在于生成s q l 语言的语法分析器。所以对于具体的底层实现 就从简处理了。 不可否认的是，这样的简化处理虽然和实际有一定的差距，但是其内核结构 已经足以反映数据库系统的基本功能，并且通过合理地扩展可以有效地推广到更 复杂的结构。 对于复杂的结构，要考虑更细致，更复杂的问题，简要的做一个概念性的说 明如下： 第二章数据库中的数据存储 现实中的d b m s 系统还应该考虑如何有效的处理非常大量的数据。包括计 算机系统是如何存储和管理非常大量的数据的，用何种表示方式和数据结构是对 有效处理此类数据的最佳支持。因此相应的应该考虑到存储器的性能、价格，并 考察数据在主存储器与辅存储器乃至三级存储器之间移动的模式以及模式对于 涉及大量数据算法的效率。间断性读写错误的处理，以及造成数据不可读写的“磁 盘崩溃”的处理。更为详细和全面的内容可以参阅参考文献中相应的资料。 第三章l e x y a c c 应用介绍 第三章l e xy a c c 应用介绍 l e x 和y a c c 都是在2 0 世纪7 0 年代由贝尔实验室开发的 5 】。y a c c 的开发早 于l e x ，它是由s t e p h e n c j o h n s o n 开发的。为了与y a c c 一起工作，m i k e l e s k 和 e r i cs c h m i d t 开发了l e x 。自第7 版u n i x 以来，l e x 和y a c c 已经成为标准的u n 实用程序。自由软件基金会的g n u 工程组发布了b i s o n ，即y a c c 的替代品，b i s o n 是由r o b e r t c o r b e t t 和r i c h a r ds t a l h n a n 编写的【6 】。同样的在b s d 和g n u 工程组 还发布了f l e x ( 快速词法分析生成器，f a s tl e x i c a la n a l y z e rg e n e r a t o r ) ，f l e x 最 终是由j e f p o s k a n z e r 编写的，v e mp a x s o n 和v a nj a c o b s o n 又对它进行了重大的 改善【7 】。 。 但是无论如何，b i s o n 、f l e x 都是u n i x 操作系统下的开源软件，由于u n i x 系统的库函数和w i n d o w s 下的还是有所差别的，所以在w i n d o w s 下选择使用软 件p a r s e rg e n e r a t o r 来代替u n i x 下传统的y a c c 、l e x 软件，p a r s e rg e n e r a t o r 提供 了自己的l e x 、y a c c 实现，并且采用了相应的w i n d o w s 库函数，它不仅将l e x 和y a c c 集成到了一个编译系统环境中，而且还提供了对应的面向对象的词法分 析和语法分析的类，使得用户也可以根据需要生成相应的对象来进行词法、语法 分析。下面就介绍一下在w i n d o w s 操作系统中如何配置p a r s e rg e n e r a t o r t s 以便 其集成到v c + + 6 0 编程环境中，这样生成的“c + + ) 程序代码可以直接编译、连 接、执行，而且还可以利用v c - h 1 6 0 环境进行调试工作。 3 1 配置p a r s e rg e n e r a t o r 首先安装p a r s e r g e n e r a t o r 到计算机中的某个目录下，这里用”用户安装目录 、 为准，以后凡是碰到需要到相应安装目录下配置的时候都以”用户安装目录 开始。 安装完成后在”用户安装目录、，下生成的几个目录如下； b 吼 此目录下为可运行的y a c c 、l e x 编译器执行文件a l e x c 】【e 、a y a c c 懿e 以及p a r s e rg e n e r a t o r 的集成环境，可以直接在继承环境中调用a l e x 既e 和 a y a c c c ，【e 来完成从1 和y 文件生成c 文件的过程。 i n c l u d e 此目录下包含了p a r s e r g e n e r a t o r 需要用到的所有编译1 和y 文件 所需要用到的头文件，包含了a l e x 和a y a c c 所用到的所有内部函数，也包含了 第三章l e x y a c c 应用介绍 面向对象的y a c c 、l e x 类的声明。 l m 、 此目录下包含了3 个子目录( b o r l a n d m s d e v 、m s v c a ) 分别 对应了流行的c 十+ 语言编译器，为了使得p a r s e rg e n e r a t o r 可以集成于不同的c 编译环境，其中b o r l a n d 对应了相应的b o d a n dc _ h 编译器，m s d e v 对应了 v c 阡的编译环境，而m s v c 对应着其他的编译环境如g c c 等。 s o u r c e 此目录下为p a r s e rg e n e r a t o r 的源代码，因为在声明中p a r s e r g e n e r a t o r 的库函数和y a c c 、l e x 标准中定义的有一定的差距，所以在用p a r s e r g e n e r a t o r 生成词法、语法分析器的时候仍然需要不时地参考相应的函数原型。 然后在v c + + 6 0 环境中作如下配置 只需要在v 口斗6 0 环境中做一次就可以的配置 “工具”菜单、 选择”选项 目录”选项卡 在”显示目录为”下拉菜单中选 择 i n c l u d ef i l e s ”的路径中添加”用户安装目录玳c l u d e 同样在”显示目录为”下拉菜单中选择 l i b r a r yf i l e s ”的路径中添加”用户安装 目录l m 、m s d e 、p 最后在”显示目录为”下拉菜单中选择”8 0 u r o ef i l e s 的路径中添加”用户安装 目录s o u r c e ， 以上的配置只需在v c + + 6 0 环境中做一次即可，但后面的配置在每个y a c c 、 l e xt 程中都需要配置 在每个工程中选择”工程”菜单- ，设置”选项 ，卅， 选项卡 ”预处理程序定 义”后面加上”。y ) e b u g ”。 然后选择”s e t t i n gf o r 下拉选项中的 d e b u g 选项- 在 l i n k 选项卡- ，对象库 模块”后面加上”y t d 1 i b 最后选择然后选择”s e t t i n gf o r 下拉选项中的 r e l e a s e 选项- 在 l i n k 选项卡 - 、，对象、库模块”后面加上”y 1 1 i b 这样，一个y a c c 、l e xt 程就配置完成了，可以将用p a r s e rg e n e r a t o r 编译 生成的c 文件添加到工程当中，然后就可以应用v c - h 6 0 编译环境去编译、连 接，调试程序了。 3 2 使用l e x l e x 属于g n u 内部的工具，它通常都是g c c 的附带工具如果使用l i n u x 操作 系统，那么肯定系统本身就有l e x 和y a c e ，不过y a c c 的名字变成了b i s o n 9 ，而l e x 变成了f l e x 。l e x 可以通过一个输入文件，然后生成扫描器的c 源代码 分析正则表达式的方法是，从正则表达式到n f a ，再到d f a 1 0 ，应用l e x 第三章l c x y a c c 应用介绍 我们只需要把相应的正则表达式输入，然后l c x 就能够为我们自己生成d f a ，然后 生成源代码。 3 2 1 正则表达式 正则表达式的定义如下： 1 基本正则表达式由一个单字符o ( 其中口在正规字符的字母表乞中) ，以 及元字符占或元字符组成。在第1 种情况下，工 ) 2 缸) ；在第2 种情况下， 工 ) 2 p ) ；在第3 种情况下，三( 妒) 2 。 2 7 1 5 格式的表达式：其中，和j 均是正则表达式。在这种情况下， l ( r i j ) = l ( r ) u o ) 。 3 i s 格式的表达式：其中，和j 是正则表达式。在这种情况下， 以r s ) = 工( r ) o ) 4 r 格式的表达式：其中，是正则表达式。在这种情况下，l ( r + ) 2 工( r ) 。 5 ( ，) 格式的表达式：其中r 是正则表达式。在这种情况下，l ( ( ，) ) 2 三( ，) ， 因此，括号并不改变语言，它们只调整运算的优先权。 对于将正则表达式转换成相应的n f a 方法如下： 对于基本的正则表达式如图3 - 1 所示： 图3 - 1 基本正则表达式到d f a 对于正则表达式中选择7 i s 、连接憎、重复一的d f a 表达分别示于图3 - 2 第三章l e xy a c c 应用介绍 3 2 2l e x 程序格式 图3 - 2 选择、连接、重复到d f a 事实上，在l e x 中书写正则表达式相当方便，因为l e x 的规范中为用户定义 了书写正则表达式所有常用的符号，并且还增加了许多可以提高效率的符号d 1 。 具体含义如表3 1 所示： 表3 - 1l e x 中应用的符号 匹配除换行符( 、n ，) 外的任何单个字符 匹配前面表达式的零个或多个拷贝 口匹配方括号中的任意字符的字符类。除了识别以v 开始的转义序列 外，其他的字符在方括号中没有特殊的含义。 作为正则表达式的第一个字符匹配行的开头。 也可用于方括号中的否定。 $作为正则表达式的最后一个字符匹配行的结尾 )当括号中包含一个或2 个数字时，表示前面模式被允许匹配的次数 |用于转移元字符 + 匹配前面的正则表达式的一次或多次出现 ?匹配前面的正则表达式的零次或一次出现 i 匹配前面的或后面的正则表达式 引号中的字符除转义外均解释成字面意义 第三章i , e xy a e e 应用介绍 只有在其后跟有制定的正则表达式时才匹配前面的正则表达式 0将一系列正则表达式组成一个新的正则表达式 3 2 3 实例说明 以下实例说明生成实数的表达式规则： d i g i t _ 0 12 l3 1 4 1 5 1 6 1 7 1 8 1 9 u n s i g n e d i n t e g e r - - d i g i td i g i t u n s i g n e d n u m b e r u n s i g n e d i n t e g e r ( ( u n s i g n e d i n t e g e r ) i 占) ( ( ( eid ( + 1 _ ls n s i g n e z i n t e g e r ) i 占) n u m b e r 一( + i - ) u n s i g n e d n u m b e r 如果用l e x 来书写正则表达式则可以用如下式子来描述： - ? ( ( o 一9 卜) l ( 【o 一9 】o - 9 】+ ) ( b e 】 _ + 】? o 一9 】+ ) ? ) 最后再来看看l e x 文件的组织结构，l e x 源程序一般的格式是： 辅助定义部分 识别规则部分) 用户子程序部分) 辅助定义部分的内容最终拷贝到生成c 程序的代码中。可以在此包含后来文 件中代码所必需包含的头文件。 识别规则部分是l e x 词法分析中的主要部分，每行的左部为正则表达式，右 部为当分析出相应的正则表达式时词法分析程序所进行的相应操作。 用户子程序部分为用户所需的函数的实现，一般定义了错误处理函数，以及 对于l e x 标准库函数的重载。当然如果生成的词法分析器须要单独使用的话还应 该有自己的m a i n 函数。 ， 下面的例子分析输入，当输入包含数字时，输出n u m b e r ，其余的情况( 字符 或其它符号) 输出本身。 c _ l e x i x n t 】； 一? ( ( 【o 一9 】+ ) 1 ( o - 9 扎【0 - 9 】+ ) ( c e 】 斗】? o - 9 】+ ) ? ) p r i n t 坟”n u m b e r n ”) ；) e c h o ； m a i n 0 第三章l e x y a c c 应用介绍 y y l e x 0 ； 3 3 使用y a c c l 廖【可以很好的分析正则文法，但是对于含有递归的上下文无关文法却无能 为力【1 2 】；要分析作为程序设计语言的主要文法结构上下文无关文法，需要用到 语法分析器y a e c 。 3 3 4 自底向上语法分析 语法分析是程序语言实现过程中最关键的部分，可以采用自顶向下的l u l ) 分析，也可以采用自底向上的l r ( 0 ) 分析。这里用到的y a c c 采用的是自底向上 的分析方法，但是区别于基本的l r ( 0 ) 分析，它所采用的是l a l r ( 1 ) 分析算法【1 3 】。 本文的重点是介绍与y a e e 相关的自底向上的分析方法。 与自顶向下从语法树根推导文法不同的是，自底向上的分析方法是从树的叶 子节点开始，逐步向上的分析，一般使用显式的栈来帮助完成分析的。分析栈包 括记号和非终结符，分析开始的时候还包含了开始符号。 分析程序有两种可能的动作： l 将终结符从输入的开头移进到栈的顶部。( s h i t s ) 2 如果有b n f 选择彳专口，则将栈顶部的串口归约为非终结符a 。( r e d u c e ) 所以自底向上的分析方法又叫做移进归约( s h i f t - r e d u c e ) 分析方法。 下面文法可以分析成对的括号，由于用到递归解决括号的嵌套，所以正则表达 式对此文法无能为力。 s _ s s 一( s ) s i s 表3 2 为自底向上分析输入( ) 的操作流程： 表3 - 2 分析( ) 流程 分析栈输入动作 ls 0 5 移进 2 $ f1 $用s 一占归约 3 $ ( s1 $移进 4 $ ( s ) $ 用s 专占归约 5 $ ( s ) s $用s 一( s ) s 归约 第三章l c xy a i c c 应用介绍 l 6 s s s 用s 专s 归约 l 7 s s s 接受 首先将其分成各个项目： s s s - s s 扣( s ) s s ( s ) s s ( s ) s s _ ( 研s s 一( s ) j 书 其中为分隔符，s 一对应s 斗占生成规则。 分析中决定移进与归约的准则如下： 如果有项目a 专口，并且，以符号工开始，其中x 可以是记号或者终结 符，那么有以下两种情况的转移： l 如果石是记号，那么转换与z 的一个在分析中从输入到栈顶部的移进相对 应。 2 如果石是非终结符，转换仍然与在分析时将x 压入栈中的动作对应，但是 它只发生在由产生式石_ 形成的归约时。 用n f a 的转移表示如图3 3 ： 图3 3 n f a 转移 这样就可以生成文法的n f a ，然后在根据n f a 生成d f a 进而分析文法接受 的语言。 对于上例的d f a 如图3 - 4 ： 第三章l e x y a c c 应用介绍 图3 - 4 d f a 如果以上的规则产生的d f a 不会产生歧义，那么此文法就是l r ( 0 ) 文法。但 是考虑一下两种情况的歧义： 1 如果d f a 中的某个状态包含了一斗和4 哼口五( x 为一个终结符) ， 会出现一个到底是执行前一个动作归约还是执行后一个动作移进的冲 突，这就是移进归约冲突( s h i f i - r o d u c e ) 。 2 如果d f a 中的某个状态包含了4 _ 舶和占一，会出现到底用前一个 归约还是用后一个归约的歧义，这就是归约归约冲突( r e c l u e - r e d u c e ) 。 可见l r ( 0 ) 的识别能力不是很强，但是可以无需先行读字符即可完成l r ( 0 ) 文法的分析。 一 s l r ( 1 ) 为简单的l r ( 1 ) 分析，相对l r ( 0 ) ，由于加入一个先行，所以功能更 强大些，相应的动作如下： 1 对于在s 中的任何项目a 寸口爿，当x 是一个终结符，且x 在 f d l o w ( x ) 中时，并且s 中没有完整的项目曰专p 。移入操作。 2 对于在s 中的任何两个完整项目彳一伽和占寸。， f o l l o w ( a ) n f o l l o w ( b ) 2 。相应的归约操作。 满足上述两点的即为s l r ( 1 ) 文法1 1 4 。 l r ( 1 ) 分析虽然是功能强大的最一般的格式，但是它也复杂的多。实际上在 大多数情况下，一般的l r ( 1 ) 分析太过复杂以至于不能震大多数情况下的分析构 造程序中使用，l a l r ( 1 ) 在保留了l r ( 1 ) 分析的大多榭减外还保留了l r ( 0 ) 分析 的简单有效性。所以y a c c 语法分析程序生成器选择了应用l a l r ( 1 ) 分析方法。 除了包含l r ( 0 ) ，s l r ( 1 ) 中的项以外，l a l r ( 1 ) 构造的d f a 中的每个状态的 项中还包含了一个先行符号，这一点和l r ( 1 ) 分析相同。 第三章l e xy a c c 应用介绍 除了满足l r ( 1 ) 的 1 如有l r ( 1 ) 项目陋斗口研，4 】，其中x 是任意符号，那么z 就有一个到 项目【4 _ 口爿 4 j 的转换。 2 如有l r ( 1 ) 项目阻b y , a ，其中b 是非终结符，那么对于每个产生 式曰_ 卢和f f 珊f ( y 中的每个记号6 都有到项目陋十声，胡的占转换。 l a l r ( 1 ) 还作了如下的变动以使得产生的d f a 状态较少，且仍然能保留大 部分l r ( 1 ) 分析的优势： 1 l r ( 1 ) 项目的d f a 状态核心是l r ( 0 ) 项目d f a 的一个状态。 2 若具有相同核心的l r ( 1 ) 项目的d f a 的两个状态 和屯，那么如果符号 x 上有一个从到的转换，那么在x 上就还有一个从是到f 2 的转换， 且和f 2 具有相同的核心。 这样