（计算机科学与技术专业论文）数据库引擎sql编译器的研究.pdf

武汉理1 = 大学硕十学位论文 摘要 当今世界每天产生海量的信息，这么多的信息通过各种方式在全世界范围 内进行传播。作为个人或企业都会接触到大量的数据信息，要管理和操纵这些 数据信息，数据库就是必不可少的工具，其中数据库管理系统( d a t a b a s e m a n a g e n l e i l ts y s t e m ) 简称d b m s 是这个系统的核心。它既能保证数据库的安全 性和完整性，又能对数据库进行全面的操纵和管理。d b m s 主要提供的功能有 长久的存储、编程接口、事务管理等。要实现这些功能数据库引擎至关重要， 它是用于存储、处理和保护数据的核心服务。 本文以s q l 语言预编译器的构建为基础，包括从编译原理的相关知识出发， 再到词法分析程序和语法分析程序，最后到代码产生和优化，把整个编译过程 和对s q l 语言的处理进行了详细的阐述。系统中的s q l 语言是标准语言，它是一 种高级的非过程化编程语言，用户能够应用它在较高级别的基础上进行工作， 也不用制定对数据库的存储方式。 本文首先阐述了编译过程的各个阶段及其相关知识，包括：正则表达式、 有限自动机、上下文无关文法、l a l r ( 1 ) 文法等。然后对几个主要的编译阶段和 过程以本系统构建的方法为基础进行了详实的介绍，其中有如何利用l e x 和 y a c c 工具生成词法分析程序和语法分析程序，并给出了它们在s q l 语言编译 器实现过程中的具体应用。再对s q l 预编译器构建的方法和相关技术路线做了 详细的说明。 s o l 预编译器的整体设计思想是先由l e x 词法生成工具构建出词法分析 器，然后再由y a c c 语法生成工具构建出语法分析器，这两个分析器作为整个 编译系统的核心。再由虚拟机作为中问环节，最后由b - t r e e 和缓冲区模块构成 后部，再加上操作系统提供a p i 接口，这样就共同组成实现了s q l 预编译器。 关键词：l e x 、y a c c 、编译器、s q l 、虚拟机、l a l r ( 1 ) a b s t r a c t i nm ew o r l dp r o d u c ea1 弼e 锄o u i l to fi n f o 册a t i o ne v e 巧d a y ，s ot os p r e a d i n f o r m a t i o nw o r l d w i d ew i t hav a r i t e t yo fw a y s a sa 1 1i n d i v i d u a lo rb u s i n e s sw i l lb e e x p o s e dt o 锄o u n t so fd a t ai n f 0 锄a t i o n ，t h ed a t a b a s e i sa 1 1e s s e n t i a lt o o lw h l c h d a t a b a s em a i l a g e m e n ts y s t 锄r e 胁e dt oa sd b m s i st h ec o r eo ft h es y s t 铋，t l l e i lt o m a n a g ea 1 1 dm a n i p u l a t et h e s ed a t a i tc a nn o to n l ye i l s u r et h es a f e t y 锄d i n t e 嘶t yo f t h ed a t a b a s e ，b u ta l s oac o m p r e h e n s i v ed a t ；l b a s et om a n i p u l a t ea n dm a j l a g e d b m s c a l lp r o v i d et h el o n 哥t e ms t o r a g e ，p r o 黟锄m i n gi n t 曲c e s ，t r a n s a c n o nm a i l a g e m e i l t d a t a b a s ee n 西n ei s e s s e n t i a lf o ri m p l e n l e n tt h e 劬c t i o i l ，i ti s u s e df o rs t o r a g e ， p r o c e s s i n g 觚dp r o t e c t i o no f d a t ai nc o r es e r v i c e s i i lt h i sm e s i s ，as m a l ld a t a b a s em a n a g 锄e n ts y s t e ms q ll a n g u a g ep r e c o m p l l e r c o n s t l l l c t i o nc s t a b l i s hi nt h e 、斩n d o w se n v i r 0 舯e n t f i r s tb e 百n 矗o mc o m p i l e rt h e o i n c l u d i n gk n o w l e d g e ，t ot h el e x i c a ja l l a l y z e r sa i l dp a r s a n df i n a l l y c o d eg e l l e r a t l o n a n do p t i m i z a t i o n ，t h ec o m p i l a t i o na n dp r o c e s s i n go ft h es q ll a n g u a g ei nd c t a i l h 1 t h es v s t 锄t h es q l1 a n g u a g ei ss t a l l d a r dl a i l g u a g e ，i ti sah i 曲一l e v e ln o n p r o c e d u r a l p r o 黟a m m i n gl a l l g i l a g e ，u s e r sc 瓯u s ei t i nt h eh i 曲- l e v e lw o r k ，w o u l dn o h a v e d e v e l o p e dm ed a t a b a s es t o r a g em e t h o d s ，b u ta l s od on o tu n d 耐锄dt h es p e c m c s t o r a g ew a y t h i st h 商sd e s c 曲e dt h ev a r i o u ss t a g e so ft h ec o m p i l a t i o np r o c e s s 柚dr e l a t e d k n o w l e d g e ，i n c l u d i n g ：r e g u l a re x p r e s s i o n s ，f i n i t ea u t o m a t a ，c o n t e x t 。缸优铲卸m a r s ， l a l r ( 1 ) g 阳m m a ra n d s oo n 1 1 1 e no nm em a i ns t a g ea i l dm ec o m p i l a t l o np r o c e s s t o b u i l dm es y s l 【觚sa p p r o a c ha st h eb a s i sf o ra d e t a i l e dd e s 谢p t i o n ，i n c l u d i n gt l l eu s eo f l e xa 1 1 dy a c ct o o lt og e n e r a t el e x i c a la n a l y z e r s a 1 1 dp a r s a n dg i v e st h 锄t h es q l l a l l g u a g ec o m p i l e rd e v i c et oa 幽e v e as p e c i f i c 印p l i c a t i o np r o c e s s s q lp r e 。c o m p i l e r a n dn l e nb u i l do nt h em e t h o d sa i l d r e l a t e dt e c l l l l 0 1 0 酉e sm a d ead e t a i l e dr o u t e d e s c p t i o n s q lp r e c o m p i l e ro ft h ew h o l ei d e ai s t oi n i t i a l l yb u i l dag e n e r a t i o nt o o ll e x - l e x i c a la i l a l y z a n d 也e nb ym ey a c c 酉锄m a rp a r s e rg e n e r a t i o nt o o l st ob u i l do u t n l e s e 伽op a n s 弱t h e 矗o n d ，t h e nt h ev i 咖a lm a c _ h i n ea sa ni n t e n n e d i a t ei l n k ， p l a y i n gac o n n e c t i n gr 0 1 e ，锄df i n a l l yb a c k e n dc o n s t m c t e db yt h eb - t r e e 锄d b u 矗e r i i 武汉理。r ：人学硕士学位论文 m o d u l e s ，t o g e t h e rw i t ht h eo p e r a t i n gs y s t 锄t op r o v i d ea p ii n t e r f a c e ，s om a tt o g e m e r c o n s t i t u t et h ei m p l e n l e n t a t i o no ft h es q l p r e - c o m p i l k e y w o r d ： l e x 、y a c c 、s q l 、c o m p l i e r 、v i r t u a lm a c h i n e 、l a l r ( 1 ) j l l 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得武汉理工大学和其它教育机构的学位和证书而使用过的材 料。与我一同工作的同志对本研究所作的任何贡献均已在论文中作 了明确的说明并表示了感谢。 豁埠晰斟 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留交向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位 论文的全部内容编入有关数据库进行检索，可以采用影印、缩印或 其他复制手段保存或汇编本学位论文。同时授权经武汉理工大学认 可的国家有关机构或论文数据库使用或收录本学位论文，并向社会 公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) c 捌：邻靳c 矧：拗蓐呲 武汉理j ：人学硕七学位论文 第1 章绪论 1 1 数据库系统的发展 当今世界每天都会产生海量的信息，这些信息会通过各种途径在全界范围 内进行传播，不管是个人或企业都会接收到大量的信息，特别是对于商业机构 在它们日常的商业活动中会收集到大量的数据和信息，它们需要记录客户和产 品供应商的详细信息，还需要保存已经出售的商品和存货的信息等。绝大多数 公司都会将这些必不可少的数据存放到数据库中，随着数据库技术的不断发展 对数据的管理从原来单一的数据管理到现在以数据库管理系统为核心进行管 理。这一系统是和操作系统复杂度相当的一种软件系统，它们将数据以一种比 较合理的数据结构形式保存起来，并提供一系列能够读取和修改数据的操作方 法。 最早期出现的数据库管理系统是在上个世纪六十年代后期，i b m 公司首先 研制出的i m s ( i n f o 彻a t i o nm a l l a g e m e l l ts y s t e m ) 系统作为其代表，以层次数据 模型为基础的数据库管理系统，其最显著的特征是采用层次和网状结构。在这 个时期涌现出来的其它数据库系统也都具有某些共同特征【l 】： ( 1 ) 对数据库的三级模式体系结构进行了很好的支持，三级模式结构是指 模式、内模式和外模式，并且它们之间可以进行相互的转换，例如：模式与内 模式，外模式与内模式等。这就保证了数据库系统中数据和程序在物理存储上 的独立性并且具有一定程度逻辑上的独立性。 ( 2 ) 层次和网状数据库系统具有自己的数据定义语言，可以用来描述数据 库的三级模式以及相互的映象。 ( 3 ) 在系统中除了保存必须的数据外，还需要保存数据与数据之问的某种 关联。在层次和网状数据库系统中是用存取的路径轨迹来表示和实现数据之间 的联系。 ( 4 ) 在对层次和网状数据库系统进行数据查询和操纵的时候，都是每次一 个记录并按照一定的方向利用过程化语言来对其进行操作，它们通常是依附于 一种高级语言来实现的。 随着数据库理论和技术的不断发展，到了上世纪七十年代l b m 研究员 武汉理工大学硕士学位论文 e f c o d d 开创性的提出了一种新的数据库模型关系数据库模型，对关系数 据库的方法和理论进行了研究，为后来人们建立这种结构模型的系统提供了理 论基础，这种方式具有的特点所带来的好处是显而易见的。 ( 1 ) 把整个现实世界中的事物都看成是实体，那么所有的事物与事物之间 的联系转变成实体与实体之间的关系，在这种关系模型中数据的逻辑结构就是 一张二维表。 ( 2 ) 以操作集合的方式来对这种关系模型进行操作，有关系代数、关系演 算、s q l 语言等。实体对象和实体结构都是以这种方式存在，这种操作方式是 与非关系模型的操作方式相对应的。 ( 3 ) 对这种关系模型进行的操纵语言也是一种高度的非过程化语言，用户 可以在非常便利的条件下完成对数据的操作。 ( 4 ) 这种模型中用户是根本不清楚数据的物理存储方式的，用户只需要知 道应该如何来操作其中的数据就可以了，而根本不必详细的了解这些数据在数 据库中是如何被存储的。 由于有了关系数据模型对数据库技术发展的强有力推动，现在需要构建更 先进的数据模型时要从以下几个方面加以考虑。 ( 1 ) 这种数据模型需要有更丰富的对象结构和更多种类的操作规则，最好 是能够把数据、对象和管理融为一个整体。 ( 2 ) 这种数据模型同时需要对数据库标准语言和标准网络协议具有更加良 好的支持，也应该具备良好的可扩展性和互联特性。 1 2 数据库系统主要功能 对于所产生的大量信息需要进行有效的组织和管理才能够加以利用和服务 于我们的日常工作。现代的数据库管理系统能够提供非常丰富和完善的功能来 为我们服务，其中主要的功能有： ( 1 ) 提供对数据的管理。现代的数据库管理系统能够在数据库中存储各种 不同类型的数据，有数值型数据也有非数值型数据。同时具有建立和删除数据 库：创建表和对数据进行的基本操作等。它把对整个数据库的操作都揽括其中， 并且是独立于任何处理程序之外而存在的。还能够实现数据共享并且能对数据 进行高效率的存取。 ( 2 ) 可以进行数据的查找。用户可以利用非常有效的查询算法来灵活的处 2 武汉理工人学硕+ 学位论文 理所需要查找的信息。同时用户可以通过使用标准结构化查询语言来对数据库 中的数据进行查询、修改、删除、添加等基本操作。这些操作结果都会被记录 在磁盘之上，以便往后如果有需要可以很方便的查找。 ( 3 ) 进行事务管理。不同用户能够实现对数据库中的数据共享，这是所有 数据库都应该具备的一个重要的特征。它的实现是必须在满足对数据库的并发 操作基础之上，并以此来满足对数据的完整性要求。同时以锁定形式来实现对 事务的处理，但每次操作后都需要记录下操作f 1 志，这样便于作为日后操作的 依据。 1 3 本文主要内容 由于大型数据库管理系统功能过于强大，在某些系统中需要利用小型数据 库管理系统来进行必要的数据管理。在此背景下，以编译原理为理论基础应用 词法分析和语法分析生成工具，构建小型数据库管理系统所需要的s q l 语言预 编译器，以此作为本研究课题的基础。数据库管理系统具有众多功能，但最主 要的功能还是对数据库中的数据进行管理，这就必然涉及到数据库的操纵语言 s q l 语言。s q l 语言是i b m 公司开发的一种专门用来对数据库进行操纵的 语言，它具有丰富的功能和简练的语言等特点，在数据库领域的应用非常的广 泛。随着技术的成熟和不断对其进行扩充和修改，现在s q l 语言已经发展成为 在关系数据库领域中的一种标准语言。与此同时，专门负责对s q l 语句进行翻 译、解释和执行的部件就是非常重要的部件，如何建构这个部件就是本文的主 要内容。为小型关系数据库系统开发相应的s q l 语言预编译器就是本文主要研 究和讨论的重点。 3 武汉理工人学硕十学位论文 2 1 编译原理 第2 章编译原理简述 我们用任何高级语言所开发的程序都必须经过编译后才能够被计算机所识 别和执行，在这一过程当中起到关键作用的就是我们常说的编译器。编译程序 是一种非常复杂的底层程序，它负责把用高级语言编写的程序翻译成计算机能 够识别的程序。对于输入的源程序代码，编译程序通过一系列的转译操作把源 程序转换成某种语言编写的目标程序。一般情况，源代码程序是用高级语言所 编写的，被大家所熟知的高级语言有c c h 、p a s c a l 、p 鲥、b a s i c 等，而目标 代码是计算机能够识别的代码。这一过程如图2 1 所示。 源程序目标代码 图2 一l 编译过程 通常人们对自然语言的翻译都需要经过这样几个主要阶段：识别单词、识 别句子、理解句子意思、翻译成母语并对译文进行适当的重组让它们能够比较 符合母语的表达方式。同样，编译器在对用高级语言编写的程序进行翻译时也 需要经过这样几个阶段：首先进行词法分析，识别出合法的单词；再进行语法 分析，得到由单词组成的句子结构；然后进行语义分析，生成代码和优化代码； 最后生成目标程序。下面简述各个阶段的功能： ( 1 ) 词法分析 词法分析过程是根据词法编写规则，而识别出源程序中的各个标记，每个 能够被识别出的标记代表一类单词。源程序中常见的标记可以归为以下几大类。 1 ) 关键字：它们是系统原本就已经定义好了的标记被包含在系统当中，一 般情况下是不能够被修改的也被称为保留字。 2 ) 标识符：它们是按照一定的组词规则构成的，在源程序代码中被用来表 示变量名、过程名、类型名和标号等，是源代码中所有对象的名称。 3 ) 字面量：一般表示一种常量，它们也可以被细分为数字字面量或字符串 字面量等。 4 武汉理t 大学硕十学位论文 4 ) 特殊符号：这些比较特殊的字符，在源程序代码中均有特定含义，根据 不同的作用被细分为运算符、分隔符等。 ( 2 ) 语法分析 语法分析过程是根据词法分析器识别出输入的字符流中的单词，再构造出 一棵能够正确反映该结构的语法树。语法树的建立是语法分析的结果是语法分 析中的关键步骤。大多数情况下采用二叉树结构的形式来表示语法树，由于二 叉树所具有的特性使得任何形态的树都可以转换成为这种结构。 ( 3 ) 语义分析 语义分析是根据语言含义对语法树中的语法单元进行静态语义检查，比如 进行类型检查或转换等。其主要目的在于保证语法的正确结构和语义的合法性。 在进行语句声明分析时，语义分析器将相应的语言环境信息记录在符号表中以 便在之后对语句的操作中使用。后面的操作需要根据符号表中的信息判断各种 操作数是否合法，以此来判断之前的操作是否正确。 ( 4 ) 中间代码生成 语义分析过程输出结果进入到中间代码生成器中产生中问代码。中间代码 可以有很多种形式，其中所具有的共同特点就是与具体机器的无关性。在这些 形式中最常用的一种是三地址码，它是采用四元式的方式来实现的。这种结构 的最大好处在于方便阅读和优化。在中间代码生成以前的各阶段对于解释器和 编译器都是完全一样的，都需要经过上述几个过程。语义分析完成后语法树就 形成了，这时执行编译的基本元素就已经具备，并可以直接形成计算步骤进行 计算。 ( 5 ) 代码优化 编译过程中的一个重要阶段就是进行中间代码的优化，由于编译器是按照 某种编译文法将源程序翻译成中间代码，这些转换过程都是通过已有的成熟方 法进行的。由于在生成中间代码形式的过程中会产生不必要的结果，进而会影 响编译的整体效率，如果想得到更加高效的目标代码，就必须对翻译出来的结 果进行优化。在中间代码生成阶段和目标代码生成阶段都可以进行优化。这个 阶段的代码也是和机器没有关系的。因此，在中间代码这个层次进行优化可以 避开与硬件有关的干扰，大部分的优化工作可以在目标代码生成之前进行，少 部分与硬件有关的优化工作可以在目标代码生成时进行。 ( 6 ) 目标代码生成 5 武汉理：r 大学硕士学位论文 编译过程的最后阶段是生成目标代码。在这一过程中需要综合考虑到计算 机各方面的因素，例如：体系结构的设计、指令系统性能的分析、寄存器的分 配以及内存的组织等。最后编译器生成的目标程序代码也有几种形式【4 】。 1 ) 汇编语言形式，编译器生成以汇编语言形式表达的代码序列。 2 ) 二进制代码形式，这种二进制代码不是一般意义上的二进制代码，而是 能够进行再次定位的二进制代码，它以模块的形式被编译器所使用。 3 ) 内存形式，编译器生成的代码序列被直接装入到原编译器所在地址并且 能够很快的被执行。 以上编译过程的各阶段划分是最典型的处理模式，但是并非所有的编译程 序都必须进行这样的划分或者包含上述所有阶段。不过，大多数实际使用的编 译程序都是采用上述几个阶段的工作过程。 2 2 编译器的构建及相关概念 在计算机发展初期，人们都是利用机器语言进行编译程序的编写工作，后 来发展到利用汇编语言编写程序，但是这些编写方法的效率都非常低下而且也 不容易被实现。因此，现在普遍使用的方法是利用通用程序设计语言来编写编 译程序，比如c c + + 语言就非常适合编译器的编写工作。通过高级语言开发编 译器其编写和执行效率都要比汇编语言和机器语言高很多，不过，现在这种方 法也已经不能满足编译器程序设计的需求了。为此，需要利用一些专用工具来 对编译器部件进行自动生成。大家所熟知的就有词法分析生成器和语法分析生 成器，另外还有语法翻译工具，自动代码生成器和数据流工具等。这些工具的 共同特点是，仅需要对语言相应部分的特征进行描述，而把算法的实现过程隐 藏起来。同时生成的部分可以并入到编译器的其它部分中去，通常这些工具会 和一种程序设计语言联系在一起使用。 此外编译器还具有些比较重要的概念： ( 1 ) 编译和解释，编译方式就是把用某种高级语言编写的程序翻译成等价 的可执行目标程序。解释方式就是直接对源代码程序的每个语言部分进行解释 执行。两者之间的根本不同在于编译方式将源程序编译成立刻执行的目标程序， 并可以直接执行此目标程序。 ( 2 ) 分析和综合，对于编译过程的各个阶段逻辑上可以把它们划分为两大 部分，即分析部分和综合部分。从词法分析到中间代码生成各阶段的工作称为 6 武汉理工大学硕七学位论文 分析，而以后直到目标代码生成各阶段的工作被称为综合。中间代码起到了上 下两部分的衔接作用，由于中间代码是与机器无关的，因此它把编译器分成了 与硬件有关和无关这两部分，从而提高了编译器整体开发和维护的效率。 ( 3 ) 遍，编译器的每个阶段都是对以某种形式表示的代码进行扫描分析。 把每个阶段的程序完整分析一遍的工作模式称为一遍扫描。但这只是逻辑上进 行的工作。如果需要进行多次扫描，就必须要用到非常大的存储空间来存放中 间代码，这必然会增加一些多余的i o 操作。因此，编译器通常是把几个阶段 的工作整合起来，进行一遍扫描，从而减少对程序的扫描遍数。要完成这个工 作必须做到两点【4 】： 1 ) 需要为编译器的运行提供足够大的空间。以此来满足各阶段的工作处理 程序能够随时准备运行，并且各阶段所需的信息也要同时放在内存当中。 2 ) 尽可能地减少扫描遍数。在语言设计和编译技术上做工作特别是利用编 译技术，尽量使得编译器可以仅从己扫描的内容中就能够得到足够的信息。 2 3 编译器发展的历史 计算机在产生之初是没有编译系统来进行代码的翻译执行的。当时人们所 编写的程序都是由机器码所组成，这些代码虽然能够很快速的在计算机里被执 行，但是它的编写和维护工作是非常繁重的，所以导致整体的工作效率非常的 低下。人们希望软件开发方式能够像利用自然语言那样来进行描述，这样既能 提高软件开发的效率同时也能够把软件开发技术普及开来。但由于当时人们对 编译原理知识的掌握有限，所以开发工作非常复杂和艰苦。在这种情况下，i b m 公司还是于上世纪五十年代研制出f o r t r a n 编程语言及其编译器。于此同时， 人们对自然语言结构的研究也有了很大的进展，使得编译器结构得以简化，甚 至还带有些自动化，并逐步形成了现在的结构。即包括了文法的四个层次【5 】：o 型文法、1 型文法、2 型文法和3 型文法。且其中的每一个都是其前面的特殊情 况。其中2 型文法被证明是程序设计语言中最有用的而且已经成为一种标准。 到了上世纪六七十年代，人们把注意力放在了分析问题的研究上，现在它 已经成为编译过程中的必要环节。与上下文无关文法紧密相关的有限自动机和 正则表达式的概念也得到了发展。并且引出了表示程序设计语言中单词的符号 方式，同时也深化了生成有效的目标代码的过程，这个时期形成了编译器的基 本组成结构并被延用至今。 7 武汉理r 大学硕十学位论文 进入到二十世纪后期，人们把研究重点都放到了编译器部件的自动生成上， 这其中就包括了代码生成，这些尝试并未取得太大进展。但是在编译器设计方 面还是取得了一定的进展，包括复杂算法的应用这使程序能够推断或简化其中 的信息，同时更加注重基于窗口的交互开发环境，比如：编辑器、连接程序、 调试程序以及项目管理程序等。但必须提到的是基本的编译器原理在近2 0 年中 都没有太大的改变，这也是人们需要继续研究的一个方向。 武汉理1 = 人学硕十学位论文 第3 章 s q l 预编译器组成 3 1s q l 预编译器简述 数据库管理系统在对存储其中的数据进行管理和操作的过程中，离不丌一 个基础核心就是利用标准s q l 语言编写的描述语句对数据进行基本的操作。通 常这一过程是在用主程序编译器进行程序编译之前，就对带有s q l 语句的源程 序代码进行预处理，转换成主程序语言能够处理的代码。再利用主程序编译器 生成目标代码，最后产生可执行代码，整个过程叫做s q l 语言预处理过程。 预编译的工作过程是首先扫描带有s q l 语句的初始程序代码，把其中含有 s q l 语句部分的程序编译成主程序对数据库操作的函数调用语句，并产生相对 应的程序文本生成语法树。这些工作主要是由三个阶段来完成：词法分析过程、 语法分析过程和代码生成过程。即第一步是对源程序语句进行词法分。词法分 析器将含有的s q l 语句的程序解析成一系列独立的单词，这一系列单独存在的 单词可以是含有特定意义的字符或字符序列，每个词都有其所属的类别，词的 类别是一个数字标识以表明这个词是什么含义。然后利用语法分析生成工具按 照工具内定义的语法规则将一系列词汇组织成层次结构的语法树。一旦语句经 过解析和分析后，语法树就作为一种结果会传送给代码生成器。最后，由代码 生成器根据语法分析树生成虚拟机程序。这棵树中的的每一部分生成一个虚拟 机指令序列来完成特定的任务，同时还会生成代码和进行查询优化。 3 2s q l 预编译器结构 为此开发的系统s q l a n a l y z e r 是模块化的结构组成，具有方便、灵活和小 巧等特征。并采用了一些比较独特的方法来对此小型关系数据库进行管理。它 主要是由于八个独立的程序模块组成。如图3 1 所示，这个模型将整个的s q l 语言预处理过程划分为几个不同的任务阶段，就和企业的工作生产线一样，按 照一定的顺序和规则执行。首先执行这个结构体中的预编译查询s q l 语句阶段， 然后在结构体中执行具体的语句翻译处理过程，最后在底部由操作系统的接口 执行相关的存储和管理操作。 9 武汉理工人学硕士学位论文 3 2 1 数据库接口 图3 一ls q l 编译器结构 一般情况下，对于不同软件供应商所提供的关系数据库软件来说这些数据 库都有它们特殊的结构和提供给应用程序调用的接口。这必然会导致不同厂商 所提供的数据库的结构各不相同，那么要能够很好的理解这些结构对程序员来 说不是一件容易的事情。在这一背景下，要开发可以使用任何一种公司提供的 关系数据库的应用程序，就需要一种通用的编程方法。现在这种方法被称为开 放式数据库连接( o d b c o p e nd a t a b a s ec o 彻e c t i v i t y ) i l j oo d b c 为使用不同 的关系数据库提供了一个统一的程序设计接口。 要想能够充分利用o d b c 管理器的首要任务就是要对已有的多数据源进行 配置。数据源是用来告诉用户程序在什么地方能够找到所需要的数据库物理文 l o 武汉理= 大学硕士学位论文 件，以及使用那一种o d b c 驱动程序来解释a p i 的调用。可以通过动态的方法 来配置o d b c 数据源，即在程序内部根据程序安装的环境由程序本身自行配置 程序与数据库的连接。 通过o d b c 实现对数据库的访问，如果数据库是在服务器端而访问程序是 在客户端，那么就可以很便捷的开发出c s 结构的数据库应用服务程序，这种 程序能够满足很多现实的需求。另一方面，随着计算机技术的不断发展，三层 或更多层体系结构也开始提出并应用在具体的实例中。 但是由于不同软件公司提供的产品的服务对象不同，它们各自数据库的功 能也不相同。由于这种接口的设计是为了满足大多数数据库的要求，具有大众 化和通用性。在这种情况下，就不可能完全实现所有的数据库操作功能，从而 影响到人们对数据库的操作，最终导致数据库的使用效率低下。所以，为了解 决以上问题，本系统中接口由c 语言编程的a p i 函数组成，也就是说不管是程 序、脚本语言或是其它文件，最终都是通过它与系统进行交互。很明显这些a p i 函数可以尽可能地发挥出数据库的功能，能够方便的实现对数据库的操作，以 减少数据库的操作时间。 3 2 2s q l 语句处理 数据库管理系统对数据进行基本操作时，其主要的方式就是通过s q l 语句 来进行的，那么对s q l 语句的处理就显得格外重要了。在对主程序中s q l 语句 进行处理时，其编译处理过程首先从词法分析阶段开始，然后进入到语法分析 阶段。这两个处理过程相互配合，共同完成处理文本形式的结构化查询语句， 并分析语法正确与否，然后转化为让下一步更方便处理的数据结构语法树。 最后把语法树传送给代码生成器进行处理。本系统预处理过程中的词法分析器 是由词法分析自动生成工具l e x 构造的，语法分析器是由语法自动生成工具 y a c c 构造的。当s q l 语句被解析成为单个词汇并组织成语法树后，语法分析 器就会将该树传送给代码生成器进行处理。而代码生成器则根据它生成一种系 统专用的汇编代码，最后由虚拟机执行并实现所有操作。 3 2 3 虚拟机模块 在本系统结构中虚拟机是一个比较重要的部件，它的主要工作是进行解释 执行字节代码。虚拟机的字节代码一般由一定数量的操作码构成，其主要的功 武汉理r 1 ：人学硕七学位论文 能是对数据库进行操作。它上面的模块和下面的模块都是在为它服务，它的每 一条指令要么是在准备进行某些操作要么就是需要完成某些特定的操作。总之， 所有的这些指令都是为了满足对数据库的操作需求，并且虚拟机的指令集能满 足比较复杂的s q l 命令的要求。系统中所有的s q l 操作从选择记录、修改记录、 创建表到视图和索引，都是首先编译成此种代码，然后再组成一个独立程序用 来完成给定的任务。 3 3 预编译器其它部分 除了上面所提到的主要组成部分外，s q l 预编译器还有几个辅助的功能模 块。它们分别是b t r e e 结构功能处理模块、操作系统接口模块和缓冲功能模块 等，其中对数据的管理工作主要是由b t r e e 结构功能模块和缓冲功能模块共同 完成。它们把数据库中存储的内容划分成大小相等的页的形式，每个页面记录 的内容就是数据库所包含的信息，这些信息包括数据记录、字段记录和索引标 识等。有趣的是这两个模块也不清楚在页内到底记录的是什么具体信息内容， 它们只负责把这些信息传输到数据库中，根本不用去管这里面是什么内容。 索引就是在所需要检索的内容中选择具有有一定意义的数据项按照一定的 有序方式排列，然后可以供其他人查找的一种工具。在这里索引的功能是依靠 b t r e e 结构来实现的，并在每个页与页之间维持着较复杂的联系，为的就是能 够找到所需要的数据。所有的页被组织成树型结构，这是一种专为查询而高度 优化了的树型。 缓冲功能模块的主要工作就是通过操作系统接口在b t r e e 结构模块和物理 存储器之间传递信息。为了能够提高对磁盘操作的速度，较常用的方法就是将 经常使用的信息页面存放到内存当中的缓冲区内，从而尽可能的减少对磁盘的 操作。实现这一过程就需要一定的算法来预测下面将要使用的页，从而使b t r e e 结构能够更快地执行相应的工作。 最后，就是操作系统调用接口部分，凡是涉及操作系统核心资源的操纵必 须由系统调用接口来实现。主要系统调用有如下： ( 1 ) 进程管理：创建进程、终止进程、等待子进程结束、替换进程映像。 ( 2 ) 文件管理：创建文件、打开文件、读文件、写文件、移动文件指针、 关闭文件。 ( 3 ) 存储管理：动态申请、释放存储空间。 1 2 武汉理! l ：大学硕士学位论文 3 3 1b t r e e 概念 我们常常在具体的数据表中设置索引，这样可以方便对数据进行操作，虽 然一级或二级索引通常有助于加快查询速度。在这里有一种更通用的数据结构， 常常被用在商业系统中，这一通用的数据结构被称为b t r e e ，其中有一个被经 常用到的变体到f 】u 做b + t r e e 。从树的本质上讲有两点值得注意【2 0 】： ( 1 ) b t r e e 能自动地保持与数据文件大小相适应的索引层次。 ( 2 ) b t r e e 对所有使用的存储块空间进行管理，使每个块的充满程度在半 满与全满之l 、日j 。这样的索引不再需要溢出块。 正如其名称所表述出来的那样，b t r e e 把它的存储块构建成一棵树。这棵 树是平衡的，即从树根到树叶的所有路径都一样长。通常一个b 。t r e e 有三个层 次：根结点、中间层和叶子，但也可以是任意多层。图3 2 显示了一个小型完整 的b t r e e 结构。对应于每个b t r e e 索引都有一个参数n ，它决定了b t r e e 的所 有存储块的布局。每个存储块存放n 个查找键值和n + 1 个指针。b t r e e 的存储 块除了有n 个键一指针外，还有一个额外的指针。在存储块能容纳n 个键和n + 1 个指针的前提下，我们把n 取得尽可能大。这里有几个重要的规则限制b t r e e 存储块中能出现的内容【i5 1 。 ( 1 ) 在根结点中至少有两个指针被使用。所有指针指向位于b t r e e 下一层 的存储块。 ( 2 ) 叶结点中，最后一个指针指向它右边的下一个叶结点存储块，即指向 下一个键值大于它的块。在叶结点块的其它n 个指针当中，至少有【( n + 1 ) 2 】个 指针被使用且指向数据记录，没有使用的指针可看作空指针且不指向任何地方。 如果第i 个指针被使用，则指向具有第i 个键值的记录。 ( 3 ) 在内层结点中，所有的n + 1 个指针都可以用来指向b t r e e 中下一层的 块。其中至少有 ( n + 1 ) 2 个指针被实际使用。如果有j 个指针被使用，那该块 中将有j 1 个键，设为k l ，k 2 k - l o 第一个指针指向b t r e e 的一部分，一 些键值小于k l 的记录可在这一部分找到。第二个指针指向b t r e e 的另一部分， 所有键值大小等于k l 且小于k 2 的记录在这一部分中。以此类推。最后，第j 个 指针指向b t r e e 的又一部分，一些键值大于等于k i 1 的记录可以在这一部分中 找到。 ( 4 ) 假若我们以常规的画树方式来画b t r e e ，任一给定的字结点按从左( 第 一个子结点) 到右( 最后一个子结点) 的顺序排列，那么，我们在任何一个层 1 3 武汉理工大学硕士学位论文 r 翠。忡 r 譬菁刚= 蓦# ；i 蓑= 三骘暑“曩i ：翟甚；霉三 缓冲模块是本系统中另一个比较重要的模块，它具有四大功能：m 控制、 页面缓存、并发控制和日志恢复。而这些功能不仅是上层b 船的基础，而且 对系统的性能和健壮性有关并影响其中关于并发控制，日志恢复和事务处理等 相关功能的实现基础。另外它的查询优化机制也非常简单基于索引。这 一切使得整个系统的实现变得简单，变得小巧，运行速度也非常快。 武汉理 二大学硕士学位论文 第4 章词法分析设计 4 1 词法分析简述 所谓词法分析器就是执行词法分析程序的部件，它是编译的第一步，在这 一阶段分析程序将源程序读作字符文件并分解为若干个标记，输出单词符号。 每一个单词符号表示源程序中的字符列。这个分析器的主要任务就是从输入的 第一个字符开始扫描到最后一个字符结束，解析出单个词汇，把原来用某种高 级语言编写的程序转换成一连串的单词符号，这些单词符号可以是标识符、常 数、运算符等。 在进行词法扫描的过程中，扫描程序需要进行格式的配对，所以需要研究 对格式的说明和识别单词的方法，这其中最主要的是正则表达式和有限自动机。 对词法分析的研究可以从几个方面进行，由于每种程序设计语言是由各种标记 组成，而每个标记又是若干字符按照一定的规则组成。所以，首先要弄清楚字 符串的集合的组成形式。其次，正则表达式的构造和有限自动机的运行机制， 以及如何编写有限自动机执行过程的程序。 4 2 词法分析要素 4 2 1 扫描处理 扫描程序的任务是从源代码中读入字符流并解析为在编译器后面部分会处 理的逻辑单元。由扫描程序生成的逻辑单元称作记号( t o k e l l ) ，将字符组合成记 号和语言中将字母构成单词并确定单词含义一样。 记号通常定义为枚举类型的逻辑项。例如，记号在c 语言中可被定义为： 聊e d e f e n 啪 ( i f ，t h e n ，e l s e ，p l u s ，m i n u s ，n u m ，i d ，) t o k 咖e ； 记号有若干种类型，这其中第一类是保留字，如i f 和t h e n ，它们表示字 符串“i f ，和“t h e i l ”。第二类是特殊符号，如算术符号加( p l u s ) 和减( m 烈u s ) ， 武汉理工大学硕士学位论文 它们表示符号“+ 和“。第三类是表示多字符串的记号，如n u m 和i d ， 他们分别表示数字和标识符。 由于扫描程序需要用至少一些记号来构造串值，任何与记号相关的值都是 记号的属性( a t t r i b u t e ) ，而串值就是属性的示例。有时候也说，记号本身就可以 看作是简单的其它属性，而记号就是它所有属性的总和。为了满足编译器后面 的处理需要，扫描程序要求至少具有与记号所需相等的属性，扫描程序会计算 每一个记号的这些属性，所以将所有的属性收集到一个单独构造的数据类型中 是很有必要的，这种数据类型称作记号记录( t o k e l lr e c o f d ) 。在c 语言中这样的 记录说明为： 1 p e d e f s t m c t t o k e n t y p et o k e 肌v a l ； c h a r 宰s t r i n g v a l ； i n t n u 】n v a l ； )t o k e n r e c o r d ； 一般情况下，扫描程序是在分析程序的控制下进行操作的，它通过函数从 输入中返回有关命令的下一个记号，在c 语言中的类似说明： t o k e l l t 押eg e t t o k e l l ( v o i d ) ； 在这个方式中声明的g e t t o k e l l 函数在调用时从输入中返回下一个记号，并 计算诸如记号串值这样的附加属性。通常，输入字符串并不给这个函数提供参 数，但参数却被保存在缓冲区中或由系统输入设备提供。 4 2 2 正则表达式 字符串的格式以正则表达式的形式来表示。它完全是由它所匹配的串集来 定义，这个集合称为由正则式生成的语言，记作l ( r ) 。下面从两个方面来说明正 则表达式的相关概念。 ( 1 ) 正则式表达式可以被定义为以下形式中的一种【8 】： 1 ) 基本正则表达式由一个单字符a ，以及元字符或元字符组成，这里 有三种形式。第一种情况，l ( a ) = a ) ；第二种情况，l ( ) = ) ；第三种情况， l ( 中) = ) 。 2 ) rfs 格式的表达式：其中r 和s 均是正则表达式。在这种情况下，l “l s ) = l ( r ) u l ( s ) 。 1 6 武汉理丁大学硕七学位论文 3 ) r s 格式表达式：其中r 和s 是正则表达式。在这种情况下，l ( r s ) = l ( r ) l ( s ) 。 4 ) 一格式的表达式：其中r 是正则表达式。在这种情况下，l ( r 宰) = l ( r ) 宰。 5 ) ( r ) 格式的表达式：其中r 是正则表达式。在这情况下，l ( ( r ) ) = l ( r ) 。 ( 2 ) 正则表达式的运算，有这样的三种运算：运算符“i ”、“、