基于JavaCC的SQL编译器的设计与实现


邮局订阅号:82-946 360 元 / 年 技 术 创 新 软 件 时 空 《PLC 技术应用 200 例》 您的论文得到两院院士关注 基于 JavaCC 的 SQL 编译器的设计与实现 Design and implementation of SQL compiler based on JavaCC (暨南大学) 闫 静 王联辉 YAN Jing WANG Lian-hui 摘要: 采用扩展的巴科斯范式(EBNF)定 义 SQL 语言的语法规则,提出了一种基于分析器自动生成工具(JavaCC)的 SQL 语 言 编 译 器 的 设 计 模 型 。 该 模 型 采 用 Java 语 言 开 发,具有良好的平台无关性;分 别 从 词 法 、语法和语义分析、信息提取等方面进行编 译器的设计与实现。 实际运行结果表明:该模型能够快速高效地构建 SQL 编 译 器,且具有良好的可扩展性。 关键词: SQL 编译器; 扩展的巴科斯范式; JavaCC 中图分类号: TP312 文献标识码:A Abstract: A design model of SQL complier based on a parser generator (JavaCC) was presented, which adopted the Extended Backus Naur Form (EBNF) to define the SQL syntax rule. The model was implemented with Java language, which can make it independent of operating system. The design and implementation of compiler were described from different aspects: lexical analysis, syntax and se- mantic analysis, information draws and so on. The practical results show that the model can construct the compiler prototype quickly and efficiently, and can be expanded easily. Key words: SQL compiler; Extended Backus Naur Form (EBNF); JavaCC 文章编号:1008-0570(2010)05-3-0195-02 引言 SQL 语言作为关系数据库的标准语言, 已经获得了广泛的 应用。 各个数据库厂家纷纷推出了自己的 SQL 接口,使得不同 数据库系统之间的互操作有了共同的基础。 随着数据库的应用 范围的逐步扩大,仅仅依靠 DBMS 自带的 SQL 解析器已经不能 满足大量应用的需求。例如在分布式的信息集成应用中,需要为 用户透明访问异构数据源提供一个统一的接口, 所以异构信息 集成系统必须对全局查询进行合法性检查,而对 SQL 语言的语 法语义分析就是一个关键的环节。 如何开发一个通用的功能完 善的 SQL 编译器已经成为此类应用的共同需求。 手工开发 SQL 查询编译器,需要对每个词法、语法、语义规 则编写相应的处理程序, 工作量大,开发周期长,维护非常困难。 使用 SUN 公司的分析器自动生成器工具 JavaCC 构 造 SQL 编 译器,可以通过修改脚本来扩展编译器的规则,且具有平台无关 性的特点。 本文通过研究 JavaCC 的使用方法实现了一个高效 的 SQL 编译器。 1 分析器自动生成器 JavaCC 的介绍 为了简化基于 Java 语言的词法分析器或者语法分析器的 开发,Sun 公司的开发人员开发了 JavaCC (Java Compiler Compil- er)。 用户只要按照 JavaCC 的语法规范编写源文件, 然后使用 JavaCC 编译器编译,就能够生成基于 Java 语言的某种特定语言 (例如 SQL 语言) 的分析器。 与 LEX,YACC 等其他生成工具相 比,JavaCC 有以下特点:(1)使用 LL(k)递归下降的语法分析方法, 文法规则表达能力强、直观、易于调试;(2) 词法、语法规则都定 义在同一个文件中, 易于阅读和维护;(3) 提供功能强大的建立 分析树的预处理器 JJTree,提供树和结点类,易于将代码分成单 离的解析和动作类;(4) 可以定制生成语法词法分析器的行为, 是否对大小写敏感等;(5) 提供独特的语法向前看和语义向前看 规则来解决移进冲突。 2 JavaCC 的使用方法和步骤 首先,用户创建一个称为语法文件的文本文件(.jjt 文件),将 自定义的词法分析器和语法分析器的规则写到里面, 然后通过 JJTree 编译成 .jj 文件,由 javaCC 读取其中的规则来生成相应的 词法分析器和语法分析器的程序。利用生成的词法分析器,先将 输入的字符流转换成由记号组成的流, 再作为语法分析器的输 入,从而得出最终的结果———抽象语法树。其中定义规则的步骤 如下:(1) 编写正则表达式来表示 SQL 语言的词法结构;(2) 根据 JavaCC 的词法规则改写(1)中的正则表达式。 同时将需要忽略的 正则表达式定义为 SKIP 类型,如空白符,注释等。 将有用的正则 表达式定义为 TOKEN 类型,如数字,标识符等;(3)编写 BNF 产生 式和 EBNF 产生式来描述 SQL 语言的语法结构。 为了生成高效 的可 靠 的分 析 器, 应 该 尽 量 使 用 EBNF 描 述 语 法 结 构 。 由 于 JavaCC 生成的编译器本质上是递归下降的,所以编写的语法产 生式要消除左递归以避免死循环;(4)根据 JavaCC 的语法改写(3) 中的语法产生式。 在 JavaCC 中,每一个非终结符最终都被定义 为一个类似于函数的形式, 最终经过 JavaCC 编译器编译后,每 一个终结符都会转变为 SQL 编译器中的一个方法;(5)为每一个 产生式添加语义动作。 当编写的产生式不是 LL (1)文法时,需要 使用 LOOKHEAD 设置来辅助分析器选择正确的产生式;(6) 使 用 JavaCC 的语法规则优化产生式。 3 SQL 编译器的体系结构 SQL 编译器的主要工作概括起来有两个: 检错和翻译。 检 错,即按照 SQL 语言的规范进行词法分析、语法分析、语义分析, 从而检查出 SQL 语句的词法错误、语法错误、语义错误。 如顺利闫 静: 硕士研究生 195-- 技 术 创 新 《微计算机信息》(管控一体化)2010 年第 26 卷第 5-3 期 360元 / 年 邮局订阅号:82-946 《现场总线技术应用 200 例》 软 件 时 空 经过检错阶段,则进入翻译阶段,即在生成的抽象语法树基础上 提取相关信息进行重写。 根据以上对 SQL 编译器主要工作的分析,本系统的体系结 构如下图所示: 图 1 SQL 编译器的体系结构 词法分析模块 词法分析的主要功能是将输入的 SQL 语句由字符串序列 分解为记号序列并检查是否有出现非法字符。 SQL 语句的记号 有以下三种:关键字,符号以及用户定义的标识符、常量。其中,关 键 字 代 表 SQL 语 言 中 有 特 殊 意 义 的 词 , 如 SELECT,FROM, WHERE 等。 符号包括比较符号 ("=""<>""<"">""<= " " > = "),运算符号(" + " " - " " * " " / "),分隔符(" , " " ( " ")" " ; "), 这些记号在 JavaCC 源文件的 TOKEN 区域内直接定义。 至于空格符,回车符,换行符则在 SKIP 区域内定义,在接下来的 语法分析过程中被忽略。 标识符代表以字母开头的由字母和数 字组成的符号序列,在 SQL 语句中,它能表示表名、列名、模块名 等;常量包括字符串常量、整数、实数。标识符和常量都用正则表 达式来描述,在 JavaCC 源文件中表示为以下形式: 语法分析模块 语法分析的主要功能是判断词法分析产生的记号序列是 否合乎 SQL 语法。 SQL 语法用 EBNF 文法来定义, 语法分析的 过程就是从文法的开始符号出发,按照文法的产生式,识别输入 的记号序列是否是一个句子, 在识别的过程中建立语法树。 以 SQL 查询语句为例,EBNF 文法对应的 JavaCC 语法产生式如下 所示: 语法产生式“:”的左端 void Query( )声 明 了 一个 非 终 结符, 表达形式类似 Java 中对方法的声明, 允许有返 回 值和 输 入 参 数。JavaCC 在由此生成的语法分析器类中会为每个非终结符定 义一个同名的方法。“:”右端的第一对{}用来编写可选的 Java 代 码块, 这些代码会被插入在生成的语法分析器中同名方法的起 始处。 这样,在分析过程中每当调用该非终结符时,都会执行这 些 代 码。“:”右 端 的 第 二 对{}定 义 了 文 法 的 产 生 式,其 中 "SE- LECT"、 "ALL"等代表终结符,SelectList()、FromClause()等代表非 终结符,其写法如同方法调用,可以有输入参数。 在对 Query()的 产生式进行分析的过程中,首先匹配终结符"SELECT",然后匹配 []中的可选项,接下 来 调用 非 终 结符 SelectList()、FromClause()对 应的同名方法进行匹配。 而对 where 子句、group 子句以及 order 子句的分析是可选的。 在每个终结符或非终结符后可以插入用 于执行语义动作的 Java 代码,例如当指令和语法规则不匹配时 进行出错处理,保存终结符/非终结符的返回值,将返回值存入符 号表等。 语义分析模块 语义分析模块的主要功能是检查 SQL 语句中表名,属性名 的合法性以及类型推断和检查。 通过在语法产生式的每个终结 符或非终结符后插入 Java 代码, 以执行语义动作。 当指令和语 义规则不匹配时进行出错处理, 如 保 存 终结 符/非 终结 符 的 返 回值,释放创建的语法树结点。 以下示例为检查 INSERT 语句中 的表名是否存在的语义分析动作: 信息提取 将以上定义了词法语法语义规则的 JavaCC 源文件(以 Sql- Parser.jj 为例)交由 JavaCC 编译,如果没有发现文法错误,则产生 以下源程序:SqlParser.java (语法分析器),SqlParserTokenManager. java(词法分析器),TokenMgrError.java(错误处理程序), Token. ja- va (记号信息)、SqlParserConstants.java (定义分析器中使用的常 量)、SimpleCharStream.java (字 符流 类)、ParseException.java(可 恢 复异常, 解析器发现问题时抛出)、Node.java (语法树结点接口 类)、SimpleNode.java(语法树中所有结点的父类)。 其中 SqlParser.java 为 SQL 编译器的主类,SQL 语句经过编 译后不再是符号序列, 而是生成一棵由结点对象构成的抽象语 法树。 为了提取 SQL 语句中的有用信息(如查询语句的投影字 段,选择条件等),就需要对抽象语法树进行遍历。 在遍历过程中, 可能涉及到多个操作, 这些操作大多要求对不同的结点进行不 同的处理。 如果将所有这些操作分散到各个不同结点类中会导 致整个系统难以理解和难以维护。 为了提高扩展性,采用 访 问 者(Visitor) 模 式,将 针对 每 一 个 结点的同类操作封装在一个独立的对象 Visitor 中,并在遍历抽 象语法树时,将此 Visitor 对象传递给当前访问的结点,当一个结 点接受该访问者时, 该结点向访问者发送一个包含自身类信息 的请求,同时将该结点对象作为参数传递,然后访问者将对该结 点执行某一特定类型的操作。 具体实现如下: (下转第 234 页) 196-- 技 术 创 新 《微计算机信息》(管控一体化)2010 年第 26 卷第 5-3 期 360元 / 年 邮局订阅号:82-946 《现场总线技术应用 200 例》 软 件 时 空 ....... } AdvancedUser.NearUse 该语句的含义是获取配置文件中 id 为 AdvancedUser 的属性 NearUse 的值。 所有高级用户的权限控 制部分都依赖于配置文件中的 id="AdvancedUser" 组件相关属 性的值,其它角色的用户同理。 这种方式实现了由 IOC 外部容 器也就是配置文件来控制权限的功能, 可以根据需要在配置文 件中修改某个角色的某一权限。这样不仅提高了代码的可读性, 还为以后权限的修改带来了极大的便利。 图 3 IOC 权限控制原理 4 结论 本文介绍了 RBAC 和 IOC 这两种技术的基本概念和原理, 结合车辆管理系统的高级用户的权限控制, 给出了利用 RBAC 和 IOC 技术设计权限控制的思路。 通过实践论证:采用这两种 技术不仅使得代码层次清晰, 还大大提高了代码的可读性和可 维护性。 是以后做 MIS 系统中的权限管理的参考模型。 本文作者创新点: 本文采取了 RBAC 和 IOC 这两种技术结 合的方式实现权限的控制。 IOC 技术实现权限控制本身并不多 见。 而本文又结合了 RBAC,体现出了更多的灵活性和针对性。 参考文献 [1]胡博,陈佳。基于 ASP.NET 的用户权限管理的实现----以水 利水电 WEB 查询系统为例[J].2008.20(1):120-127 [2]马林,黄文培,聂捷楠,汪凌峰,RBAC 的权限扩展和其在 Acegi 下的实现[J] .微计算机信息.2008,2-3:34-36 [3]罗时灼.精通 Spring[M].北京:电子工业出版社,2005. 作者简介:杨扬(1982-),女(汉族),河南郑州,毕业于武汉理工大学 计算机学院,硕士,现就职于河南省电力通信自动化公司。 主要 研究智能电网、企业信息化。 Biography:YANG Yang (1982 - ), female, (the Han nationality), ZhengZhou, graduated from Wuhan University of Technology, Master, now working in HenNan Electric Power Communica- tion&Automation Company and mainly engaged in smartgrid, en- terprise information. (450002 河南郑州 河南省电力通信自动化公司) 杨 扬 李 雄 (HeNan Electric Power Communication & Automation Company ZhengZhou HeNan 450052 , China ) YANG Yang LI Xiong 通讯地址:(450052 郑州市嵩山南路 87 号河南省电力通信自动 化公司) 杨 扬 (收稿日期:2009.06.10)(修稿日期:2009.09.10) (上接第 196 页) 这样,在遍历语法树的过程中,可以通过实现 AbstractVisitor 接口为每一个特定类型的操作实现一个访问者类, 将针对特定 结点的不同操作区分开来。 4 结束语 在研究 JavaCC 分析器自动生成工具的基础上, 通过 EBNF 定义 SQL 语言的词法语法语义规则,快速地构建了一个通用的 SQL 编译器,具有良好的系统扩展性。 本文作者创新点:遍历抽 象语法树的过程中使用访问者模式进行信息提取, 有效地将针 对不同结点的不同类型的操作区分开来, 有利于系统的维护和 二次开发。 参考文献 [1]阎宏. Java 与模式[M]. 北京:电子工业出版社,2002:946-957. [2]Sun o’reilly. The document of javacc [EB/ OL]. 2005 - 04 -10. http :/ / javacc. dev. java. net/ doc/ CharStream. html. [3]谢运佳, 王会进, 钟瑞琼等. 一种轻量级的 J2EE 解决方案及其 应用[J]. 微计算机信息, 2006, 3-3: 223-225. 作者简介:闫静(1984-),女(汉),硕士研究生,研究方向为信息集成和 网格计算;王联辉(1984-),男(汉),硕士研究生,研究方向为数据库。 Biography:YAN Jing(1984-), female(the Han nationality), Master, research directions are information integration and grid computing. (510632 广州 暨南大学计算机系) 闫 静 王联辉 通讯 地 址:(510632 广 州 市 黄埔 大 道 西 601 号 暨 南 大学 真 如 B 南学生宿舍 5830 室) 闫 静 (收稿日期:2009.06.17)(修稿日期:2009.09.17) (上接第 221 页) 作者简介:陈品华(1973-),男(汉族),浙江金华人,上海行健职业学 院讲师,硕士,主要研究方向是计算机软件和计算机网络; 石林 祥,上海第二工业大学,副教授,硕士研究生; 卢周成,百脑汇电子 信息有限公司(杭州),工程师,学士。 Biography:CHEN Pin -hua, Male, Born in 1973, Shanghai, Shanghai Xingjian College, Lecturer, Research area: Software engineering、Computer network. (200072 上海 上海行健职业学院) 陈品华 (201209 上海 上海第二工业大学) 石林祥 (310013 杭州 百脑汇电子信息有限公司) 卢周成 (Shanghai Xingjian College, Shanghai, 200072, China) CHEN Pin-hua (Shanghai Second Polytechnic University, Shanghai, 201209, China) SHI Lin-xiang (Buynow Electronic Information Co., Ltd.,Hangzhou,310013, China) LU Zhou-cheng 通讯 地 址:(200072 上 海 市 闸 北 区 大 宁 路 540 弄 27 号 201 室) 陈品华 (收稿日期:2010.02.12)(修稿日期:2010.05.12) 234--
还剩2页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 3 人已下载

下载pdf