Lex和Yacc简明教程

《Lex和Yacc简明教程》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Lex和Yacc简明教程作者:ThomasNiemann 翻译：傅惠忠目录序言3 导言4 Lex6 理论6 练习7 YACC11 理论11 练习，第一部分12 练习，第二部分15 计算器18 描述18 包含文件20 Lex输入文件21 Yacc输入文件22 解释器26 编译器27 图28 Lex进阶34 字符串34 保留字35 lex的调试35 Yacc进阶37 递归37 IfElse歧义37 错误信息38 继承属性39 内含动作39 调试Yacc39 参考书目40序言本书将教会你如何使用lex和yacc构造一个编译器。lex和yacc

2、是两个用来生成词汇分析器和剖析器的工具。我假设你能够运用C语言编程，并且理解数据结构的含义，例如“链表”和“树”。导言部分描写了构建编译器所需的基本部分，以及lex和yacc之间的互动关系。后面两章更加详细的描写了lex和yacc。以此为背景，我们构建了一个经典的计算器程序。这个计算器支持常用的算术符号和控制结构，例如实现了像ifelse和while这样的控制结构。经过小小的修改，我们就把这个计算器转换成一个可以运行在基于栈的计算机上的编译器。后面的间节讨论了在编写编译器是经常发生的问题。本书中使用的例程的源代码可以从下面列出的网站上下

3、载到。允许下面列出的网站复制本书的一部分内容，没有任何附加限制。例程中的源代码可以自由的用于任何一个软件中，而无需通过作者的授权。THOMAS NIEMANN 波特兰，俄勒冈州网站：epaperpress.com 译者序: 找不到好的中文资料，所以自己翻译了一个，如发现错误，请不吝赐教。电子邮件：fuhuizn@hotmail.com 傅惠忠导言在1975年之前，编写编译器一直是一个非常费时间的工作。这一年Lesk[1975]和Johson [1975]发表了关于lex和yacc的论文。这些工具极大地简化了编写编译器的工作。在Aho[1

4、986]中描写了关于如何具体实现lex和yacc的细节。从下列地方可以等到lex和yacc工具：●Mortice Kern System (MKS)，在www.mks.com ，●GNU flex和bison，在www.gnu.org ，●Ming，在www.mingw.org ，●Cygwin，在www.cygwin.org ，还有●我的Lex和Yacc版本，在epaperpress.com MKS的版本是一个高质量的商业产品，零售价大约是300美元。GNU软件是免费的。flex 的输出数据也可以被商业版本所用，对应的商业版本号是1.

5、24，bison也一样。Ming和Cygwin 是GNU软件在某些32位Windows系统上的移植产物。事实上Cygwin是UNIX操作系统在Windows 上的一个模拟接口，其中包括了gcc和g++ 编译器。我的版本是基于Ming的，但量是使用Visual C++编译的并且包含一个改善文件操作程序的小补丁。如果你下载我的版本，请记住解压缩的时候一定要保留文件夹结构。图1 ：编译顺序Lex为词法分析器或扫描器生成Ｃ程序代码。它使正则表达式匹配输入的字符串并且把它们转换成对应的标记。标记通常是代表字符串或简单过程的数值。图１说明了这一点。

6、当Lex 发现了输入流中的特定标记，就会把它们输入一个特定的符号表中。这个符号表也会包含其它的信息，例如数据类型（整数或实数）和变量在内存中的位置。所有标记的实例都代表符号表中的一个适当的索引值。Yacc为语法分析器或剖析器生成Ｃ程序代码。Yacc使用特定的语法规则以便解释从Lex 得到的标记并且生成一棵语法树。语法树把各种标记当作分级结构。例如，操作符的优先级和相互关系在语法树中是很明显的。下一步，生成编译器原代码，对语法树进行一次第一深度历遍以便生成原代码。有一些编译器直接生成机器码，更多的，例如上图所示，输出汇编程序。图２：用Le

7、x/Yacc构建一个编译器图２显示了Lex和Yacc使用的命名约定。我们首先要说明我们的目标是编写一个BASIC编译器。首先我们要指定Lex的所有的模式匹配规则（bas.l）和Yacc的全部语法规则（bas.y ）。下面列举了产生我们的编译器，bas.exe，的命令。yacc dbas.y #生成y.tab.h, y.tab.clex bas.l#生成lex.yy.ccc lex.yy.cy.tab.c obas.exe# 编译／连接Yacc读入bas.y中的语法描述而后生成一个剖析器，即y.tab.c中的函数yyparse。bas.y

8、 中包含的是一系列的标记声明。“d”选项使Yacc生成标记声明并且把它们保存在y.tab.c中。Lex 读入bas.l中的正则表达式的说明，包含文件y.tab.h，然后生成词汇解释器，即文件lex.yy.c