1、1/ 52从 lex&yacc 说到编译器（1.正则表达 式作者：tangl_99:msn:ta ngl_b5E2RGbCAPemail: tangl_p1EanqFDPw学过编译原理的朋友肯定都接触过LEX 这个小型的词法扫描工具.但是却很少有人真正把LEX 用在自己的程序里.在构造专业的编译器的时候，常常需要使用到 lex 和 yacc.正是因为这两个工具,使得我们编写编译器,解释器等工具的时候工作变得非常简单.不过话说回来，会使用 lex和 yacc 的人也确实不简单.Lex 和 yacc 里面牵涉到一系列的编译原理的理论知识，不是简单地看看书就能搞懂的.本文只是简单地
2、介绍一下lex 和 yacc 的使用方法.相关编译理请查看本科教材.DXDiTa9E3d国内大学教材里面对于lex 和 yacc 的介绍很少，有些根本就没有，不过在国外的编译原理教材介绍了很多.按照学科的分类，国内大学本科里面开的 教程只是讲解编译的原理,并不讲解实践.而对于实践方面则是另外一门学科.关于编译技术的书籍在国内是少之又少.前不久，听说上海交大的计科内部岀版过编译技术的教材.可惜我们这些人就无法得见了 .还好，机械工业岀版社引进了美国Kenneth C.Louden所著的经典著作 中，比较详细地介绍 lex 和 yacc 的使用.RTCrpUDGiTLex 属于 GNU 内部的工具
3、，它通常都是 gcc 的附带工具.如果你使用的 Linux 操作系统，那 么肯定系统本身就有lex 和 yacc,不过 yacc 的名字变成了 bis on.如果你使用的 Win dows 操作系统,那么可以到 cygwin 或者 GNUPro 里面找得到.网上也有 windows 版本 lex 和 yacc,大家可以 自己去找一找 .5PCzVD7HxA本文一共有两篇，一篇是介绍 lex,另一篇是介绍 yacc. Lex 和 yacc 搭配使用，我们构造自己 的编译器或者解释器就如同儿戏.所以我把本文的名字叫做黄金组合.jLBHrnAlLg本文以 flex（ Fase Lex 为例 , 两讲
4、解如何构造扫描程序 .Flex 可以通过一个输入文件 ,然后生成扫描器的 C 源代码2/ 52其实扫描程序并不只用于编译器 . 比如编写游戏的脚本引擎的时候 ,我看到很多开发者都是 自己写的扫描器 ,其算法相当落后 （完全没有 DFA 的概念化 , 甚至很多脚本引擎开发者的词法扫 描器都没有编写 ,而是在运行过程中寻找 token（ 单词 . 在现代的计算机速度确实可以上小型的 脚本引擎在运行中进行词法扫描 , 但是作为一个合格的程序员 , 或者说一个合格的计算机本科毕 业生而来说 , 能够运用编译原理与技术实践,应该是个基本要求 .xHAQX74J0X如果要说到词法分析的扫描器源代码编写 ,
5、 其实也很简单 , 会 C 语言的人都会写 . 可是 Kenneth Louden 在 里面 ,花了 50 多页 ,原因就是从理论角度 , 介绍标准的 ,可 扩展的,高效的词法扫描器的编写.里面从正则表达式介绍到DFA（有穷自动机 ,再到 NFA（非确定性有穷自动机 , 最后才到代码的编写 . 以自动机原理编译扫描器的方法基本上就是现在词法 扫描器的标准方法 ,也就是 Lex 使用的方法 . 在 Lex 中,我们甚至不需要自己构造词法的 DFA, 我 们只需要把相应的正则表达式输入，然后 lex 能够为我们自己生成DFA,然后生成源代码，可谓方便之极 .LDAYtRyKfE本文不讲 DFA,
6、lex 的输入是正则表达式 , 我们直接先看看正则表达式方面知识就可以了1. 正则表达式 (regular expression:对于学过编译原理的朋友来说,这一节完全可以不看.不过有些东西还是得注意一下,因为在flex 中的正则表达式的使用有些具体的问题是在我们的课本上没有说明的.Zzz6ZB2Ltk先看看例子 :例1.1nameTangl_99这就是定义了 name 这个正则表达式 ,它就等于字符串 Tangl_99. 所以,如果你的源程序中 出现了 Tangl_99 这个字符传 ,那么它就等于出现一次 name 正则表达式 .dvzfvkwMI1例1.2digit 0|1|2|3|4|5
7、|6|7|8|9这个表达式就是说，正则表达式 digit就是 0,1,2,9中的某一个字母.所以无论是 0,2,或者 是 9都是属于 digit这个正则表达式的.rqyn14ZNXI“ 符| ”号表示 ”或者 ”的意思 .那么定义正则表达式 name Tangl_99|Running, 同样的 ,如果你的源程序中出现了 Tangl_99 或者 Running, 那3/ 52么就等于出现了一次 name 正则表达式 .EmxvxOtOco例1.3one1*“ *符”号表示 ”零到无限次重复 ”那么 one 所表示的字符串就可以是空串（什么字符都没有 , 1, 11, 111, 11111,111
8、, 等等.总之,one 就是由 0 个或者 N 个 1 所组成（N 可以为任意自然数 .SixE2yXPq5与”*”相同的有个 ”+”符号 .请看下面的例子 1.4例1.4realone1+“ +符”号表示”1到无限次重复 ”那么 realone 和 one 不同的唯一一点就是 ,realone 不包含空串 ,因为 ”+”表示至少一次重复 那么 realone至少有一个 1.所以 realone 所表达的字符串就是 1,11,111, 1111, 11111，等等 .6ewMyirQFL例1.5digit0-9lettera-zA-Z这里的digit 等于例 1
9、.2 中的 digit, 也就是说 ,a|b|c 就相当于 a-c.同理letter 也就是相当于 a|b|c|d|e|f| |y|z|A|B|C|D |Z 不过注意的一点就是，你不能把letter 写成 A-z, 而必须大写和小写都应该各自写出来.kavU42VRUs例1.6notAFA“ 表示非，也就是除了这个字符以外的所有字符4/ 52所以 notA 表示的就是除了 A 以外的所有字符 .下面让我们来看看一些一般高级程序语言中常用的综合例子.digit0-9numberdigit+lettera-zA-Z_digit 前面多次提起过 ,就是 0-9 的阿拉伯数字 .number 就是所有
10、的数字组合,也就是整数 .Letter 前面也提起过 ,唯一不同的就是多了一个下划线 .因为一般我们的 C 语言中容许有下 划线来表示定义的变量名 ,所以我也把下划线当成英语字母来处理了.y6v3ALoS89这里 number 中使用上面定义的digit 正则表达式.在 lex 中，用digit就是表示正则表达式digit.M2ub6vSTnPnewlinenwhitespace t+newline 就是提行的意思.这里我们使用的是n 这个符号，它和 C 语言中表示提行号一致.问 题是大家可能要问到为什么要使用符号.因为在 lex 中，如果你使用,那么里面表示的肯定就是单个字符号，而不会被理解
11、成” ”和” n 两个字符.OYujCfmUCwWhitespace 就是空格符号的意思 .一般的高级程序语言中有两种 ,一种就是简单的空格 ,还 有一种就是 t 制表符 .使用了 两+两符号 ,就表示了这些空白符号的无限组合.eUts8ZQVRd从 lex&yacc 说到编译器 (2.flex 的使用 作者：tangl_99:msn:tan gl_sQsAEJkW5Temail:ta ngl_GMsiasNXkA看了第一篇的关于正则表达式的说明后，下面我们就来通过它，使用 flex 这个词法分析工具来构造我们的编译器的词法分析器.TlrRGchYzg5/ 52关于 lex
12、的教程应该是很多，这里我就简单地介绍一下，然后着重后面的 lex 和 yacc 的配合使用以及其技巧.所以,如果你不看了后还是不太明白lex 或者 yacc 的使用，请你自己上网去查查,这方面的教程是很多的.我知道的一篇常见的就是7EqZcWLZNXYacc 与 Lex 快速入门 Lex 与 Yacc 介绍它的作者就是 Ashish Ban sal.Flex 就是 fast lex的意思.而 lex 就是 Lexical Analyzar的意思.flex 可以在 cygwin 或者 gnupro 中找到.它是 unix 的一个工具，属于 GNU 组织产品.网上也可以找到单独可以在 window
13、s 下用的版本.lzq7IGfO2E我们一般把我们的词法扫描程序要扫描的一些单词(token用正则表达式写好，然后作为lex 的输入文件，输入命令 flex xxx.l(xxx.l就是输入文件,lex 经过处理后，就能得到一个名字叫 lex.yy.c 的 C 源代码.这个 C 源代码文件，就是我们的词法扫描程序.通常 lex 为我们生成的词法分析器的C 源代码都是十分复杂而且庞大的，我们一般根本不会去查看里面的代码(放心好了 ,flex 这个东西不会岀错的zvpgeqJ1hk下面让我们看看几个我已经使用过的几个lex 输入文件.这是一个前段时间我为GBA 上的一个 RPG 游戏写的脚本弓 I
14、擎所使用的lex 输入文件(部分例 2.1%/* n eed this for the call to atof( below */#include #include #include #include globals.h%6/ 52digit0-9number(-|+?digit+hexnumber0 x(digit|a-fA-F+lettera-zA-Zidentifier(letter|_(number|letter|_*newlinenwhitespace t+stringA*comment#$#*#%string return VM_STRING 。 Logo return VMIN
15、_LOGO 。 FaceIn return VMIN_FACEIN 。 FaceOut return VMIN_FACEOUT 。 LoadTile return VMIN_LOAD_TILE 。 CreateRole return VMIN_CREATE_ROLE 。 ReleaseRole return VMIN_RELEASE_ROLE。 7/ 52whitespace /* skip whitespace */identifier return VM_IDnewline%int yywrap(return 1这里的 lex 输入文件一共有三个部分 , 用%分开. 第一部分中的 %和%中
16、的内容就是直接放 在 lex 输出 CCreateMap return VMIN_CREATE_MAPReleaseMAP return VMIN_RELEASE_MAP 。 ShowBitmap return VMIN_SHOWBITMAP 。CreateDialog return VMIN_CREATE_DIALOGReleaseDialog return VMIN_RELEASE_DIALOGFight return VMIN_FIGHTDelay return VMIN_DELAYPressA return VMIN_PRESS_APressB return VMIN_PRESS_BP
17、ressR return VMIN_PRESS_RPressL return VMIN_PRESS_LPressStart return VMIN_PRESS_STARTPressSelect return VMIN_PRESS_SELECTnumber return VM_NUMBER 。8/ 52代码中的顶部 . 我们通过它可以来定义一些所需要的宏 , 函数和 include 一些头文 件等等.我的这个 lex 输入文件中也没什么特别的东西，就是常规的 C 源文件的 in elude 头文件NrpoJac3v1%/* need this for the call to atof( belo
18、w */#include #include #include #include globals.h%第一部分中 , 除了前面的 %和 %包含的部分 , 下面的就是正则表达式的定义 .看了第一篇的正则表达式 , 这样你就能够在这里派上用场了 .让我们来看看我这里定义的正则表达式 :digit0-9number(-|+?digit+hexnumber0 x(digit|a-fA-F+lettera-zA-Zidentifier(letter|_(number|letter|_*newlinenwhitespace t+stri ng“A*comme nt#A#*#digit 就不用说了 , 就是
19、0-9 的阿拉伯数字定义 , 第一篇文章中也举了这个例子 .number 就 是 digit 的 1 到无限次的重复 ,再在其前面加上” +”和” -“符号 .1nowfTG4KI9/ 52“a”: 即使 a 是元字符 ,它仍是字符 aa: 当 a 是元字符时候 , 为字符 aa?: 一个可选的 a, 也就是说可以是 a, 也可以没有 aa|b: a 或 b(a: a 本身abc: 字符 a,b 或 c 中的任一个a-d: a,b,d 或者 d 中的任一个Fab:除了 a 或 b 外的任何一个字符.: 除了新行之外的任一个字符xxx:名字 xxx 表示的正则表达式这里需要特别说明的就是newl
20、ine nnewline 就是新行，这里我使用了 把n 换行号括起来.因为如果我直接用n 表示的话，那 么按照上面的规则 ,那就会看成 和 n 两个字符 , 所以我使用了 n. 有些时候 newline 也被写成 n|rn. 因为在文本文件中 , 一般换行一次 , 那么就是一个 n(0 xA, 可是在二进制文件中 , 换 行有时候又是 rn(0 xD,0 xA 一共两个字符号 .fjnFLDa5Zo第二部分就是定义扫描到正则表达式的动作 .这些动作其实就是C 代码，它们将会被镶嵌在 lex 输岀的 C 文件中的 yylex(函数中.上面的例子的动作其实十分平常 , 就是返回一个值 .我们在外部
java基础525讲解
21、使用这个lex 为我们生成 C 代码的时候，只需要使用它的 int yylex( 函数.当我们使用一次 yylex(,那么就会自动去扫描一个匹配的正则表达式，然后完成它相应的动作.这里的动作都是返回一值，那么 yylex 就会返回这个值.通常默认 yylex 返回 0 时候,表示文件扫描 结束,所以你的动作中最好不要返回0,以免发生冲突.当然,动作中也可以不返回一值，那么yylex 就会完成这个动作后自动扫描下一个可以被匹配的字符串，一直到扫描到文件结10/ 52束.tfnNhnE6e5当扫描到一个可以被匹配的字符串，那么这个时候，全局变量 yytext 就等于这个字符串请大家一定记住这些正则
22、表达式的顺序如果岀现一个字符串，可以同时匹配多个正则表达式，那么它将会被定义在前面的正则表达式匹配.所以我一般把字符串String 定义在最前面.HbmVN777sL如果文件中的字符没有被lex 输入文件中任何一个字符匹配，那么它会自动地被标准输岀所以大家一定要记住在每个正则表达式处理完毕后，一定要加上newline和.这两个正则表达式的动作.V7l4jRB8Hs好，让我们看看 lex 为我们输出 C 文件中提供一些常量Lex 变量yyinFILE*类型。 它指向 lexer正在解读的当前文件。yyoutFILE*类型。它指向记录 lexer 输岀的位置。缺省情况下，yyin和 yyout 都
23、指向标准输入和输岀。yytext匹配模式的文本存储在这一变量中vchar* )。yyle ng给岀匹配模式的长度。yyli neno提供当前的行数信息。vlexer 不一疋支持。)例 2.211/ 52这是编译原理与实践 书中配套的源代码的 lex 输入文件 . 大家可以参考 自己定义的一个 Tiny C 编译所做的词法扫描器 .83lcPA59W9%#include globals.h#include util.h#include scan.h/* lexeme of identifier or reserved word */char tokenStringMAXTOKENLEN+1 。%
24、digit0-9numberdigit+lettera-zA-Zidentifierletter+newlinen*mZkklkzaaP/* File:tiny.lAVktR43bpw/* Lex specification forTINY */ORjBnOwcEd/* Compiler Construction: Principles and Practice/* Kenneth C.Louden/*/*/2MiJTy0dTT*/uEh0U1YfmhgIiSpiue7A*/whitespace t+, 作者为它12/ 52%ifreturn IF 。 thenreturn THEN 。 el
25、sereturn ELSE 。 endreturn END 。 repeatreturn REPEAT 。 untilreturn UNTIL 。 readreturn READ 。 writereturn WRITE 。 I!_I!return ASSIGN 。 I! I!return EQ 。 return RPAREN 。 I!I! 。 return SEMI 。 numberreturn NUM 。 identifierreturn ID 。 newlinelineno+ 。 whitespace/* skip whitespace */13/ 52do c = input(。if (
26、c = EOF breakif (c = n lineno+ while (c != 。return ERROR 。 %TokenType getToken(void static int firstTime = TRUE。TokenType currentToken 。if (firstTime firstTime = FALSE 。lineno+ 。yyin = source 。yyout = listing 。currentToken = yylex( 。strncpy(tokenString,yytext,MAXTOKENLENif (TraceScan char c14/ 52fpr
27、intf(listing,t%d: ,lineno printToken(currentToken,tokenString 。return currentToken 。这里有点不同的就是 , 作者用了另外一个 getToken 函数来代替 yylex 作为外部输出函数 . 其中getToken 里面也使用了 lex 默认的输出函数 yylex(, 同时还做了一些其它的事情 . 不过我 建议大家不要像作者那样另外写自己的结果输出函数 , 因为在后面 , 需要和 yacc 搭配工作的时 候 ,yacc 生成的语法分析程序只认名字叫 yylex( 的词法结果输出函数 .IAg9qLsgBXif (f
28、irstTime firstTime = FALSE。lineno+ 。yyin = source 。yyout = listing 。其中的 yyin,yyout,source,listing 都是 FILE* 类型 .yyin 就是要 lex 生成的词法扫描程 序要扫描的文件 ,yyout 就是基本输出文件 ( 其实我们通常都不用 yyout, 即使要生成一些输出信 息 , 我们都是自己通过fprintf 来输出 .WwghWvVhPE char c 。do c = input( 。if (c = EOF break 。if (c = n lineno+ 。 while (c != 。其中
29、，作者的这个 Tiny C 是以来包括注释信息.作者并没有写岀注释信息的正则表达式 但是它可以通过检索“” ,然后用 lex 内部函数 input( 一检查后面的字符是不是来跳过注释文字.(C 语言的/* */注释文字正则表达式十分难写，所以很多时候我们都用这种方法15/ 52直接把它的 DFA(扫描自动机 写岀来.asfpsfpi4k本文就是通过简单地举岀两个比较实际的例子来讲解flex 输入文件的.再次说明，如果你是第一次接触 lex,那么请看看前面我推荐的文章，你可以在 IBM 的开发者网上查到.下一篇关于 yacc 于 BNF文法的说明也是如此.请大家先参考一下其它标准的教程.ooey
30、YZTjj12003-9-30从 lex&yacc 说到编译器（3.范式文法作者：tangl_99:msn: tan gl_BkeGu InkxIemail:ta ngl_PgdOOsRlMo从这一节开始，我们就算进入编译器构造的正题了.不得不说，前面的词法扫描器在整个编译器部分只是个很小很小的组成，而这两节讲述的语言构造器才能真正为我们的编译工作起到重 要的作用.这些东西相信大家在大学的编译原理的课程已经学了不少，那么本文我也只是大致地带过，让大家回忆起大学的知识，重要的 yacc 使用技巧等等，我将在后面的内容讲岀.3cdXwckm15例 3.1exp - exp op
31、exp |(exp | nu mberop -+ |-|*这里就是一个定义的带有加法，减法,乘法的简单整数算术表达式的文法 .其中粗体表示的 是终结符号，也就是不能有产生式生成的符号 .而 exp,op 就是非终结符，它们都是由一个”- 符号来产生的.h8c52WOngM比如 100 + 222 *- (888+11就是符合上述文法的具体的表达式16/ 52注意,在文法定义中 ,是可以递归的 .所以 exp 产生式右边的式子中可以再次出现 exp.这里的 | 和正则表达式一样 , 表示的选择的意思 , 也就是说 ,exp 可以是 exp op exp 或者(exp 再或者 numb
32、er.v4bdyGious下面让我们看看 书中的一个关于 BNF 文法的介绍. 比如说我们有个数学表达式(34-3*42, 然后我们来看看上面的 exp 文法怎么来推导识别它(1 exp = exp op expexp -exp opexpJ0bm4qMpJ9(2number= exp op number exp - XVauA9grYP(3*= exp * number op - bR9C6TJscw(4(exp= (exp * number exp - pN9LBDdtrd(5= (exp op exp * number exp -exp op expDJ8T7nHuGT(6= (exp
33、op number* numberexp - numberQF81D7bvUA(7= (exp - number * number op - -4B7a9QFw9h(8= (number number* number exp - numberix6iFA8xoX最终 ,exp 里面全部的非终结符号全部变成了终结符号 . 那么推导完成 .这种推导十分像我们在离散数学中讲到的命题推理 . 其实形式语言的推导的数学基础就是 我们离散数学的命题推理 .wt6qbkCyDE在推导过程中 , 其实就是把原来的文法中的递归展开 . 那么我们在推导的过程 , 也就很容易 实现分析树的生成 . 而分析树就是我们
34、编译程序中十分重要的信息源 .我们之所以前面又做词法17/ 52分析,又做语法分析的目标就是为了生成分析树 .有了它 ,我们编译程序在后面的代码生成过程中 将变得容易百倍 .Kp5zH46zRk请看 :例 3.2同样是 书上的例子 .设 E - E+a | a 表示的文法为 G, 那么考虑它生成的表达L(G如果由标准的数学定义 , 那么我们用公式 L(G=s | exp =* s 表示一种文法 G.s 代表记号符号的任意数组串 , 也就是我们的终结符号 . 而 exp 代表非终结符号 ,=* 表示一 系列的从非终结符到终结符号的推导过程.这里 *有点像我们在讲述正则表达式中的*符号一样 ,它表
35、示 0 到无限次的重复 . 所以 =* 就是表示 0 次到无限次的推导过程 .Yl4HdOAA61L(G = a,a+a,a+a+a,a+a+a+a,E = E+a = E+a+a = E+a+a+a同时 , 在我们的编译课本上 , 又经常讲述另一种数学表达方式来阐述文法的定义 .G=(T,N,P,S注意 , 这里的 T,N,P,S 都是集合 .T 表示终结符号 (terminal, 也就是这里 a,+N 表示非终结符号(nonterminal,也就是这里E,但是 N 不能与 T 相交.P 表示产生式(production或者文法规则(grammar rule的集合,这里它只有一个元素：E-
36、E+ach4PJx4BlIS 表示集合 N 的开始符号(start symbol. 关于 S,本人也搞不清楚它的用处，所以很抱歉！18/ 52例 3.3这是我们 C 程序语言中经常使用if else 文法statement - if-stmt |otherif-stmt - if (exp statement | if (exp statement else statementqd3YfhxCzoexp -0| 1statement 就是我们 C 语言中使用语句 , 它的产生式包括了两种可能 , 一是 if-stmt 语句 , 二是 other. 然后我们又另外定义 if-stmt 语句的产生
37、式 . 这里有两种情况 ,一是没有 else 的, 另 外就是有 else 的 . 里面我们又使用了递归 .if-stmt 本来是包含在 statement 里面的 , 可是我们 又在 if-stmt 的产生式中使用 statement.正是因为文法中允许递归 , 所以它比起我们前面讲的 正则表达式有更广泛的表示能力 ,但同时 ,文法的推导识别也更加法复杂 .按照编译原理的书籍 , 一般讲完 BNF 文法后，就要重点讲解文法的推导算法.一共有两种，一是 LL 算法，自顶向下的算法二是 LR 算法，自底向上的算法 丄 L 算法比较简单，其中还有一种特殊的情况，就是我们下一节要讲的递归下降的算法.
38、由于 C 语言中的函数本来就可以递归，那么实现这中递归下降的算法是十分简单的 , 而且对于我们一般的程序设计语言来说 , 虽然它的算法能力很弱 , 但是已经是足够用了 而关于 LR的算法，那么就是一个大难题了.它的算法能力最强，但是实现起来十分困难，还好，已经有科学家为我们提供了yacc(或者叫 bison这个工具，可以来自动生成 LR 的文法推导算法.这就是我们一直在提到的 yacc 工具了 .E836L11DO5回过头来 , 我们看看下面的程序if(0 other else other的分析树思考 : 为什么要把文法最终分析成树结构后 , 后面在处理代码生成等问题上 , 也可以用递归来很容
39、易地完成 .S42ehLvE3M因为文法本身是递归的 , 而表示的递归的最好数据结构就是树, 所以我们把文法弄成树结构19/ 52例 3.4这里我给出 microsoft 在 msdn 中对于 C 语言的 statement 的文法注意,这里用 :符号替代了我们前面产生式的 -statementlabeled-statementcompound-statementexpression-statementselection-statementiteration-statementjump-statementtry-except- statement /* MicrosoftSpecific */
40、 try-finally-statement /* Microsoft Specific */501nNvZFisjump-statement :gotoidentifier。 continue 。 break。 returnexpressionopjW1viftGw9compound-statement : declaration-listoptstatement-listoptdeclaration-list :declarationdeclaration-list declarationstatement-list :statementstatement-list statementex
41、pression-statement :expressionopt。iteration-statement :while ( expression statement do statement while( expression 。 for( expressionopt。 expressionopt。 expressionopt statementxS0DOYWHLP20/ 52selectio n-stateme ntif (expressionstatement if(expression statementelse statement switch(expression statemen
42、tLozMkiqiowlabeled-stateme ntidentifier: statement case constantexpression: statement default :statementzKzuQsujedtry-except-stateme nt :/* Microsoft Specific */_trycompound-statement_except( expressi on compo und-statementdGY2mcoKtTtry-fi nally-stateme nt:/* Microsoft Specific */_trycompo un d-stat
43、eme nt _fin allycompo un d-stateme ntrCYbswRLiA从 lex&yacc 说到编译器（4.文法识别（一 作者：tangl_99:msn:tan gl_FyXjoFlMWhemail: tangl_TuWrUpPObX没想到这一系列文件能得到csdn 和大家的这么看好，首先要感谢大家的赏识和csdn 的推荐.那么我就更没有理由不写好这下面的几篇文章了.本来我的计划是简单把lex 和 yacc 介绍完后就直接进入编译器的构造的技术细节问题讨论，但是最近看了一些国外经典教材后，发现文法的识别问题在编译原理和技术中是个绝不能忽视的问题.即使现
44、在有了 yacc 工具来帮助我来识别文法，但是有些时候还是需要我们自己来写简单的语法分析器.7qWAq9jPqE1.什么是文法识别（语法分析首先要告诉大家的是，这里的文法识别是指的上下文无关的文法，也就是上一节我们一直在讨论的那些 BNF 式.llVIWTNQFk21/ 52比如说 , 我写了一句if (a6+5 printf(“ OK!” 。 else printf(“No!”。那么它匹配的文法也就是if-stmt - if expr stmt| if expr stmt else stmt我们通常要为一个程序语言写岀很多BNF 式的文法，怎么知道这句话是匹配的哪个文法，这就是语法分析器 (
45、或者叫文法分析器要做的工作.知道了是那句文法后 ,我们才能对这句话做出正确的解释 , 所以文法识别是个不可忽视的工作. 下面我来看看我们常使用的文法识别的算法.yhUQsDgRT12.自顶向下的算法 (LL 算法自顶向下的语法分析算法是十分简单的.自顶向下的算法也叫LL 算法丄 L(k就是向前预测k 个符号的自顶向下的算法 . 不过无论是我们国内的编译教程还是国外的经典教程都是只讨论了LL(1算法.因为一般的程序语言，只使用 LL(1算法就已经足够了.这里我们同样也只是讨论LL(1 算法 .MdUZYnKS8I其中有种特殊的算法叫做递归下降的算法，在 C 语言中，由于函数本身是可以递归的，所以
46、实现这种算法就只需要写简单的几个函数的递归过程就是了.09T7t6eTno为什么叫自顶向下呢 ?因为在分析过程中 , 我们是从语法树的树顶逐步向树底分析的 , 所以 叫自顶向下的算法 .为了方便说明自顶向下算法的简单性 , 我们来看一下 中的一个例子 .( 本系列文章经常要引用国外经典著作的范例, 希望大家不要告我抄袭 , 我实在找不到比大师的范例更经典的范例了e5TfZQIUB5例 4.1考虑一个 Pascal 中定义变量的文法特别说明 , 这里的 dotdot 表示” . ”type-simple| id | array simple oftype22/ 52simple -integer
47、 | char | num dotdot num在为 array num dotdot num of integer构造一个分析数的时候 , 该算法就是从根结点开始 .s1SovAcVQM下面我们通过其中主要的三个步骤来看看算法的实现原理 .第一步分析:_ GXRw1kFW5s首先分析的是输入的字符串第一个串” array ”, 判断出它属于 type 的 First 集合 . 所以在 图中的分析树部分 , 我们的当前分析就是树根结点 type.( 图中标上箭头 , 就表示是当前正在分析 的部分 .UTREx49Xj9这里遇到一个新名词 : First 集合 .在大学里的编译课程肯定是讲过 F
48、irst 集合的吧 . 不过 我还是要在这里重复一次了 .8PQN3NDYyP名词解释 First 集合 :在对文法产生式进行判断的时候 , 每个产生式都是由好几个终结符和非终结符构成. 比如本例中的文法type-simple| id| array simple oftypesimple -integer23/ 52| char| num dotdot num判断 type 的产生式的时候 , 如果我们把每个产生式里面的 simple,id,array, ,simple , , of , type这些终结符和非终结符都进行判断的话, 那么就会涉及到”实验和错误”的问题 . 当一个文法产生式分析
49、到最后 ,发现并不匹配 , 就必然会产生回溯的问题 , 就要回 到头, 从新开始对第二个产生式逐步进行判断分析 .我们知道 ,回溯的算法效率肯定是十分低效率 的. 但是实际上我们完全可以避免这种回溯算法,而完成同样工作的文法分析 . 这就产生了计算First 集合的理论和以及后面的 左提公因式 的问题 .mLPVzx7ZNwFirst 集合简单地说 ,就是一个非终结符的最开头的字符串(终结符号 的集合 .比如说 .非终结符在其开头 , 那么 simple 的开头字符串同 的一部分 .AHP35hB02d为什么我们只计算每个非终结符的最开头的终结符 ? 因为我们这里是考虑的 LL(1 算 法丄
50、L(1算法只向前预测一个字符号，所以我们只考虑一个First 集合就可以判断岀是哪个文法产生式了 .NDOcB141gT这里听起来似乎有些不太可能 , 一个产生式有那么千百万化 , 如果单单只看第一个非终结符 号, 如果就能说明一个输入串到底是哪个产生式呢 ? 如果有两个产生式的最开头一样怎么办 , 比 如像 if 语句，那怎么办？但其实我们几乎所有的程序语言的文法都可以通过LL(1来分析岀来.原因是我们可以通过 左提公因式 来把最开头的相同的产生式的公共终结符号提取岀来, 留下两个子产生式 , 而他们的最开头的非终结符号不相同 .1zOk7Ly2vA左提公因式例 4.2考虑文法A- abFi
51、rst(simple = integer, char, numFirst(type = First(simple U id ,array 这里的 type 的一个产生式中有个 时也可以是 simple, 所以 First(simplesimple也是 First(type24/ 52|ac这里 ,A 的两个产生式中最开头的终结符号都是a, 那么就无法通过这个最开头的终结符号来判断一个输入串到底该是哪个产生式了 . 那么我们可以修改文法成fuNsDv23KhA- aAA- b | c这样一来，一个文法变成两个，但是无论 A 还是 A,它们的每个产生式的 First 集合都是 不相交的 .所以,
52、他们能够只通过最开头的终结符号来判断是哪个产生式.tqMB9ew4YX这个变化过程有点想我们的代数里面的ab + ac = a(b+c,所以叫它左提公因式 .这只是个简单的左提公因式的例子 , 实际当中还会遇到一些复杂的问题 . 但是无论是哪个编 译教材 , 都会给出针对一切文法的左提公因式的算法.同样 , 计算 First 集合的算法也在教材中详细讲解了 . 我就不在这里再描述了 .HmMJFY05dE第二步分析:_ ViLRaIt6sk经过第一步的考察输入串中的第一个串为” array ”属于非终结符号 type 第三个产生式的 First 集合, 那么就可以确定这个串确实为 type 文
53、法第三个产生式的串 .所以在第二步中 , 展开 出 type 的第三个产生式出来 .type- array simple of integer9eK0GsX7H1那么接下来就是继续分析构造出来的 type - array simple of integer产生式中的每个结点 .naK8ccr8VI所以箭头又放到了分析树中 type 的第一个孩结点 array 上. 因为 array 是终结符号 , 如果 它和输入中的当前箭头所指的终结符号相同 , 那么箭头都往下移动一结点到 符号 .同样地 , 由于分析树中的 是终结符号 , 那么只要看输入中的串是否是 就可以了 . 如果是 ,那么继 续往下分
54、析 .分析到分析数中的simple的时候 , 由于 simple 是非终结符号 , 那么就需要考虑 simple 的产生式了 .B6JgIVV9ao第三步分析:P2IpeFpap525/ 52在第二步中 , 分析到分析数中的 simple 子结点的时候 , 由于 simple 是非终结符号 , 那么就 需要考虑simple 的产生式 .simple 一共有三个产生式 . 通过输入串当前的串是” num” , 是属于 simple 产生式中第 3 个产生式的 First 集合 , 所以 simple 在分析数中就按第三个产生式simple- num dotdot num 来展开 . 那么分析箭头
55、同样 , 也自动移动到 simple 的第一个子 结点 num 上继续分析 .3YIxKpScDM总体说来 , 这中自顶向下的分析原理就基本上是上面的过程 .通过计算产生式的 First 集合 , 来逐步产生非终结符的产生式 . 最后的分析树都会划归到终结符来进行判断 (非终结符号是无法 进行直接判断的 , 一定要展开过后才行 .gUHFg9mdSs看了原理 , 我们再看实现的伪代码 . 代码很简单 ._ uQHOMTQe79void match( char tokenif lookahead = tokenlookahead = token 。elseerror(0 。void type(i
56、f ( lookahead = integer | lookeahead =char | lookahead26/ 52elseerror(0void simple(if ( lookahead =integar match( integer 。else if ( lookahead = char match( char 。else if ( lookahead = nummatch( num。 match( dotdot 。 match(elseerror(0 。= numIMGWiDkflPsimple(else if ( lookahead = id match( id 。else if
57、 ( lookahead = array match( array match( 。 simple(match( match( of 。 type(WHF4OmOgAwnum。aDFdk27/ 526hhPd注意：这里的代码都是纯的语法分析代码，实际执行过程中并没有什么用处，但是我们构造语法树 parse-tree的代码就是镶嵌在这些纯的语法分析代码中.ozEiLi4T从 lex&yacc 说到编译器（5.实用 javacc、八 、，刖言本系列的文章的宗旨是让大家能够写岀自己的编译器，解释器或者脚本引擎，所以每到理论介绍到一个程度后，我都会来讨论实践问题.理论方面，编译原理的教材已经是够多
58、了，而实践的问题却很少讨论.CvDtmAfjiA前几节文章只讨论到了词法分析和LL 文法分析，关键的 LR 文法分析这里却还没有讲，我们先不要管复杂的 LR 文法和算法，让我们使用 LL 算法来实际做一些东西后再说.本文将介绍一个在 JAVA 上广泛使用的 LL 算法分析工具 Javacc.（这是我唯一能找到的使用LL 算法的语法分析器构造工具 .这一节的文章并非只针对JAVA 开发者，如果你是 C/C+开发者，那么也请你来看看这个 JAVA 下的优秀工具，或许你将来也用得着它.QrDCRkJkxhLex 和 yacc 这两个工具是经典的词法分析和语法分析工具，但是它们都是基于C 语言下面的工
59、具，而使用 JAVA 的朋友们就用不上了 .但是 JAVA 下已经有了 lex 和 yacc 的替代品 javacc（JavaCompiler Compiler .同时 javacc 也是使用LL算法的工具，我们也可以实践一下前面学的 LL 算法.4nCKn3dlMX首先声明我不是一个 JAVA 专家，我也是刚刚才接触 JAVA.Java 里面或许有很多类似 javacc 一样的工具，但是据我所知,javacc 还是最广泛，最标准的 JAVA 下的词法语法分析 器.ijCSTNGmOEaDFdk28/ 52Javacc 的获取29/ 52同 lex 和 yacc 一样 ,javacc 也是一个
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/1192.html