利用LEX和YACC实现对SQL查询语句的语法分析


收稿日期 :2004 04 26 作者简介 :孙兵(1971 ) ,男 ,江苏南通人 ,江苏省教育厅信息中心统计师 ,南京航空航天大学信息科学与技术学院 2003 级硕士研究生。 文章编号 :1671 4644(2004) 03 0016 04 利用 LEX 和 YACC 实现对 SQL 查询语句的语法分析 孙  兵 (江苏省教育厅  信息中心 , 江苏  南京  210024) 摘  要 :介绍了 LEX、YACC 的基本工作原理 ,给出了 SQL 查询语句的 BNF 范式 ,利用这两个工具实现了对 SQL 查询 语句的词法分析和语法分析 ,并生成语法分析树。 关键词 :LEX; YACC;词法分析 ;语法分析 ;SQL ;巴科斯范式 中图分类号 :TP314   文献标识码 :A 引言 高级语言编译程序是计算机系统软件的重要组 成部分 ,构造一个好的高级语言编译程序的基础是 要对输入的单词符号进行词法分析 ,核心是要根据 词法分析结果进行语法分析 ,整个编译过程类似于 英文翻译。 LEX 与 YACC 是 UNIX 系统所提供的词法分析 工具和语法分析工具 ,人们经常使用这两个工具来 生成词法和语法分析器 ,生成好的编译程序 ,缩短开 发系统软件的周期 ,节约时间 ,提高工作效率。本文 详细讨论 LEX 与 YACC 的基本工作原理 ,并针对 SQL 语句中核心语句(SELECT语句) ,写出其 BNF 范 式 ,利用这两个工具实现词法、语法分析 ,并生成语 法树。 1  LEX、YACC 的基本原理与应用 1. 1  LEX 的基本原理与应用 1. 1. 1  LEX 的基本原理 UNIX 系统中的 LEX 词法分析工具是根据正规 式和确定有限状态自动机原理 (DFA) ,对所输入的 一些字符进行线性扫描分析 ,产生一个个单词符号 , 并返回单词符号的类型码。一个确定有限状态自动 机 M 是一个五元组 M = ( S , ∑, δ, S0 , F) , 其 中 : (1) S 是一个由有限个状态组成的集合; (2) ∑是一个有穷字母集 ,它的每个元素称为 输入字符; (3) δ是一个从 SX ∑至 S 的单值部分映射 ,如 δ( s , a) = S′,其中 s ∈S , a ∈ ∑,意味着当现在 状态为 s ,输入字符为 a 时 ,将转换到状态 S′; (4) S0 ∈S 为初始状态; (5) F ∈S 是一个终止状态。 有限自动机对输入的字符进行扫描 ,根据读入 进行状态转移 ,从而分析出所有单词符号 ,可以看出 用 LEX 进行词法分析 ,只是一种线性、简单地分析。 1. 1. 2  LEX 的简单应用 用 LEX 工具生成词法分析器 ,首先要写出其输 入文件 ,经过 LEX 编译程序生成词法分析器 ,然后 利用所生成的词法分析器对所输入的串进行词法分 析 ,输出单词符号和类型码 ,供 YACC 使用。 LEX 输入文件的格式为 : %{ 定义部分 %} %% 词法规则部分 %% 子程序部分 其中定义部分主要包含了一些头文件、单词符 号的属性值等 ;词法规则部分是 LEX 输入文件的主 体部分 ,主要是利用正则表达式的规则定义一些单 第 4 卷第 3 期 2004 年 9 月 南 京 工 业 职 业 技 术 学 院 学 报 Journal of Nanjing Institute of Industry Technology Vol. 4 ,No. 3 Sep. ,2004 词符号 ,返回单词类型号 ,通过向全局变量 yylval 赋 值 ,往值栈填单词值。子程序部分可以写一些 C 语 言的程序。 1. 2  YACC 的基本原理与应用 1. 2. 1  YACC 的基本本原理 从字面上理解 YACC 是一个编译程序的编译程 序 ,但严格说它不是编译程序自动产生器 ,它不能产 生一个完整的编译程序。YACC 根据上下文无关文 法产生式 ,即 BNF 范式 ,利用自下而上的语法分析 方法 ,自动构造一个语法分析器 ,能够利用 LEX 词 法分析的结果 ,将匹配的表达式转化后放到堆栈。 词法分析是一种简单、线性分析 ,而语法分析是一种 层次结构的分析。 1. 2. 2  YACC 的简单应用 用 YACC 工具来生成语法分析器 ,首先要根据 BNF 范式编写 YACC 的输入程序 ,然后经过 YACC 程 序 ,生成语法分析器 ,最后利用词法分析工具 ,通过 调用 yylex(),进行词法分析的同时 ,进行语法分析和 生成语法树。 YACC 输入文件的格式为 : 定义部分 %% 语法规则部分(BNF 范式) %% 子程序部分 其中定义部分主要包括一些头文件的说明 ,开 始符、终结符的说明等等。语法规则部分是 YACC 输入文件的核心部分 ,它直接关系到语法规则的定 义 ,其格式采用 BNF 范式。子程序部分主要是要编 写一些 C 程序可以供动作调用 ,另外还提供一个语 法分析控制器 yyparse (),该程序是语法分析的入口。 1. 3  LEX、YACC 的配合使用 LEX与 YACC 分别是词法分析器、语法分析器 的自动生成工具 ,它们既可单独使用 ,也可以配合使 用 ,本文主要是介绍二者配合使用对 SELECT 语句 进行词、语法分析。下面就在实际过程中所遇到的 问题 ,提出了几点需要注意的地方。 (1) 在 LEX 输入文件的定义部分必须要定义词 法分析结束符 ,且属性值必须要小于 0。 (2) 为了能够正确得生成语法树 ,必须要对终 结符、非终结符进行类型的说明。 (3) 各单词符号的属性值定义必须要大于 256 , 且 YACC 输入文件中定义的属性值 ,不要在 LEX 中 重复定义 ,只要在 LEX 输入文件的定义部分加上 # include“y. tab. h”即可实现调用。 (4) 在 YACC 输入文件的子程序中必须要调用 yyparse (),它调用词法分析器 yylex(),来实现词法分 析的同时 ,进行语法分析。 2  利用 LEX、YACC 对查询语句进行 词和语法分析   利用 LEX 和 YACC 来进行词、语法分析的一般 步骤为 :对语句分析、写出 LEX 和 YACC 的输入文 件、运行调试。 2. 1  对 SELECT语句分析 在 SQL 中 SELECT语句的一般格式为 : SELECT字段名[,字段名 ] ⋯FROM 表名或视图 名[,表名或视图名]WHERE 条件表达式 2. 1. 1  先确定查询语句中单词符号的分类 关键字 :SELECT FROM WHERE  运算符 : + - 3 / AND OR 常数、表名、字段名、变量名、字符串 界符 :,(  ) 语句结束符 ; 根据以上单词符号的分类确定语法树的节点类 型 ,哪些为中间结点 ,哪些可为叶结点。 2. 1. 2  写出 BNF 范式 query: SELECT fiel-list FROM form-list WHERE clause fiel-list : fiel-list‘,’fiel-name| fiel-name| ‘3 ’; fiel-name : ID| FID; form-list : form-list‘,’form-name| form-name ; form-name : ID; clause : clause AND clause | clause OR clause | clause-express| ‘(′clause′) ’; clause-express : element compopera element ; element : element mathopera element| element1|‘( ′ element′) ’; compopera :‘< ’|‘> ’|‘= ’|‘> = ’|‘< = ’; mathopera :‘+ ’|‘- ’|‘3 ’|‘/ ’; element1 : ID| ICON| FID|‘″’STRI‘″’; 2. 2  编写输入文件 2. 2. 1  LEX 的输入文件 以下给出简要的 LEX 输入程序 , 取名为 sql- scanner. l (必须要以 l 结尾) 。 %{ 71第 4 卷第 3 期   孙兵 :利用 LEX和 YACC 实现对 SQL 查询语句的语法分析 ⋯⋯ # define ENDMARK - 10  / 3 定义扫描结束符 的类型值 3 / # include ″y. tab. h″ %} digit [029 ] alpha [a2zA2Z] alnum {a2zA2Z029} %% SELECT {yylval. str = yytext ;return(SELECT) ;} “;”{yylval. str = yytext ; return ( ENDMARK) ;}/ 3 ;为结束符 3 / ⋯⋯ {alpha } { alnum} 3 { yylval. str = yytext ; return (ID) ;}/ 3 变量名或字段各 3 / {digit} +   {yylval. str = yytext ;return( ICON) ;} / 3 常数 3 / {alpha}{alnum} 3 [ . ]{alpha}{alnum} 3 {yylval. str = yytext ;return(FID) ;} / 3 带表或视图名的字段名 3 / {alnum} + {yylval. str = yytext ;return(STRI) ;}/ 3 字符串 3 / [/ t/ n ] ; / 3 去除空格、制表符和换行 3 / %% 2. 2. 2  YACC 的输入文件 因为语法树是在对语句进行语法分析的同时生 成的 ,所以在 YACC 输入文件中必须要确定语法树 的结构、生成结点程序以及单词符号、植栈结构的说 明。值栈定义方法为 %union {   char 3 str ;   struct sstree 3 sstr ;} 其中 str 为指向字符缓存的指针 ,sstr 是指向语 法树结构的指针。 语法树结点结构 : 结点类型 结点字符 左指针 中间指针 右指针   struct sstree { int ss-type ; char 3 ss-char ; struct sstree 3 ss-left ; struct sstree 3 ss-mid ; struct sstree 3 ss-right ; } 生成语法树结点的子程序如下 : struct sstree 3 builtnode (sstype , sschar , ssleft , ss2 mid , ssright) int sstype ; char 3 sschar ; struct sstree 3 ssleft , 3 ssmid , 3 ssright ; {   struct sstree 3 sspoint ;   sspoint = (struct sstree 3 ) malloc (sizeof (struct sstree));   if (sspoint = = NULL) yyerror();   sspoint - > ss-char = sschar ;   sspoint - > ss-type = sstype ;   sspoint - > ss-left = ssleft ;   sspoint - > ss-mid = ssmid ;   sspoint - > ss-right = ssright ;   return(sspoint) ; } 然后利用查询语句的 BNF 范式和调用语法树 结点生成子程序 ,即可很方便的编写出 YACC 的输 入程序 ,取名为 sql-yacc. y ,即可实现语法分析的同 时生成语法树。在动作集中调用生成语法树结点子 程序时要利用伪变量 ,举例如下 : query : SELECT fiel-list FROM form-list WHERE clause   { $$ = builtnode (1 , ″query″, $2 , $4 , $6) ;}; 2. 3  运行调试 LEX、YACC 的输入程序编完后 ,就可在 UNIX 环境下编译运行 ,直到没错误为止 ,过程如下 : lex sql- scanner. l yacc - d sql-yacc. y gcc - o sqlyacc y. tab. c lex. yy. c - ll sqlyacc 3  结语 本文讨论了 YACC 和 LEX 的基本工作原理以及 如何利用这两个有效的工具实现对 SELECT 语句的 语法分析 ,并生成语法树 ,但真正要利用这两个工 具 ,来构造一个实用高效的 SQL 编译器 ,还有很多细 节要考虑 ,包括对 SQL 子集的详细分析、二义性的处 81  南京工业职业技术学院学报 第 4 卷第 3 期 理、语法树的优化等。 参考文献 : [1 ] 陈火旺等. 程序设计语言编译原理[M]. 北京 :国防科技 大学出版社 ,2000. [2 ] 史杏荣等. 编译程序设计原理与构造技术[M]. 合肥 :中 国科学技术大学出版社 ,1998. [3 ] 萨师煊 ,王珊. 数据库系统概论 (第三版) [M]. 北京 :高等 教育出版社 ,2000. Syntax Analysis of SQL Select Sentence through Using LEX and YACC SUN Bing ( Education Department of Jiangsu Province , Nanjing 210024 , China) Abstract : This paper mainly presents the principles of LEX and YACC and gives the BNF of select sentence. Using these tools ,we can implement the lexical and syntax analysis of SQL select sentence and generate the syntax analysis tree. Key words : LEX; YACC ; lexical analysis ; syntax analysis ; SQL ; BNF (责任编辑  周  源) (上接第 12 页) Calculating an Assembly Dimension Chain by Coordination Method XU Xiu - juan , DONGJi - xian ( Shanxi University of Science & Technology , Xianyang 712000 , China) Abstract : The method of calculating an assembly chain by the relative tolerance zone is discussed. Disposing the optimum location of a relative tolerance zone of the closed dimension can simplify the adjustment process of an assembly production. Key words : dimension chain ; closed link ; relative tolerance zone (责任编辑  陈晓润) 91第 4 卷第 3 期   孙兵 :利用 LEX和 YACC 实现对 SQL 查询语句的语法分析
还剩3页未读

继续阅读

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

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

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

下载pdf

pdf贡献者

hwl86

贡献于2011-05-19

下载需要 15 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf