用 CUP 构 造 编 译 器 的 方 法

1、用 CUP 构 造 编 译 器 的 方 法论文摘要：介绍了编译器自动生成器的根本原理，通过设计一个简单的计算器，说明使用CUP(Constructor of Useful Parsers)构造编译器的方法。论文关键词：编译器,分析器生成器0引言高级语言编译程序是计算机系统软件最重要的组成局部之一。通常所说的编译程序(即编译器)是指这样一个程序，它能够把某种高级语言写的源程序转换成低级语言写的目标程序，而后者与前者在逻辑上是等价的。本文首先简单介绍了编译器的设计原理，然后重点探讨了如何利用基于Java的CUP构造编译器。1编译器设计原理编译过程通常分为五个阶段：词法分析、语法分析、语义分析与中间

2、代码生成、优化、目标代码生成。由于词法分析远比语法分析简单，而语义分析通常采用语法制导翻译，故语法分析是整个编译系统的关键。并非所有编译程序都分成这五阶段，有些简单的编译程序是在语法分析的同时产生目标代码的。构造一个好的高级语言编译程序的根底是要对输入的单词符号进行词法分析，核心是要根据词法分析的结果进行语法分析。要完成最简单的日常解析任务，不需要使用像分析器生成器那样复杂的东西。但是，一旦某种语言的语法变得复杂，那么其中的有效表达式数量将迅速膨胀。而将任意表达式解析成其组成局部所需的代码将变得越来越困难。幸运的是，有许多词法和语法分析器的自动生成工具。利用了这些工具，设计人员不再需要费心于分

3、析器的具体实现，而只需用正那么表达式描述单词符号的构词规那么，用上下文无关文法描述语言的文法规那么即可。词法分析器(又称扫描器)和语法分析器(简称分析器)的自动生成工具将描述这些规那么的文件分别作为源文件，即可生成相应的扫描器和分析器。分析器自动生成工具的作用在于：它使设计人员从开发时间长，可读性差，不易调试，不易移植，可维护性和可扩充性更差，可靠性也不高，效率极低的手工构造编译程序中解脱出来。设计人员只需关注于词法和语法规那么的制定，这不仅缩短了开发周期，提高了开发效率，而且大大增加了可靠性、可移植性、可维护性和可扩充性。在UNIX世界里，传统上有两种在功能上互补的编译器构造工具存在。一种用

4、来构造编译器的词法分析器，例如：Lex、JLex、JFlex等，另一种那么是用来构造语法分析器，例如：byacc、bison、CUP。需要指出的是，词法和语法分析只是一个语言解释器的根本局部。一个使用上述工具构造出来的词法分析器和语法分析器无法完成另一件至关紧要的事生成目标代码。不过这些工具通常提供应编程者一些被称为钩子;的接口，使用者可以使用它将代码生成局部和词法及语法分析器合为一体。语法分析器可以分为截然不同的两类。一类是自顶向下的递归下降分析器或LL分析器。另一类是自底向上的表驱动的LR分析器，此类方法效率高，没有左递归的问题，对语法规那么限制少，容易生成语法树。实际上，大多数的分析器生

5、成器如：YACC和本文使用的CUP，都使用了一种LR算法。LR分析器是由总控程序和LR分析表构成的，不同的LR分析法、不同的文法，其LR分析总控程序是相同的，差异仅在于LR分析表的不同，故LR语法分析器的自动构造实质就是LR分析表的自动构造。LALR分析法，是LR分析法的一个变种，它将相互联系的工程集合并在一起，从而压缩了分析表的大小。这个算法虽然比LR分析法能力稍差一些，但远比LR分析法实用的多。YACC是UNIX系统所提供的经典的语法分析工具，人们经常使用这个工具来生成语法分析器。现在，在JAVA下已经有了它的替代品CUP，它几乎实现了YACC的所有特性。2如何用CUP设计编译器下面通过对

6、一个计算器的CUP源文件的介绍，来说明CUP源文件的结构和由CUP构造一个编译器的方法(本例把计算器支持的表达式看作一种简单的语言来处理)。21一个计算器的CUP源程序*Preliminaries*packagejava_cupcalc；importjava_cup.runtime*；*TerminalsandNon-terminals*terminalPLUS，MINUS，TIMES，DIVIDE；terminalSEMI，LPAREN，RPAREN；terminalIntegerNUMBER；nonterminalexpr_list，expr_part；nonterminalInteger

