Lex和Yacc简明教程

和简明教程 LexYacc 作者 :Thomas Niemann 翻译：傅惠忠目录序言­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­3 导言­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­4 Lex­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­6 理论­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­6 练习­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­7 YACC­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­11 理论­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­11 练习，第一部分­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­12 练习，第二部分­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­15 计算器­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­18 描述­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­18 包含文件­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­20 输入文件 Lex­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­21 输入文件 Yacc­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­22 解释器­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­26 编译器­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­27 图­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­28 进阶 Lex­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­34 字符串­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­34 保留字­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­35 的调试 lex­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­35 进阶 Yacc­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­37 递归­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­37 歧义 If­Else­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­37 错误信息­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­38 继承属性­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­39 内含动作­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­39 调试Yacc­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­39 参考书目­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­40序言本书将教会你如何使用和构造一个编译器。和是两个用来生成词汇分析器和 lexyacclexyacc 剖析器的工具。我假设你能够运用语言编程，并且理解数据结构的含义，例如“链表”和 C “树”。导言部分描写了构建编译器所需的基本部分，以及和之间的互动关系。后面两章更加 lexyacc 详细的描写了和。以此为背景，我们构建了一个经典的计算器程序。这个计算器支持常用 lexyacc 的算术符号和控制结构，例如实现了像和这样的控制结构。经过小小的修改，我们就 if­elsewhile 把这个计算器转换成一个可以运行在基于栈的计算机上的编译器。后面的间节讨论了在编写编译器是经常发生的问题。本书中使用的例程的源代码可以从下面列出的网站上下载到。允许下面列出的网站复制本书的一部分内容，没有任何附加限制。例程中的源代码可以自由的用于任何一个软件中，而无需通过作者的授权。 THOMAS NIEMANN 波特兰，俄勒冈州网站：epaperpress.com 译者序 : 找不到好的中文资料，所以自己翻译了一个，如发现错误，请不吝赐教。电子邮件：[e-mail] 傅惠忠导言在年之前，编写编译器一直是一个非常费时间的工作。这一年和 1975Lesk[1975]Johson 发表了关于和的论文。这些工具极大地简化了编写编译器的工作。在中 [1975]lexyaccAho[1986] 描写了关于如何具体实现和的细节。从下列地方可以等到和工具： lexyacclexyacc ，在， Mortice Kern System (MKS) ●和，在， GNU flex bison ●，在， Ming ●，在，还有 Cygwin ●我的和版本，在 LexYaccepaperpress.com ●的版本是一个高质量的商业产品，零售价大约是美元。软件是免费的。的 MKS300GNUflex 输出数据也可以被商业版本所用，对应的商业版本号是，也一样。和是 1.24bisonMingCygwin 软件在某些位系统上的移植产物。事实上是操作系统在 GNU32WindowsCygwinUNIXWindows 上的一个模拟接口，其中包括了和编译器。 gccg++ 我的版本是基于的，但量是使用编译的并且包含一个改善文件操作程序的小 MingVisual C++ 补丁。如果你下载我的版本，请记住解压缩的时候一定要保留文件夹结构。图：编译顺序 1 为词法分析器或扫描器生成Ｃ程序代码。它使正则表达式匹配输入的字符串并且把它们转 Lex换成对应的标记。标记通常是代表字符串或简单过程的数值。图１说明了这一点。当发现了输入流中的特定标记，就会把它们输入一个特定的符号表中。这个符号表也会包 Lex 含其它的信息，例如数据类型（整数或实数）和变量在内存中的位置。所有标记的实例都代表符号表中的一个适当的索引值。为语法分析器或剖析器生成Ｃ程序代码。使用特定的语法规则以便解释从得到的标 YaccYaccLex 记并且生成一棵语法树。语法树把各种标记当作分级结构。例如，操作符的优先级和相互关系在语法树中是很明显的。下一步，生成编译器原代码，对语法树进行一次第一深度历遍以便生成原代码。有一些编译器直接生成机器码，更多的，例如上图所示，输出汇编程序。图２：用构建一个编译器 Lex/Yacc 图２显示了和使用的命名约定。我们首先要说明我们的目标是编写一个编译 LexYaccBASIC 器。首先我们要指定的所有的模式匹配规则（）和的全部语法规则（）。下面列 Lexbas.lYaccbas.y 举了产生我们的编译器，，的命令。 bas.exe　　　　　　　生成 yacc ­d bas.y #  y.tab.h, y.tab.c　　　　　　　　　　生成 lex bas.l #  lex.yy.c　编译／连接 cc lex.yy.c y.tab.c ­o bas.exe # 读入中的语法描述而后生成一个剖析器，即中的函数。中包含 Yaccbas.yy.tab.cyyparsebas.y 的是一系列的标记声明。“”选项使生成标记声明并且把它们保存在中。读入 ­dYaccy.tab.cLex 中