（计算机软件与理论专业论文）数据库过程语言解释器的研究与实现.pdf

电子科技大学硕士论文：数据库过程语言解释器的研究与实现 中文摘要 学科专业：计算机软件与理论 论文题目：数据库过程语言解释器的研究与实现 导师姓名：孙世新教授 硕士生姓名及班学号：张永星( 0 2 s 0 8 3 0 8 1 ) 成都华好网景科技有限公司拥有自主知识产权的国产关系数据库管理系统 华好0 k s q l ，在0 k s q lv 1 2 已经支持s q l 9 2 入门级标准中大多数语句的基础上， 在0 k s q lv 2 0 的开发过程中加入对数据库过程语言的支持以实现服务器端的存 储过程和函数。本文针对为实现存储过程和函数而进行的数据库过程语言解释器 的开发进行了详细论述，并对编译和解释系统相关技术进行了探讨和研究。 在对语言实现方面的研究中，论文总结了编译器的一般模型，并针对本系统 前端和后端分别选择了合适的实现方案。并对语言设计、语法分析、语义分析， 以及中间代码生成和用来对中间代码解释执行的虚拟机等进行了深入的讨论。 在系统前端语法分析、语义分析及中间代码生成方面，先经过语法、语义分 析建立抽象语法树，然后对抽象语法树进行遍历生成中间代码。 在系统后端虚拟机实现方面，借鉴了j v m 和n e tc l r 的思想，用虚拟机维 护由代码区、框架栈、函数运行栈、常量区和指令计数器等共同构成的运行时环 境，控制程序的执行。通过特殊设计，对参数和局部变量的访问，不需要访问符 号表，提高了虚拟机的执行效率。 关键字：解释器；过程语言；抽象语法树；中间代码；虚拟机 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 a b s t r a c t m a j o r ：c o m p u t e r s o f t w a r ea n dt h e o r y s u b j e c t ：s t u d ya n di m p l e m e n t a t i o no f i n t e r p r e t e ro f d a t ab a s e p r o c e d u r e l a n g u a g e t u t o r ：p r o f s u ns h i x i n m a s t e rc a n d i d a t e ：z h a n gy o n g x i n g ( 0 2 s 0 8 3 0 8 1 ) h u a h a oo k s q li st h eh o m e m a d er e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e m ( r d b m s ) o fc h e n g d uh u a h a ow a n g j i n gt e c h n i q u ec o r p o r a t i o nl t d i no r d e rt o r e a l i z et h ep r o c e d u r ea n df u n c t i o no fs e r v e r , t h es u p p o r tf o rt h ed a t a b a s ep r o c e d u r e l a n g u a g ei s a d d e di nt h ed e v e l o p m e n tp r o c e s so fo k s q lv 2 0 ，o nt h eb a s eo f o k s q lv 1 2 w h i c h a l r e a d y s u p p o r t s m o s ts t a t e m e n t s a c c o r d i n g t o s q l 9 2 e l e m e n t a r ys t a n d a r d i nt h i st h e s i s ，s u r r o u n dt h ed e v e l o p m e n to f d a t a b a s ep r o c e d u r e l a n g u a g ei n t e r p r e t e r w h i c hi st or e a l i z et h e p r o c e d u r ea n df u n c t i o n ，t h ed e t a i l e d d i s c u s s i o ni sm a d e m o r e o v e r , t h i st h e s i sa l s om a k e ss o m ee x p l o r a t i o na n dr e s e a r c h o nt h er e l e v a n tt e c h n i q u e so fc o m p i l ea n di n t e r p r e ts y s t e m ac o m m o nf r a m e w o r ko fc o m p i l e ri sa b s t r a c t e d d u r i n g t h er e s e a r c ho ft h e i n t e r p r e t e ro f p r o c e d u r el a n g u a g e a f t e rt h a t ，t h ei m p l e m e n t a t i o ns c h e m e s o f t h ef r o n t e n da n db a c ke n da r ep r e s e n t e d a n dat h o r o u g hd i s c u s s i o ni sd e v e l o pa c c o r d i n gt o l a n g u a g ed e s i g n ，s y n t a xa n a l y s i s ，s e m a n t i ca n a l y s i s ，t h ei n t e r m e d i a t ec o d eg e n e r m i o n a n dt h ev i r t u a lm a c h i n ew h i c hi su s e dt oi n t e r p r e ta n de x e c u t et h ei n t e r m e d i a t ec o d e s a n ds o o n i nt h ea s p e c to fs y n t a xa n a l y s i s ，s e m a n t i ca n a l y s i sa n dt h ei n t e r m e d i a t ec o d e g e n e r a t i o no fs y s t e mf r o n t ，a na b s t r a c ts y n t a xt r e ei s b u i l ta f t e rs y n t a xa n a l y s i sa n d s e m a n t i ca n a l y s i s ，a n dt h e nt h i sa b s t r a c ts y n t a xt r e ei st r a v e r s e dt og e n e r a t et h e i n t e r m e d i a t ec o d e d u r i n gt h er e a l i z a t i o no f v i r t u a lm a c h i n eo fs y s t e mb a c k ，w ec o n s u l tt h et h e o r yo f j v ma n d n e tc l r t h ev i r t u a lm a c h i n ei s u s e dt om a i n t a i nt h er u n - t i m e e n v i r o n m e n tw h i c hi sc o m p o s e do fc o d es e c t i o n ，f r a m es t a c k ，f u n c t i o ns t a c k ，c o r m r a n t s e c t i o n ，i n s t r u c t i o np o i n t e r , e t ca n dc o n t r o lt h ee x e c u t i n go fp r o g r a m t h r o u g ht h e s p e c i a ld e s i g n ，w h e np a r a m e t e r sa n dl o c a lv a r i a b l e sa r ev i s i t e d ，t h ev i s i to f s y m b o l t a b l ei sn om o r en e c e s s a r y t h e r e f o r e ，t h ee x e c u t i n ge f f i c i e n c yo f v i r t u a lm a c h i n ei s r a l s e d 。 i i 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 k e yw o r d s ：i n t e r p r e t e r ；p r o c e d u r el a n g u a g e ；a b s t r a c ts y n t a xt r e e ；i n t e r m e d i a t e c o d e ；v i r t u a lm a c h i n e i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包括 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同学对本教研室做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：匆琶串蠼日期：如护芗年f 月6 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：2 卯歹年月b 日 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 第一章引言 本章主要阐述本课题的背景、来源、重要意义、实用价值及本人在课题中的 工作；并介绍了本论文的组织形式。 1 1 研究背景与意义 掌握核心软件技术，开发自主知识产权的系统软件一直是我国软件产业发展 的目标。作为信息处理的核心软件之一，数据库系统是除操作系统外最重要的核 心软件，也是我国信息化建设中需求量最大、应用最广泛的基础性软件。但中国 数据库软件市场主导者一直是国外厂商。我国信息化建设的深入迫切需要中国人 在数据库软件上有所作为。数据库软件是数据处理的核心，因此无论是发展民族 软件产业角度还是保障国家信息安全的角度，发展国产数据库软件一直都是我国 科研技术人员的梦想。与此同时，国防、政府、金融等要害部门对自主、安全的 数据库管理系统提出了非常迫切的要求。在此背景下，发展国产数据库系统，将 对我国软件产业及相关产业发挥重大影响。 l 、发展国产数据库系统，掌握数据库核心技术对提升整个中国软件业的技术 水平、摆脱应用软件市场的被动局面、推动基础软件的规模化、产业化进程具有 十分重要的意义。 2 、发展适合国情的国产数据库基础性软件，对推动我国信息化建设具有重要 的作用。国家每年要花大量的资金在国外数据库软件上，如果采用国产软件，将 节省大量的资金。 3 、发展国产数据库系统对保证国家信息安全具有重要意义。信息化涉及到国 家政治、经济、军事、安全的要害领域，因此拥有自主知识产权的国产数据库对 保证国家信息安全具有重要的意义。信息安全首先是系统的安全，数据库系统的 安全为数据安全提供了最可靠的保证。 成都华好网景科技有限公司自主研发的国产数据库管理系统华好o k s q lv 1 2 已经支持s q l 9 2 入门级标准中大多数语句，在此基础上，我们在o k s q lv 2 0 的 开发过程中加入对数据库过程语言的支持以实现服务器端的存储过程和函数。数 据库过程语言解释器的的主要目的是实现服务器端的存储过程和函数，存储过程 和函数结合了s q l 的简单灵活、功能丰富的数据操作特点和过程化语言的数据处 理特点。由流控制和s q l 语句书写存储过程，若干个有联系的过程可以组合在一 起构成程序包。从而大大增强了s q l 语言的功能和灵活性，可以完成复杂的判断 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 和较复杂的运算。由于存储过程可以使没有权限的用户在控制之下间接地存取数 据库，从而保证数据的安全。而且存储过程可以使相关的动作在一起发生，从 而可以维护数据库的完整性。 本文就是关于国产数据库系统o k s q l 实现服务器端的存储过程和函数的开发 过程中的解决方案和一些技术问题。 1 2 研究内容 正如论文题目“数据库过程语言解释器的研究与实现”所述。论文的主要研 究内容可概括为： 。过程语言的选择和设计，包括语言定义、语言的词法、文法； 过程语言的词法分析、语法分析、语义分析； 。中间代码的指令设计和生成； 用来支持中间代码执行的虚拟机的设计和实现； 其中，我的主要工作有：语法分析部分y a c c 文法的编写，中间代码的生成 模块以及后端虚拟机的设计与实现。同时对中间代码的指令设计提出了一些修改 意见。 1 3 论文组织 本论文包括八章，如下： 第一章：引言。即本章，介绍本文的研究背景、研究内容和意义。 第二章：相关技术及背景。介绍了数据库系统相关知识，华好o k s q l 数据库 管理系统，由于我们的过程语言参照了o r a c l e 的p l i s q l 的语法，因此还对 p l s q l 语言进行了简单介绍。 第三章：系统的总体设计。总结了编译器的一般模型，选择了系统的实现方 案，据此对解释器的实现进行了总体设计。并对连接解释器前后两端的关键 中间代码的指令格式进行了设计。 第四章：词法分析和语法分析。介绍了词法分析、语法分析的功能，以及本 系统词法语法分析的实现。 第五章；中间代码的格式和生成。在词法分析和语法分析后生成的抽象语法 数的基础上，对其进行遍历生成我们定义的中间指令格式的中间代码。 第六章；虚拟机。虚拟机的设计以及对于中间代码解释执行的实现。 第七章：存储过程的运行实例。给出一个存储过程创建和执行过程的实例。 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 第八章：结束及展望。总结了本论文完成工作的特点和一些不足之处。 由于通用大型数据库管理系统的实现国内还处在起步阶段，而国外厂商没有 公开核心技术，再者时间仓促而且作者本人水平有限，论文中谬误之处在所难免， 敬请各位老师和各位同仁批评指_ i _ f 。共同创造更好的数据库管理系统。 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 第二章相关技术及背景 2 1 数据库管理系统产生与发展 数据库系统是一个实际可运行的存储、维护和应用系统提供数据的软件系 统，是存储介质、处理对象和管理系统的集合体。通常由软件、数据库和数据管 理员组成。其软件主要包括操作系统、各种宿主语言，实用程序以及数据库管理 系统。数据库由数据库管理系统统一管理，数据的插入、修改和检索均要通过数 据库管理系统进行。数据库管理系统是一种系统软件，它的主要功能是维护数据 库并有效地访问数据库中任意部分数据。对数据库的维护包括保持数据的完整 性、一致性和安全性。 众所周知，数据库系统并不是在计算机产生的同时就出现的，而是随着计算 机技术的不断发展，在特定的历史时期、特定的需求环境下出现的。人类在1 9 4 6 年发明了世界上的第一台计算机到2 0 世纪6 0 年代这漫长的2 0 年里，计算机操 作系统还主要局限于文件的操作，同样。对数据的管理也主要是通过文件系统来 实现。进行计算所需要的各种数据存放在各自的文件里面。当要使用这些数据的 时候，将文件打一开，读取文件中的数据到内存中。当计算完毕后，将计算结果 仍旧写入到文件中去。虽然这种在文件中存放数据的方式目前在很多系统中还在 使用，但是，这样的数据存放方式在三四十年前的当时，就已经显示出了非常明 显的不足。这些不足主要集中在无法对数据进行有效的统一管理。具体表现在这 样几个方面： 程序员编写应用程序非常不方便。应用程序的设计者需要对程序所使用的文 件的逻辑结构和物理结构都了解的非常清楚。而计算机操作系统只提供将文件打 开、关闭、保存等非常低级的操作，而对数据的修改、查询操作则需要应用程序 来解决，如果程序所需要的数据存放在不同的文件里，而且这些文件的存储格式 又迥然不同。这样就给应用程序的开发带来了巨大的麻烦，程序员要为程序中所 用到的每个文件都写好相应的接口，而且不同的文件格式相差很大，这样就大 大的增加了编程的工作置，从而使得在文件级别上开发应用程序的效率非常低 下，严重影响应用软件的发展。文件结构的每一处修改都将导致应用程序的修改， 从而使得应用程序的维护工作量特别大。 计算机操作系统中的文件系统一般不支持对文件的并发访问。而在现代计算 机系统中，为了充分发挥计算机系统的资源使用效率，一般都允许多个程序“同 时”运行，即并发性。对数据库系统同样有并发性的要求，现在比较大型的数据 4 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 库都有非常强的并发访问机制，这样可以充分利用数据库服务器的软、硬件资源， 避免浪费。 由于基于文件系统的数据管理缺乏整体性、统一性，在数据的结构、编码、 表示格式等诸多方面不能做到标准化、规范化，不同的操作系统有不同的表示方 式，因此在一定程度上造成了数据管理的混乱。 另外，基于文件系统的数据管理在数据的安全性和保密性发面难以采取有效 的措施，在一些对安全性要求比较高的场合，这种安全上的缺陷是完全不允许的。 针对文件系统的这些重要缺点，人们逐步发展了以统一管理数据和共享数据为主 要特征的系统，这就是数据库系统。数据库系统就是在这样的背景下发展起来了。 1 9 6 4 年，美国通用电气公司开发成功了世界上的第一个数据库系统一 i d s ( i n t e g r a t e dd a t as t o r e ) i d s 奠定了网状数据库的基础，并且得到了广泛 的发行和应用，成为数据库系统发展史上的一座丰碑。1 9 6 9 年，美国国际商用 机器公司( i b m ) 也推出世界上第一个层次数据库系统i m s ( i n f o r m a t i o n m a n a g e m e n t s y s t e m ) ，同样在数据库系统发展史上占有重要的地位。 七十年代初，e f c o d d 在总结前面的层次、网状数据库优缺点的基础卜， 提出了关系数据模型的概念。在整个七十年代，关系数据库系统无论从理论上还 是实践上都取的了丰硕的成果。在理论上，确立了完整的关系模型理论、数据依 赖理论和关系数据库的设计理论：在实践上，世界上出现了很多著名的关系数据 库系统，比较著名的如s y s t e mr ，i n g r e s ，o r a c l e ，d b 2 等。和文件系统相比， 数据库系统有一系列的特点，具体表现在以下几个方面： 数据库系统向用户提供高级的接口，在文件系统中，用户要访问数据，必须 了解文件的存储格式、记录的结构等。而在数据库系统中，这一切都不需要了。 数据库系统为用户处理了这些具体的细节，向用户提供非过程化的数据库语言 ( 郎通常所说豹s q l 语言) ，用户只要提出需要什么数据，而不必关心如何获得这 些数据。对数据的管理完全由数据库管理系统( d b m s ：d a t a b a s em a n a g e m e n t s y s t e m ) 来实现。 查询的处理和优化。查询通常指用户向数据库系统提交的一些对数据操作的 请求。由于数据库系统向用户提供了非过程化的数据操纵语言，因此对于用户的 查询请求就由d b m s 来完成，查询的优化处理就成了o b i s 的重要任务。 并发控制。前面曾经提到，文件系统一般不支持并发操作，这样大大的限制 了系统资源的有效利用。在数据库系统中，情况就不一样了。现代的数据库系统 都有很强的并发操作机制，多个用户可以同时访问数据库，甚至可以同时访问同 一个表中的不同记录。这样极大的提高了计算机系统资源的使用效率。 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 数据的完整性约束。凡是数据都要遵守一定的约束，最简单的一个例子就是 数据类型，例如定义成整型的数据就不能是浮点数。由于数据库中的数据是持久 的和共享的，因此对于使用这些数据的单位来说，数据的正确显得非常重要。在 关系数据库系统中，比较重要的完整性约束有实体完整性、域完整性、参照完整 性和用户自定义的完整性等。 进入二十一世纪八十年代之后，计算机硬件技术有了飞速的提高。计算机技 术的提高促使计算机应用不断深入，产生了许多新的应用领域，例如计算机辅助 设计、计算机辅助制造、计算机辅助教学、办公自动化、智能信息处理、决策支 持等。这些新的领域对数据库系统提出了新的要求。但是由于应用的多元化，不 能设计出一个统一的数据模型来表示这些新型的数据及其相互关系，因而出现 了百家争鸣的局面，产生了演绎数据库、面向对象数据库、分布式数据库、工程 数据库、时态数据库、模糊数据库等新型数据库的研究和应用。 不过到目前为止，在世晃范围内得到主流应用的还是经典的关系数据库系 统，比较知名的如：o r a c l e ，s q ls e r v e r ，s y b a s e ，d b 2 等。 数据库系统的出现是计算机应用的一个里程碑，它使得计算机应用从以科学 计算为主转向以数据处理为主，并从而使计算机得以在各行各业乃至家庭普遍使 用。在它之前的文件系统虽然也能处理持久数据，但是文件系统不提供对任意部 分数据的快速访问，而这对数据量不断增大的应用来说是至关重要的。为了实现 对任意部分数据的快速访问，就要研究许多优化技术。这些优化技术往往很复杂， 是普通用户难以实现的，所以就由系统软件( 数据库管理系统) 来完成，而提供给 用户的是简单易用的数据库语言。由于对数据库的操作都由数据库管理系统完 成，所以数据库就可以独立于具体的应用程序而存在，从而数据库又可以为多个 用户所共享。因此，数据的独立性和共享性是数据库系统的重要特征。数据共享 节省了大量入力物力，为数据库系统的广泛应用奠定了基础。数据库系统的出现 使得普通用户能够方便地将日常数据存入计算机并在需要的时候快速访问它们， 从而使的计算机走出科研机构进入各行各业、进入家庭。 2 2 国产数据库管理系统华好o k s o l 的背景及特点 成都华好网景科技有限公司开发的o k s q l 数据库，是拥有完全自主知识产权 的通用关系型数据库管理系统，并且在在一些领域内已经得到了一些应用，例如： l 四) l l 省林业局森林资源管理系统、电脑商情报发行数据库系统、成都华好网景科 技有限公司提供手机定位服务的后台数据库等等。数据库系统的成功研制和应 用，一方面将可能解决由于广泛应用国外数据库产品可能带来的信息安全问题， 6 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 另一方面也将在系统软件领域极大地推动我国民族软件产业的发展。 1 o k s q l 体系结构简介 3 - 一台机器安装的o k s q l 实例可同时对多个数据库进行服务，整个系 统含一个系统库( 其名固定为：s y t e m ) 及多个用户库，系统库仅用 于记录系统级用户及所有用户库的信息，在其上不能创建饪何新的 表及任何模式对象( 如：v i e w 、s e q u e n c e 等) ； 3 - 在系统库( s y s t e m ) 上具有d b a 或r e $ 0 1 1 , r c e 权限的用户可以创建用 户库，创建者即为用户库的d b o ，自然拥有该库的d b a 权限； 3 - s y s t e m 库上的用户，但若他( 她) 不是某用户库的合法用户，则不 能连接该用户库，即各个库的权限控制是独立的； 九 每个数据库由l 到多个数据文件、2 个控制文件( c t l ) 、3 个l o g 文件 ( 1 0 9 ) 组成，多个数据文件归属于一个或多个表空间，一个数据库至 少有一个表空间即系统表空间，使用中，视需要可为一个库创建多 个附加的表空间，一个表空间可含一个或多个数据文件，各个数据 文件可以放在不同的磁盘、不同的目录下； 3 - 表存贮在表空间中，创建表时，若不指定表空间，则使用系统表空 间作为默认表空间： 九多个数据库在启动后共享处理器、内存等系统资源，系统可同时接 收若干个来自客户端的连接，这些连接可连到系统库或某个用户库 上。 2 。o k s q l 技术特征 3 - 支持s q l 9 2 入门级标准中大多数语句； 九支持事务处理，具有多级回滚机制； 九支持子查询； 九可以很简单地建立数据库、表等对象，也支持使多个选项创建结构 复杂、高效的数据库、表等； 九允许多种块尺度的表空间共存于一个系统中； 九支持大对象存取； 九使用特别技术实现无限制的行级锁，因而系统具有较高的并发处理 能力； 九支持库级、表级、列级权限控制： 九同时支持网络加密与数据文件加密，极大地保证了数据的安全性； 九有故障恢复能力： 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 九 能在较低配置的机器中良好运行，也能充分利用强大的硬件资源。 3 目前提供的用户接口 九o d b c 支持； 九j d b c 支持； 天提供系统安装和卸载、d b a7 - 具、交互式s o l 。 4 运行环境 丸 硬件：i n t e lp 36 5 0 m h z 以上及其兼容c p u 、2 5 6 m 内存、1 0 0 以上 硬盘、1 0 m ( 或1 0 0 m ) 以太网卡； 九 操作系统：w i n d o w sn t4 , 0 以上版本、w i n d o w s 2 0 0 0p r o f e s s i o n a l 、 w i n d o w s 2 0 0 0s e r v e r 、w i n d o w sx p 等以n t 为内核的w i n d o w s 版本。 2 3 编译和解释系统相关知识 高级语言程序的执行方式有两种，即编译执行和解释执行。 ( 1 ) 编译执行：高级语言程序的编译执行通常分成两个阶段，即编译阶段和运 阶段。编译阶段是将源程序全部转换成目标程序。运行阶段是将已生成的目标程 序连同运行系统，接受程序的输入数据，执行目标程序，输出执行结果。 ( 2 ) 解释执行：程序的解释执行是不需要将源程序翻译成目标程序，而是对源 程序解释直接得到计算结果。有的解释执行是将高级语言程序先加工成一种中间 语言的代码，然后直接解释执行这种中间语言代码。完成上述功能的程序称为解 释程序或解释器( i n t e r p r e t e r ) 。有一类解释程序没有生成中闻语言代码这一过程， 因此是直接解释执行源程序的。 解释器的设计与实现涉及到编译的主要原理和技术，在此对编译程序构造的 一般原理、基本设计方法、主要实现技术和一些自动构造工具作简单的介绍。 2 3 1 编译过程及编译程序结构 编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序 ( s o r i c el a n g u a g e ) 编写的程序作为输入，而产生用目标语言( t a r g e tl a n g u a g e ) 编写的 等价程序。通常地，源程序为高级语言( h i g h - r e v e ll a n g u a 4 ；e ) ，如c 或c + + ，而目 标语言则是目标机器的目标代码( o b j e c tc o d e ，有时也称作机器代码( m a c m n e c o d e ) ) ，也就是写在计算机机器指令中的用于运行的代码。这一过程可以用下图 表示： 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 专纂霾毒序， 蔓至至垂 目标程序 2 3 2 编译过程概述 编译程序完成从源程序到目标程序的翻译工作，这是一个复杂的过程。编译 原理及方法能很好地完成对一个语言的编译器的构造，己形成了一套系统的理论 和利于程序实现的较形式化的算法，目前还有自动生成工具“l e x ”，”y a c c ” 等可供使用。 一般的编译程序由以下几个模块组成：词法分析模块，语法分析模块，语义 分析模块，中间代码生成模块，代码优化模块，目标代码生成模块，错误检查和 处理模块，信息表管理模块。 1 词法分析( 1 e x i e a la n a l y s i s ) ；将字符串形式的源程序扫描转换为单词串形式 的等价程序。用文法来描述语言中的各类单词，通常采用的是正规表达式( r e g u l a r e x p r e s s i o n ) ，据此构造识别各类单词的有限自动机( f m i t e a u t o m a t a ) 。词法分析的结 果提供给语法分析使用。l e x 是一种自动生成词法分析程序的工具，使开发者 将精力集中于程序单词的正规表达式的构造上。 2 语法分析( s y n t a xa n a l y s i s ) ：负责对源程序进行全面的分析，可以用于判断 源程序的合法性。用文法来描述整个程序的语法结构，通常由上下文无关文法 ( c o n t e x t f r e eg r a m m a r ) 来描述，其形式表现为产生式( , p r o d u c t i o n ) 。对一种语言的 产生式集合的构造将是很关键的，其中要考虑二义性问题，同时还需要与语法分 析、语义分析等整个过程结合起来考虑，比如冲突的消除、语义子程序的设计等。 在数据结构上一种语言的程序可以表达为分析树( p a r s et r e e ) 或语法树( s y n t a x t r e e ) 。因此对语言的语法分析也就有自顶向下( t o p d o w n p a r s i n g ) 自底向上 ( b o t t o m u pp a r s i n g ) 分析两种。对于自顶向下分析有递归下降分析 ( r e c u r s i v e - d e s c e n tp a r s i n g ) , l l ( 1 ) 分析( l l ( 1 ) p a r s i n g ) 以及l l0 0 分析( l l ( k ) p a r s i n g ) 等技术，对于自底向上分析有l r ( 1 ) 分析( l r ( 1 ) p a r s i n g ) ，s l r ( 1 ) 分析 ( s l r ( 1 ) p a r s i n g ) , s l r ( k 扮析( sl r ( k ) p a r s i n g ) ，l a l r ( 1 ) 分析( l a l r ( 1 ) p a r s i n g ) 等 技术。y a c c 是一个l a l r ( 1 ) 分析程序的生成器，只需编写y a c c 说明文件， 就可自动生成l a l r ( 1 ) 分析程序。在具体使用上，有两个难点：一是在构造产 生式集时冲突及二义性的消除；二是对各产生式的动作子程序的编写。 3 语义分析( s e m a n t i ca n a l y s i s ) ：主要是计算编译过程所需的附加信息，它包 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 括与上下文无关文法和标准分析算法以外的信息，如符号表、表达式和语句中的 类型推断和检查以及在语言的类型规则作用域内判断它们的正确性。这一阶段通 常与代码生成，优化等过程结合起来进行。目前对于语义分析还没有形式化的算 法及成熟的通用工具，这方面大有研究发展的前景。属性文法( a t t r i b u t e g r a m m a t ) 提供了语义分析的一种很好的思想，它对语法制导的语义分析( s y n t a x d i r e c t e d s e m a n t i ca n a l y s i s ) 具有重要的指导意义。通过这种方法，对源程序进行多遍扫描， 产生合适的中间数据结构，为代码生成提供支持。 4 中间代码( i n t e r m e d i a t ec o d e ) 生成：即线性化前述分析过程中所得到的反映 源程序的数据结构，使之更有利于执行。目前常用的中间代码形式有：三元式、 四元式、p 一代码( p - c o d e ) ，u 一代码等。中间代码的生成技术，与语义分析技术 密切联系。 5 代码优化( c o d eo p t i m i z a t i o n ) ：在不改变原有程序功能的前提下，通过对中 间代码的改进、调整，来提高执行的效率。优化的技术也有很多，如：利用流图 ( f l o wg r a p h ) 、基本块的d a g 图( d a go f ab a s i cb l o c k ) 来进行优化的技术就是其中 一例。 6 目标代码( t a r g e tc o d e ) 生成：将中间代码转化为目标机器的代码，并再次优 化。 7 错误检查和处理：检查并报告程序的错误，并进行适当的处理。 8 信息表管理：这涉及到符号表、运行时动态信息的组织和管理等方面，所 管理的信息中要包含调试所需的信息。 一个编译过程可由一遍、两遍或多遍完成。所谓“遍”，也称“趟”，是对源 程序或其等价的中间语言程序从头到尾扫描并完成规定任务的过程。每一遍扫描 可以完成上述一个阶段或多个阶段的工作。例如一遍只完成词法分析工作：或一 遍完成词法分析和语法分析工作：甚至一遍完成整个编译工作。对于多遍的编译 程序，第遍输入的是用户书写的源程序，最后一遍输出的是目标语言程序，其 余上一遍的输出是下一遍的输入。通常，一个多遍的编译程序比一遍的编译程序 占内存少，且整个编译程序的逻辑结构清晰，但遍数增多也增加了读写中间文件 的次数，耗时多，比一遍的编译速度慢。 上述各阶段都是相互联系和结合的，它们的设计必须站在整个过程的着眼点 e 。 2 3 。3 编译器的一般架构 编译器的设计最典型的特点是其相对独立的构造阶段，符号表是整个编译阶 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 段的交互中心。但是随羞软件体系结构的发展和程序设计语苦对可靠性、有效性、 可用性以及可移植性的要求，现代编译器的体系结构通常划分为前端和后端。前 端包括词法分析、语法分析、语义分析和中间代码生成，这几个阶段只和源语言 相关，而和目标机器是无关的；后端包括中间代码优化和目标代码生成，后端和 目标机器相关，而和源语言无关。中间代码( 或者是中间表示) 作为其间的交互媒 介。这种体系框图如图所示。 图2 - 2 基于中间代码技术的编译架构 这样的架构具备有：a ) 良好的可移植性：可以通过方便的改变后端模块来实 现在不同目标环境中的执行：b ) 良好的可扩展性：可以通过方便的改变前端模块 来支持不同文法的源语言。这种架构也顺应了面向对象设计中的开闭原则。当 前，常见的中间代码技术包括三元式、四元式、d a g 、字节码( b y t ec o d e ) 、m si l 。 字节码( b y t ec o d e ) 使用基于栈的计算模型具有简单，易读的特点。每个指令的 长度都是一个字节。例如：j v m 采用的是字节码。m si l ( m i c r o s o f ti n t e r m e d i a t e l a n g u a g e ) 是一种不依赖于c p u 的机器语言，i l 的级别要比大多数c p u 的机器语 言高。i l 支持对象类型，并具可以创建、初始化对象、调用对象虚拟方法，直 接操作数组元素，支持错误处理和异常指令。 针对这种基于中间码的编译体系思想，对于中间代码的处理，后端系统有以 下常见的设计原理： 编译执行：对于要执行的中间代码，首先编译为本地的目标代码，然后执 行目标代码。同时编译执行不是一次执行一条中间指令，因此可以进行代码优化。 常见的编译系统后端包括中间代码优化和目标代码生成两个部分。这是一个典型 的编译器。 解释执行( i n t e r p r e t a t i o n ) ：首先对中间代码进行载入，每次只执行一条 指令，然后执行与该指令相关的机器码，如此不断循环直到停机。这样整个系统 就是一个解释器。y v u 采用的就是这种方式。本文中的对于数据库过程语言采用 的就是这种实现方式。 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 解释执行与编译执行结合：通过运行信息寻找应用程序的关键部分( 8 0 的 代码执行时间往往花在2 0 的代码上) 通过动态编译把这些关键代码内置，同时 在程序的两次执行期间不保存编译结果而保证可移植性。当前的j v m f 朝着这种 虚拟机技术方向发展。 2 4o r a c i ep l s q l 语言简介 由于本文实现数据库过程语言基本参照o r a c l e 的p l s q l 的语法，这里对 p l s q l 做一些简单介绍。 p l s q l 是o r a c l e 对标准数据库语言的扩展，o r a c l e 公司已经将p l s q l 整 合到o r a c l e 服务器和其他工具中了，近几年中更多的开发人员和d b a 开始使用 p l s q l 。 p l s q l 的优点 从版本6 开始p l s q l 就被可靠的整合到o r a c l e 中了，一旦掌握p l s q l 的 优点以及其独有的数据管理的便利性，那么你很难想象o r a c l e 缺了p l s q l 的情 形。p l s q l 不是一个独立的产品，他是一个整合到o r a c l e 服务器和o r a c l e 工 具中的技术，可以把p l s q l 看作o r a c l e 服务器内的一个引擎，s q l 语句执行者 处理单个的s q l 语句，p l s q l 引擎处理p l s q l 程序块。当p l s o l 程序块在p l s o l 引擎处理时，o r a c l e 服务器中的s o l 语句执行器处理p l s q l 程序块中的s q l 语 句。 p l s o l 的优点如下： p l s q l 是一种高性能的基于事务处理的语言，能运行在任何o r a c l e 环境 中，支持所有数据处理命令。通过使用p l s q l 程序单元处理s o l 的数据定义和 数据控制元素。 p l s o l 支持所有s o l 数据类型和所有s o l 函数，同时支持所有o r a c l e 对 象类型 p l s o l 块可以被命名和存储在o r a c l e 服务器中，同时也能被其他的p l s o l 程序或s o l 命令调用，任何客户朋匣务器工具都能访问p l s o l 程序，具有很好的 可重用性。 可以使用o r a c l e 数据工具管理存储在服务器中的p l s q l 程序的安全性。 可以授权或撤销数据库其他用户访问p l s q l 程序的能力。 p l s q l 代码可以使用任何a s c i i 文本编辑器编写，所以对任何o r a c l e 能 够运行的操作系统都是非常便利的 对于s o l ，o r a c l e 必须在同一时间处理每一条s q l 语句，在网络环境下这 电子科技大学硕士论文：数据库过程语言解释器的研究与实现 就意味着每一个独立的调用都必须被o r a c l e 服务器处理，这就占用大量的服务 器时间，同时导致网络拥挤。而p l s q l 是以整个语句块发给服务器，这就降低 了网络拥挤。 p l s q l 块结构 p l s q l 是一种块结构的语言，组成p l s q l 程序的单元是逻辑块，一个p l s q l 程序包含了一个或多个逻辑块，每个块都可以划分为三个部分。与其他语言相同， 变量在使用之前必须声明，p l s q l 提供了独立的专门用于处理异常的部分，下 面描述了p l s q l 块的不同部分： 声明部分( d e c l a r a t i o ns e c t i o n ) 声明部分包含了变量和常量的数据类型和初始值。这个部分是由关键字 d e c l a r e 开始，如果不需要声明变量或常量，那么可以忽略这一部分；需要说明 的是游标的声明也在这一部分。 执行部分( e x e c u t a b l es e c t i o n ) 执行部分是p l s q l 块中的指令部分，由关键字b e g i n 开始，所有的可执行 语句都放在这一部分，其他的p l s q l 块也可以放在这一部分。 异常处理部分( e x c e p t i o ns e c t i o n ) 这一部分是可选的，在这一部分中处理异常或错误，对异常处理的详细讨论 我们在后面进行。 p l s q l 块语法 d e c l a r e d e c l a r a t i o ns t a t e m e n t s b e g i n e x e c u t a b l es t a t e m e n t s e x c e p t i o n e x c e p t i o n s t a t e m e n t s e n d p l s 吼块中的每一条语句都必须以分号结柬，s q i 。语句可以使多行的。但分 号表示该语句的结束。一行中可以有多条s o l 语句，他们之间以分号分隔。每一 个p l s q l 块由b e g i