7、expr；*Precedences*precedencelelfPLUS，MINUS；precedencelefnTIMES，DIVIDE;*Thegrammar*expr_list=expr_listexpr_partlexpr_part；expr_part=expr:eSEMIexpr=expr：elPLUSexpr：e2：RESULT=newInteger(e1intValue()+Value()；:|expr：elMINUSexpr：e2：RESULT=newInteger(e1intValue()-e2intValue()；:|expr：elTIMESexpr：e2：RESULT=n

8、ewInteger(e1intValue()*e2intValue()；：|expr：elDIVIDEexpr：e2：RESULT=newInteger(e1intValue()e2intValue()；:|NUMBER：n：RESULT=n;:|LPARENexpr：eRPAREN：RESULT=e；：；22CUP源程序的分析一个CUP源程序由预先声明、符号列表、优先级及结合性声明、语法规那么四个局部组成。这一段提供多种预先声明来指定如何产生分析器，并提供运行时的代码。这个段是可选的，并不一定要被包含在一个CUP源文件中。对于我们的计算器，在这个段中有两个项。第一项为哪一项一个包声明，然后是

9、导入类声明。其它可选的预先声明项都以假设干关键字和：;开始，以：;结尾，所有的java代码都写在中间。所有这些java代码会被直接复制到产生的分析器的类定义中，这些选项主要有parsercode;、initwith;、scanwith;等。(2)符号列表这个段包括终结符和非终结符的列表，并为每个终结符和非终结符提供类型。这个段是CUP源文件必需的。终结符声明的语法是：terminalClassnamenamel，name2，；Classname是符号对应的java类型，如：Integer。如果不写Classname，那么被认为是Object类型。在Classname后面罗列声明为该类型的终结符

10、的名字，各终结符以逗号分隔，例如：terminalUMINUS，LPAREN，RPAREN；terminalIntegerNUMBER；注意，这里只有NUMBER有一个相应的类型。在我们的例子里，它是唯一有值的终结符。例如，当词法分析器识别了一个PLUS符号，就会把表示终结符PLUS的代码传递给语法分析器；但是当它识别了一个NUMBER，它不仅要传递表示终结符NUMBER的代码，还要将其具体的值一同传递。非终结符以同样的方式声明。唯一的区别是声明以nonterminal起始，以说明它是一个非终结符。(3)终结符的优先级和结合性这个段指明终结符的优先级和结合性，它是可选的段。本段主要用于处理二义

11、文法。虽然，可以通过调整语法结构使它没有二义性来省略本段，但是，用二义性文法的LR分析和同样语言非二义性文法的LR分析相比可提高对输入串分析的速度。当给出了二义性文法终结符之间的优先关系和结合性的规定后，可能会解决LR工程集中的冲突。例如，TIMES应该有比PLUS高的优先级。当语法分析器遇到一个语句比方5+4*3，它不知道这个表达式应该按照5+(4*3)计算还是按照(5+4)*3计算。为了用这个段消除这种二义性，需要如下来声明优先级。最高的优先级从列表的底部，向上递减。left表示在那个优先级中终结符的结合性是从左到右。例如：precedenceleftPLUS，MINUS；preceden

12、celeftTIMES，DIVIDE；由此，语法分析器知道该表达式应该按照5+(4*3)计算。(4)语法规那么CUP源文件的最后是语法规那么。语法中的每一个产生式的中间是：=;，它将整个产生式分割为左右两边，左边是一个非终结符，右边是零或多个终结符、非终结符和内嵌java代码，内嵌的java代码放在一对定界符：和：之间，最后以一个分号结束，右边的符号都可以有标号。例如：expr：=expr：elPLUSexpr：e2：RESULT=newInteger(e1intValue()+e2intValue()；：产生式右边第一个非终结符expr有个标号e1，第二个有个标号e2。而产生式左边总是有隐含

13、的标号RESULT。在运行时，所有产生式中出现的符号都会由一个分析栈中的一个Symbol类的对象来表示。各标号就是这些对象的实例变量值的引用。在表达式expr：elPLUSexpr：e2中，e1、e2都是Integer类型对象的引用，这些对象都位于分析栈中表示这些非终结符的Symbol类型对象的值域中。产生式中RESULT也是Integer类型的，因为expr被声明为Integer类型。这个对象成为一个新的Symbol对象的实例变量值。23与词法分析器(扫描器)的整合新版本的CUP对扫描器的整合作了重大改良，使得CUP与JLex、JFlex等自动生成的扫描器结合得更好。改良后的CUP要求扫描器

14、必须实现如下接口：packagejava_cupruntime；publicinterfaceScannerpublicSymbolnext_token()throwsjava1angException；由于我们的计算器的例子十分简单，可以直接手工编写出一个扫描器。对于复杂的语法，可以利用JFlex之类的工具自动生成。24CUP的出错恢复机制下面简单地介绍一下CUP的出错恢复机制，CUP使用了与YACC一样的局部出错恢复机制。LR分析表包含移进、归约、接收和出错动作。当分析器遇到出错动作时将停止分析并报告出错。这种做法可能对程序员是很不友好的，因为程序员希望分析器能够报告程序中所有的错误，而不

15、仅仅是一个。局部出错恢复机制的原理包括：检测出错位置，允许分析器依据自己的判断来调整栈和输入。局部恢复机制，使用了特殊的error符号以控制恢复进程。当这一特殊的eror符号在文法规那么中出现时，一个错误输入符号列就得到了匹配。25编译器的生成和运行首先直接手工编写一个扫描器，名为Lexer.java。然后将我们的CUP源文件保存为calc.cup。在命令行下输入：为了运行我们的计算器程序，还需要一个包含main函数的类，为此创立一个名为Test.java的文件，其唯一的函数如下：staticpublicvoidmain(Stringargv)tryparserP=newparser(newLexer(newFileReader(argv)；Objectresult=P.parse().value；catch(E