《{电子公司企业管理}编译原理简明讲义第2版)冯秀芳,崔冬华,段富电子教》由会员分享，可在线阅读，更多相关《{电子公司企业管理}编译原理简明讲义第2版)冯秀芳,崔冬华,段富电子教（45页珍藏版）》请在金锄头文库上搜索。
1、,编译原理简明教程,普通高等教育“十二五”规划计算机教材,-太原理工大学 -计算机科学与技术学院 -冯秀芳、崔冬华、段富等,第一章 引言 第二章 形式语言理论基础 第三章 自动机理论基础 第四章 词法分析 第五章 语法分析自顶向下分析方法 第六章 语法分析自底向上分析方法 第七章 语义分析及中间代码的生成 第八章 代码优化 第九章 目标代码的生成 第十章 符号表 第十一章 目标程序运行时的存储组织与分配 第十二章 出错处理 第十三章 编译程序自动生成工具简介 第十四章 面向对象语言的编译 第十五章 并行编译技术,目 录,第十三章 编译程序自动生成工具简介,学习目标 了解和掌握高级语言编译程序自
2、动生成工具的种类 了解和掌握几种常用的词法分析自动生成工具用法 了解和掌握几种常用的语法分析自动生成工具用法,词法分析、语法分析、一遍扫描分析和多遍扫描分析等，其实都是非常机械的过程，完全可以由计算机代替人工完成，由此出现了词法和语法分析的自动生成工具，本章简单介绍这种自动生成工具的发展、作用、分类以及目前常用的工具应用。 学习本章后，学生应该能够掌握使用编译程序自动生成工具完成高级语言词法和语法分析的基本方法，具有设计、实现、分析和维护编译器的词法和语法分析的初步能力。,13.1 引言 13.1.1 编译程序自动生成工具简介 13.1.2 编译程序自动生成工具的种类及常用工具简介 13.2
3、词法分析自动生成工具 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
4、.2 编译程序自动生成工具的种类及常用工具简介 由于在编译器实现过程所包含的几个阶段中，词法分析和语法分析的实现原理明确，操作步骤确定，可以借助于计算机来自动完成，所以编译程序自动生成工具主要包含词法分析和语法分析两种类型。 早期的研究一般是分别给出词法和语法分析的实现工具，如UNIX操作系统平台上的LEX和YACC； 现在的一些工具则将词法和语法分析的实现集成在一起，而且也不再局限于用C语言实现，出现了很多基于Java语言且可以生成多种目标语言的词法和语法分析工具，比如ANTLR和JavaCC %,/* 正则表达式定义 */ delim tn ws delim+ letter A-Za-z
5、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 (THEN); else return (ELSE); id yylval = (int) installID().; return(ID); numberyylval = (int) installNum().; return(NUMBER); “
6、” yylval = NE; return(RELOP); “” yylval = GT; return(RELOP); “=” yylval = GE; return(RELOP); line printf(“%5d %s”, lineno+, yytext); %,13.2.1 LEX系列词法分析自动生成工具简介 int installID()/* 将词素初始化到符号表中的函数，返回一个指针；其中yytext是指向词素开头的指针，yyleng存放刚找到的词素的长度 */ int installID() /* 与installID相似，但初始化和存放的是数字常量 */ main() yyle
7、x(); return 0; ,13.2 词法分析自动生成工具,13.2 词法分析自动生成工具,13.2.1 LEX系列词法分析自动生成工具简介 5Lex中的冲突解决 Lex解决冲突的两个规则，即当输入的多个前缀与一个或多个模式匹配时，Lex用下列规则选择正确的词素： 总是选择最长的前缀。 如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式。,13.2 词法分析自动生成工具,13.2.2 其他词法分析自动生成工具简介 1FLex Flex(Fast Lex)是最常见的Lex开源版本，它是由Free Software Foundation创建的Gnu Compiler Pac
8、kage的一部分，可以在许多Internet 站点上免费得到。与其配套的开源语法分析器编译工具是Bison，这组工具使用C语言来指定动作代码(我们使用属性“动作”来指代由编程人员所写的在词法或语法分析执行部分某个特定点要执行的代码)。,13.2 词法分析自动生成工具,13.2.2 其他词法分析自动生成工具简介 2JLex JLex是Lex的一个Java版本，由普林斯顿大学计算机科学系的一个学生Elliot Joel Berk开发。JLex在功能上与Flex非常相似，它接受类似Lex文件格式的词法分析文件，生成Java源代码格式的词法分析器。与其配套的语法分析器编译工具是CUP(Construc
9、tor of Useful Parsers，YACC的Java版本)或BYacc/J(Bob Jamison对经典Berkeley YACC的Java扩展) 。,13.2 词法分析自动生成工具,13.2.2 其他词法分析自动生成工具简介 3PCCTS/ANTLR PCCTS (Purdue Compiler Construction Tool Set)主要是由Terence Parr开发的集词法、语法分析于一体的编译自动生成工具，最初PCCTS是用C+语言写的，产生的目标代码也是C+。PCCTS开发的主要目的是应对使用Lex/YACC系列工具解决编译问题时所产生的复杂性。后来PCCTS1.33
10、版本转向了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 其他
11、词法分析自动生成工具简介 4JavaCC(Java Compiler Compiler) JavaCC是SUN公司开发的、用Java语言编写的与ANTLR非常相似的一个编译器自动生成工具，所产生的文件都是纯Java代码。 与PCCTS/ANTLR一样，JavaCC集词法分析生成器和语法分析生成器于一体，可以同时完成对输入文件的词法分析和语法分析的工作，使用起来相当方便。JavaCC和它所自动生成的语法分析器可以在多个平台上运行。另外，JavaCC可以看成Java世界里的一个类Lex/YACC工具，同是也是一个可以免费获取的通用工具，它遵循BSD License(Berkeley Softwar
12、e Distribution License)，可以自由使用，也可以在很多Java相关的工具下载网站下载，当然，要获得最新版本的JavaCC，还是在官网https:/JavaCC,13.2 词法分析自动生成工具,13.2.2 其他词法分析自动生成工具简介 5SableCC SableCC是一种新的生成Java目标代码的编译器自动生成工具，同时具有词法和语法分析的功能。其实现原理与PCCTS/ANTLR、JavaCC类似，其中的词法分析也是作为语法分析的一部分而构成整个系统的。SableCC可以从网站http:/sablecc.org/免费获取。,13.3 语法分析自动生成工具,语法分析在词法分
13、析提供的单词流的基础上，对源代码的结构做总体分析。主要任务是：按照文法识别出词法分析器提供的各类语法成分，同时进行语法检查，检查它是否能由源语言的文法产生，为语义分析和代码生成做准备。 语法分析器在编译器中的地位如图13.3所示。,图13.3 语法分析器在编译器中的位置,13.3 语法分析自动生成工具,语法分析器的作用主要有两点： 根据词法分析器提供的记号流，为语法正确的输入构造分析树(或语法树)。 检查输入中的语法(可能包括词法)错误，并调用出错处理器进行适当处理。,13.3 词法分析自动生成工具,13.3.1 YACC系列语法分析自动生成工具简介 YACC是语法分析器生成工具中最著名的、也
14、是最早开发出来的采用LALR(1)分析算法的语法分析生成器，它源于贝尔实验室UNIX计划，最初由S.C.Johnson设计开发，是20世纪70年代初期的产物； 基本原理：读取语法规范，该规范包含被编译语言的文法以及该文法产生式中每一个可替代者对应的动作。然后YACC生成语法分析器，该语法分析器一旦发现就将执行与每一个可替代者对应的动作代码。 YACC工具的输入表示方法称为YACC规范，而工具本身则称为YACC编译器。YACC除了具有自动生成特性外，还有一些默认规则来处理二义性文法和操作符顺序，大大简化了语法分析器设计时的手工劳动。,13.3 语法分析自动生成工具,13.3.1 YACC系列语法
15、分析自动生成工具简介 1YACC的使用方法 YACC的使用方法见图13.4所示,图13.4 用YACC创建一个语法分析器的操作步骤,13.3 语法分析自动生成工具,13.3.1 YACC系列语法分析自动生成工具简介 2YACC文法输入文件的格式 a. 完整的YACC源程序由用两组%分隔的3部分组成： 声明部分 % 翻译规则 % 程序部分 其中，声明部分和程序部分是可省略的，但规则部分是必须的。 b. 因此，YACC源程序文件的最简形式是： % 规则部分,13.3 语法分析自动生成工具,13.3.1 YACC系列语法分析自动生成工具简介 【例13.5】 为了说明怎样准备YACC源程序，构造一个简
16、单的台式计算器，该计算器读入一个算术表达式，计算表达式的值，然后打印输出表达式的结果值。台式计算器的建立从下面的表达式文法开始： E E + T | T T T * F | F F ( E ) | digit 记号digit是09的单个数字。,13.3 语法分析自动生成工具,13.3.1 YACC系列语法分析自动生成工具简介,13.3 语法分析自动生成工具,13.3.1 YACC系列语法分析自动生成工具简介 3使用带有二义性文法的YACC规约 修改上例的YACC说明，使台式计算器更加有用。 首先，让台式计算器计算表达式序列，每行一个，还允许表达式之间有空白行。为做到这一点，修改第一条为 1ines ： lines expr n printf(%gn,$2)； | 1inesn | /* empty */ ; 在YACC中，第三行那样的空白产生式表示。 其次，扩展表达式的种类，使之可以包含由多个数字位组成的数值，包括算符+、-(一元和二元)、*和/。
