《编译原理简明教程》普通高等教育“十二五”规划计算机教材---太原理工大学---计算机科学与技术学院---冯秀芳、崔冬华、段富等第一章 引言
第二章 形式语言理论基础第三章 自动机理论基础第四章 词法分析第五章 语法分析—自顶向下分析方法第六章 语法分析—自底向上分析方法
第七章 语义分析及中间代码的生成第八章 代码优化第九章 目标代码的生成第十章 符号表第十一章 目标程序运行时的存储组织与分配第十二
章 出错处理第十三章 编译程序自动生成工具简介第十四章 面向对象语言的编译第十五章 并行编译技术目 录第十三章 编译程序自动
生成工具简介 学习目标了解和掌握高级语言编译程序自动生成工具的种类了解和掌握几种常用的词法分析自动生成工具用法 了
解和掌握几种常用的语法分析自动生成工具用法 词法分析、语法分析、一遍扫描分析和多遍扫描分析等，其实都是非常机械的过程，完
全可以由计算机代替人工完成，由此出现了词法和语法分析的自动生成工具，本章简单介绍这种自动生成工具的发展、作用、分类以及目前常用的工
具应用。 学习本章后，学生应该能够掌握使用编译程序自动生成工具完成高级语言词法和语法分析的基本方法，具有设计、实现、分
析和维护编译器的词法和语法分析的初步能力。13.1 引言13.1.1 编译程序自动生成工具简介 13.1.2 编译程序自动生成工具
的种类及常用工具简介13.2 词法分析自动生成工具13.2.1 LEX系列词法分析自动生成工具简介 13.2.2 其他词法分析自动
生成工具简介 13.3 语法分析自动生成工具13.3.1 YACC系列语法分析自动生成工具简介 13.3.2 其他语法分析自动生成
工具简介 目 录13.1 引言13.1.1 编译程序自动生成工具简介编译程序自动生成工具的实质：就是实现编译器中的词法和语法分
析过程，其原理就是本书前几章所介绍的编译过程的词法和语法分析的自动化实现。编译程序自动生成工具的作用：自动识别源程序是否符合该语言
所规定的语法规则。编译程序自动生成工具的分类：词法分析和语法分析两个阶段 13.1 引言13.1.2 编译程序自动生成工具的种类
及常用工具简介由于在编译器实现过程所包含的几个阶段中，词法分析和语法分析的实现原理明确，操作步骤确定，可以借助于计算机来自动完成，
所以编译程序自动生成工具主要包含词法分析和语法分析两种类型。 早期的研究一般是分别给出词法和语法分析的实现工具，如UNIX操作系统
平台上的LEX和YACC；现在的一些工具则将词法和语法分析的实现集成在一起，而且也不再局限于用C语言实现，出现了很多基于Java语
言且可以生成多种目标语言的词法和语法分析工具，比如ANTLR和JavaCC & SableCC等。根据语法分析阶段采用“自底向上”
或“自顶向下”分析方法的不同，以及分析阶段向前看字符数的差别，可以将编译程序自动生成工具分成若干种类。13.1 引言13.1.2
编译程序自动生成工具的种类及常用工具简介表13.1 几种编译器的词法、语法分析自动生成工具的特性对照表13.2 词法分析自动
生成工具 ? 词法分析工具将源程序看做字符文件类型，由Lex创建的词法分析器与语法分析器类工具按照如下图的方式协
同工作(如图13.1所示)：词法分析器读取源程序并将文件分为若干个单词，提交给语法分析阶段使用。图13.1 词法分析器与语法分析
器之间的交互示意图13.2 词法分析自动生成工具 ? 13.2.1 LEX系列词法分析自动生成工具简介Lex是美
国Bell实验室的M.Lesk等人用C语言研制的词法分析自动生成工具；基本原理：使用正则表达式扫描源程序，并为每一个匹配模式定义一
些操作。特点：Lex和C是强耦合的，词法分析过程中，Lex接收一个后缀为.l的文件(描述词法分析规则的规范文件)，分析检查并生成词
法分析的可执行版本，通过Lex公用程序来传递并生成基于C语言的输出文件。 Lex工具的输入表示方法称为Lex语言，而工具本身(如F
lex)则称为Lex编译器。在Lex工具的核心部分，Lex编译器将输入的模式转换成一个状态转换图，并生成相应的实现代码，存放到一个
称为1ex.yy.c或1exyy.c的Lex输出文件中，这些代码用来模拟转换后的状态转换图。 13.2 词法分析自动生成工具
? 13.2.1 LEX系列词法分析自动生成工具简介1、Lex的使用方法 用Lex创建一个词法分析器的操作步骤图1
3.2图13.2 用Lex创建一个词法分 析器的操作步骤示意图13.2 词法分析自动生成工具 ?
13.2.1 LEX系列词法分析自动生成工具简介2．正则表达式的Lex约定正则表达式(regular expression)：是
一种可以用于模式匹配和替换的强有力的工具。 【例13.1】 为“以aa或bb开头，末尾是一个可选的c”描述的串写出两种正则表达式。
参考解答： (aa|bb)(a|b)c?
或 ("aa"|"bb")("
a"|"b")"c"?13.2 词法分析自动生成工具 ? 13.2.1 LEX系列词法分析自动生成工具简介2．
正则表达式的Lex约定正则表达式(regular expression)：是一种可以用于模式匹配和替换的强有力的工具。 【例13.
2】为一个带符号的数集写出正则表达式，这个集合可能包含一个小数部分或一个以字母E开头的指数部分。参考解答： (“+”|“-”
)？[0-9]+( “.” [0-9])?(E(“+”|“”)?[0-9]+)?13.2 词法分析自动生成工具 ?
13.2.1 LEX系列词法分析自动生成工具简介2．正则表达式的Lex约定正则表达式(regular expression)
：是一种可以用于模式匹配和替换的强有力的工具。 【例13.3】 定义前面讲述的signed num。参考解答： num =
[0-9]+ signednum = ("+"|"-")? num也可以定义为 num [0-9]+
signednum (+|-)?{num}注意，在定义名字时并未出现花括号，它只在使用时出现。13.2 词法分析自动生成工具
? 13.2.1 LEX系列词法分析自动生成工具简介3．Lex词法输入文件的格式Lex输入文件的格式如下：{ de
finitions }%%{ rules }%%{ auxiliary routines }Lex输入文件(即Lex程序)由3部分
组成：定义(definition)集、规则(rule)集、辅助程序(auxiliary routine)集或用户程序(user r
outine)集这3部分由位于新一行第1列的双百分号分开。 13.2 词法分析自动生成工具 ? 13.2.1 L
EX系列词法分析自动生成工具简介3．Lex词法输入文件的格式第1个双百分号之前出现的是：定义(或称声明)部分，包括两部分可选内容：
一是包含在分隔符“%{”和“%}”之间的任何函数外部的任意C代码(注意这些字符的顺序)，这些C代码可以插入到生成的C程序中；二是正
则表达式名字的定义。第1和第2个双百分号之间出现的是：规则部分，由一系列带有C代码的正则表达式组成，每个转换规则的格式为 模
式 ｛动作｝；其中每个模式是一个正则表达式，可以使用声明部分给出的正则定义。当匹配相对应的正则表达式时，这些动作对应的C代码片段就
会被执行。第2个双百分号之后出现的是：规则部分各个动作需要使用的所有辅助函数，这部分是可选内容。 通常，当不需要第3个部分
的辅助函数时，第2个双百分号就无须出现了，但第1行双百分号总是需要出现的。 13.2 词法分析自动生成工具 ? 1
3.2.1 LEX系列词法分析自动生成工具简介4．Lex输入文件格式示例【例13.4】 以下的Lex输入能够识别表13.2中的各
个词法单元并返回，观察这段代码，分析Lex程序的特点。%{/ 常量定义(声明)LT, LE, EQ, NE, GT, GE, L
T, THEN, ELSE, ID, NUMBER, RELOP /#include int lineno
= 1;%}/ 正则表达式定义 /delim [ \t\n]ws {delim}+lett
er [A-Za-z]digit [0-9]id {letter}({ letter }|{ digit}
)number {digit}+(\.{digit}+?(E[+- ]?{digit }+)?line .\n
%%13.2 词法分析自动生成工具 ? 13.2.1 LEX系列词法分析自动生成工具简介{ws} {
/ 没有动作或没有返回 / }if {return (IF);}then {return (TH
EN);}else {return (ELSE);}{id} {yylval = (int) installID
(?).; return(ID);}{number} {yylval = (int) installNum(?).; return
(NUMBER);}“<” {yylval = LT; return(RELOP);}“<=” {yylval =
LE; return(RELOP);}“=” {yylval = EQ; return(RELOP);}“<>” {y
ylval = NE; return(RELOP);}“>” {yylval = GT; return(RELOP);}“>
=” {yylval = GE; return(RELOP);}{line} {printf(“%5d %s”, line
no++, yytext);}%%13.2.1 LEX系列词法分析自动生成工具简介int installID(?){/ 将词素
初始化到符号表中的函数，返回一个指针；其中yytext是指向词素开头的指针，yyleng存放刚找到的词素的长度 /}int i
nstallID(?){ / 与installID相似，但初始化和存放的是数字常量 / }main(?){ yylex(?)
; return 0; }13.2 词法分析自动生成工具 ?13.2 词法分析自动生成工具 ? 13.2.1
LEX系列词法分析自动生成工具简介5．Lex中的冲突解决Lex解决冲突的两个规则，即当输入的多个前缀与一个或多个模式匹配时，Le
x用下列规则选择正确的词素：① 总是选择最长的前缀。② 如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式。1
3.2 词法分析自动生成工具 ? 13.2.2 其他词法分析自动生成工具简介1．FLexFlex(Fast Le
x)是最常见的Lex开源版本，它是由Free Software Foundation创建的Gnu Compiler Package
的一部分，可以在许多Internet 站点上免费得到。与其配套的开源语法分析器编译工具是Bison，这组工具使用C语言来指定动作代
码(我们使用属性“动作”来指代由编程人员所写的在词法或语法分析执行部分某个特定点要执行的代码)。13.2 词法分析自动生成工具
? 13.2.2 其他词法分析自动生成工具简介2．JLexJLex是Lex的一个Java版本，由普林斯顿大学计算机
科学系的一个学生Elliot Joel Berk开发。JLex在功能上与Flex非常相似，它接受类似Lex文件格式的词法分析文件，
生成Java源代码格式的词法分析器。与其配套的语法分析器编译工具是CUP(Constructor of Useful Parser
s，YACC的Java版本)或BYacc/J(Bob Jamison对经典Berkeley YACC的Java扩展) 。13.2
词法分析自动生成工具 ? 13.2.2 其他词法分析自动生成工具简介3．PCCTS/ANTLR PC
CTS (Purdue Compiler Construction Tool Set)主要是由Terence Parr开发的集词法
、语法分析于一体的编译自动生成工具，最初PCCTS是用C++语言写的，产生的目标代码也是C++。PCCTS开发的主要目的是应对使用
Lex/YACC系列工具解决编译问题时所产生的复杂性。后来PCCTS1.33版本转向了Java并更名为ANTLR2.xx。
ANTLR(ANother Tool for Language Recognition)，是PCCTS的Java版本，它可以接受
词法和语法规则描述，并能产生识别这些规则的程序代码，同时作为翻译程序的一部分，我们可以使用简单的操作符和动作来参数化表示词法、语法
规则的文法，告诉ANTLR怎样去创建抽象语法树(AST)及产生输出，ANTLR知道怎样去生成相应代码的识别程序，包括Java，C+
+，C#代码。 作为开放源代码的对象关系映射独立框架，Hibernate就是采用ANTLR来编译HQL查询语言的。13.2
词法分析自动生成工具 ? 13.2.2 其他词法分析自动生成工具简介4．JavaCC(Java Compiler
Compiler) JavaCC是SUN公司开发的、用Java语言编写的与ANTLR非常相似的一个编译器自动生成工具
，所产生的文件都是纯Java代码。 与PCCTS/ANTLR一样，JavaCC集词法分析生成器和语法分析生成器于一体，可以
同时完成对输入文件的词法分析和语法分析的工作，使用起来相当方便。JavaCC和它所自动生成的语法分析器可以在多个平台上运行。另外，
JavaCC可以看成Java世界里的一个类Lex/YACC工具，同是也是一个可以免费获取的通用工具，它遵循BSD License(
Berkeley Software Distribution License)，可以自由使用，也可以在很多Java相关的工具下载网
站下载，当然，要获得最新版本的JavaCC，还是在官网https://JavaCC.dev.java.net/下载比较好。与ANT
LR相比，除了版权和生成代码的类别外，两者之间没有重要的差别。 13.2 词法分析自动生成工具 ? 13.2.2
其他词法分析自动生成工具简介5．SableCC SableCC是一种新的生成Java目标代码的编译器自动生成工具
，同时具有词法和语法分析的功能。其实现原理与PCCTS/ANTLR、JavaCC类似，其中的词法分析也是作为语法分析的一部分而构成
整个系统的。SableCC可以从网站http://sablecc.org/免费获取。13.3 语法分析自动生成工具 ?
语法分析在词法分析提供的单词流的基础上，对源代码的结构做总体分析。主要任务是：按照文法识别出词法分析器提供的各类语法成分
，同时进行语法检查，检查它是否能由源语言的文法产生，为语义分析和代码生成做准备。 语法分析器在编译器中的地位如图1
3.3所示。 图13.3 语法分析器在编译器中的位置13.3 语法分析自动生成工具 ?语法分析器的作用主要有两点：① 根据词
法分析器提供的记号流，为语法正确的输入构造分析树(或语法树)。② 检查输入中的语法(可能包括词法)错误，并调用出错处理器进行适当处
理。13.3 词法分析自动生成工具 ? 13.3.1 YACC系列语法分析自动生成工具简介YACC是语法分析器生成
工具中最著名的、也是最早开发出来的采用LALR(1)分析算法的语法分析生成器，它源于贝尔实验室UNIX计划，最初由S.C.John
son设计开发，是20世纪70年代初期的产物；基本原理：读取语法规范，该规范包含被编译语言的文法以及该文法产生式中每一个可替代者对
应的动作。然后YACC生成语法分析器，该语法分析器一旦发现就将执行与每一个可替代者对应的动作代码。YACC工具的输入表示方法称为Y
ACC规范，而工具本身则称为YACC编译器。YACC除了具有自动生成特性外，还有一些默认规则来处理二义性文法和操作符顺序，大大简化
了语法分析器设计时的手工劳动。 13.3 语法分析自动生成工具 ? 13.3.1 YACC系列语法分析自动生成工具简
介1．YACC的使用方法 YACC的使用方法见图13.4所示图13.4 用YACC创建一个语法分析器的操
作步骤13.3 语法分析自动生成工具 ? 13.3.1 YACC系列语法分析自动生成工具简介2．YACC文法输入文
件的格式a. 完整的YACC源程序由用两组%%分隔的3部分组成：声明部分%%翻译规则%%程序部分 其中，声明部分和程序部分是可省
略的，但规则部分是必须的。b. 因此，YACC源程序文件的最简形式是： %%规则部分13.3 语法分析自动生成工具
? 13.3.1 YACC系列语法分析自动生成工具简介【例13.5】 为了说明怎样准备YACC源程序，构造一个简单的
台式计算器，该计算器读入一个算术表达式，计算表达式的值，然后打印输出表达式的结果值。台式计算器的建立从下面的表达式文法开始：
E → E + T | T T → T F | F F → ( E ) | digit记号digit是0～9的单
个数字。 13.3 语法分析自动生成工具 ? 13.3.1 YACC系列语法分析自动生成工具简介13.3 语法分
析自动生成工具 ? 13.3.1 YACC系列语法分析自动生成工具简介3．使用带有二义性文法的YACC规约 修改上例
的YACC说明，使台式计算器更加有用。首先，让台式计算器计算表达式序列，每行一个，还允许表达式之间有空白行。为做到这一点，修改第一
条为 1ines ： lines expr ''\n'' { printf("%g\n",$2)；}
| 1ines''\n'' | / empty / ; 在
YACC中，第三行那样的空白产生式表示?。其次，扩展表达式的种类，使之可以包含由多个数字位组成的数值，包括算符+、-(一元和二元)
、和/。最简单的描述方法是用下面的二义文法： E → E + E | E – E | E E | E / E | (E
) | – E | NUMBER 13.3 语法分析自动生成工具 ?13.3 语法分析自动生成工具 ?yylex( ){
int c; while((c = getchar( ).) == '''') ; if((c == ''.'')||(is
digit(c)) ){ ungetc(c,stdin); scanf("%lf", &yylval);
return NUMBER; } return c;}————————————————————13.3 语法分析
自动生成工具 ?lines : lines expr ''\n'' {printf("%g\n", $2);}
| lines ''\n'' | / ? / ;expr
: expr ''+'' expr {$$ = $1 + $3;} | expr ''-'' ex
pr {$$ = $1 - $3;} | expr '''' expr {$$ = $1 $3;
} | expr ''/'' expr {$$ = $1 / $3;} | ''
('' expr '') '' {$$ = $2;} | ''-'' expr %prec UMINUS {
$$ = - $2;} | NUMBER ;%%13.3 语法分析自动生成工具 ?
13.3.1 YACC系列语法分析自动生成工具简介4．YACC中的冲突解决默认方式下，YACC按下面两条规则来解决语法分析中的所
有动作冲突：①“归约-归约”冲突：从冲突产生式中选择在YACC说明中最先出现的那个产生式。②“移进-归约”冲突：总是移进优先于归约
。这条规则正确地解决了悬空else二义性所产生的“移进-归约”冲突。 除此之外，YACC提供了一个通用的机制来解决“移进-归约”冲
突。在声明部分，我们可以为终结符指定优先级和结合性。例如：? 声明：% left ‘+’‘-’ 使得算符+和算符–有相同的优先级
，并且都是左结合的。? 声明：% right ‘↑’ 使得算符↑为右结合。此外，还可以声明一个运算符是非结合性的二目运算符(即该
运算符的两次相邻出现不能合并到一起)，例如：% nonassoc ‘<’。13.3.1 YACC系列语法分析自动生成工具简介5．Y
ACC中的错误处理 YACC中，错误恢复可以使用出错误产生式的形式。 YACC把错误产生式当做普通产生式处理，根据这个规约生
成一个语法分析器，通过这种方法来处理 YACC在文法中加入形如“A → error ?”的错误产生式，其中“A”是一个主要
的非终结符，“?”是一个可能为空的文法符号串，error 是YACC的一个保留字。13.3 语法分析自动生成工具 ?13.3
语法分析自动生成工具 ? 13.3.2 其他语法分析自动生成工具简介1．BisonGNU Bison实际上是使用
最广泛的一种类YACC的通用目的的语法分析自动生成工具，它将LALR(1)上下文无关文法的描述转化成分析该文法的C程序。 Biso
n不但与YACC兼容，还具有许多YACC不具备的特性。Bison最新版本是Bison 2.1，该版本的最大改进就是支持以C++语言
做为输出，并且在分析器的本地化输出中有多项改进。13.3 语法分析自动生成工具 ? 13.3.2 其他语法分析自
动生成工具简介2．CUP/BYACC/J YACC的Java版本叫做CUP (Constructor of Useful Pars
er)，由乔治技术学院图形可视化和使用中心的Scott E. Hudson所开发。CUP和YACC非常相似，也是一个LALR(1)
的语法分析器生成器，但动作代码是用Java书写的。13.3 语法分析自动生成工具 ? 13.3.2 其他词法分析
自动生成工具简介3．PCCTS/ANTLR YACC使用的是LALR(1)分析，而ANTLR采用的是LL(1)分析，不过它
具有连接词法分析和语法分析的能力。 ANTLR能够提供从包含动作的语法描述到识别器构建、解释器、编译器以及翻译器的框架生成的
语言工具，可以生成多种目标语言。 此外，ANTLR还有一个相对复杂的语法开发支持环境，是由Jean Bovet写的ANTLR
Works。 13.3 语法分析自动生成工具 ? 13.3.2 其他语法分析自动生成工具简介4．JavaCC
(Java Compiler Compiler) JavaCC是SUN公司开发的、用Java语言编写的与ANTLR非常
相似的一个编译器自动生成工具，所产生的文件都是纯Java代码。 与ANTLR类似，JavaCC也是采用LL算法，可以同时
进行词法和语法分析的自动分析工具。 和YACC等一样，JavaCC不直接支持分析树或抽象语法树(AST)的生成，如果要完成这些功能，用户需要自己编写相应的代码。幸运的是，JavaCC有一个扩充工具JJTree支持分析树或抽象语法树的生成。 13.3 语法分析自动生成工具 ? 13.3.2 其他语法分析自动生成工具简介5．SableCC 作为一种编译器自动生成工具，SableCC不仅产生词法和语法分析器，而且还创建完整的一组Java类，严格地说，SableCC是一个用Java编程语言来生成编译器(或解释器)的面向对象的框架，该框架基于两个基本的设计决策：首先利用面向对象技术自动构建严格类型的抽象语法树，该语法树能够匹配被编译语言的文法，并且简化调试。其次，该框架使用经过扩展的Visitor访问者模式来生成树遍历(tree-walker)类，这样抽象语法树上节点动作的实现就可以使用继承机制。上述两个设计决策保证SableCC能够在短周期内构建一个编译器。 13.3 语法分析自动生成工具 ? 13.3.2 其他语法分析自动生成工具简介6．其他语法分析生成器工具简介 Grammatica是一个C#和Java的语法剖析器生成器(Parser Generator) ，支持LL(k)语法分析，允许向前看的字符数没有限制，同时也是GNU LGPL下的开源软件； RunCC是一种在运行时生成Parsers和Lexers的语法分析生成器，它的特色是简单，源代码的生成是可选的，只生成一个独立、可运行、能识别Unicode码的词法分析器和为识别语法的简单扩展巴科斯范式(Extended Backus-Naur Form，EBNF)表示的文件。 Any question ? |
|
