论文摘要：介绍了编译器自动生成器的基本原理，通过设计一个简单的计算器，说明使用CUP(Constructor of Useful Parsers)构造编译器的方法。
论文关键词：编译器,分析器生成器
0引言
高级语言编译程序是计算机系统软件最重要的组成部分之一。通常所说的编译程序(即编译器)是指这样一个程序，它能够把某种高级语言写的源程序转换成低级语言写的目标程序，而后者与前者在逻辑上是等价的。
本文首先简单介绍了编译器的设计原理，然后重点探讨了如何利用基于Java的CUP构造编译器。
1编译器设计原理
编译过程通常分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。由于词法分析远比语法分析简单，而语义分析通常采用语法制导翻译，故语法分析是整个编译系统的关键。并非所有编译程序都分成这五阶段，有些简单的编译程序是在语法分析的同时产生目标代码的。
构造一个好的高级语言编译程序的基础是要对输入的单词符号进行词法分析，核心是要根据词法分析的结果进行语法分析。要完成最简单的日常解析任务，不需要使用像分析器生成器那样复杂的东西。但是，一旦某种语言的语法变得复杂，那么其中的有效表达式数量将迅速膨胀。而将任意表达式解析成其组成部分所需的代码将变得越来越困难。幸运的是，有许多词法和语法分析器的自动生成工具。利用了这些工具，设计人员不再需要费心于分析器的具体实现，而只需用正则表达式描述单词符号的构词规则，用上下文无关文法描述语言的文法规则即可。词法分析器(又称扫描器)和语法分析器(简称分析器)的自动生成工具将描述这些规则的文件分别作为源文件，即可生成相应的扫描器和分析器。分析器自动生成工具的作用在于：它使设计人员从开发时间长，可读性差，不易调试，不易移植，可维护性和可扩充性更差，可靠性也不高，效率极低的手工构造编译程序中解脱出来。设计人员只需关注于词法和语法规则的制定，这不仅缩短了开发周期，提高了开发效率，而且大大增加了可靠性、可移植性、可维护性和可扩充性。
在UNIX世界里，传统上有两种在功能上互补的编译器构造工具存在。一种用来构造编译器的词法分析器，例如：Lex、JLex、JFlex等，另一种则是用来构造语法分析器，例如：byacc、bison、CUP。
需要指出的是，词法和语法分析只是一个语言解释器的基本部分。一个使用上述工具构造出来的词法分析器和语法分析器无法完成另一件至关紧要的事生成目标代码。不过这些工具通常提供给编程者一些被称为“钩子”的接口，使用者可以使用它将代码生成部分和词法及语法分析器合为一体。
语法分析器可以分为截然不同的两类。一类是自顶向下的递归下降分析器或LL分析器。另一类是自底向上的表驱动的LR分析器，此类方法效率高，没有左递归的问题，对语法规则限制少，容易生成语法树。实际上，大多数的分析器生成器如：YACC和本文使用的CUP，都使用了一种LR算法。
LR分析器是由总控程序和LR分析表构成的，不同的LR分析法、不同的文法，其LR分析总控程序是相同的，差别仅在于LR分析表的不同，故LR语法分析器的自动构造实质就是LR分析表的自动构造。
LALR分析法，是LR分析法的一个变种，它将相互联系的项目集合并在一起，从而压缩了分析表的大小。这个算法虽然比LR分析法能力稍差一些，但远比LR分析法实用的多。
YACC是UNIX系统所提供的经典的语法分析工具，人们经常使用这个工具来生成语法分析器。现在，在JAVA下已经有了它的替代品CUP，它几乎实现了YACC的所有特性。
2如何用CUP设计编译器
下面通过对一个计算器的CUP源文件的介绍，来说明CUP源文件的结构和由CUP构造一个编译器的方法(本例把计算器支持的表达式看作一种简单的语言来处理)。
2．1一个计算器的CUP源程序
／*Preliminaries*／
packagejava_cup．calc；
importjava_cup.runtime．*；
／*TerminalsandNon-terminals．*／
terminalPLUS，MINUS，TIMES，DIVIDE；
terminalSEMI，LPAREN，RPAREN；
terminalIntegerNUMBER；
nonterminalexpr_list，expr_part；
nonterminalIntegerexpr；
／*Precedences*／
precedencelelfPLUS，MINUS；
precedencelefnTIMES，DIVIDE;
／*Thegrammar*／
expr_list==expr_listexpr_part
lexpr_part；
expr_part==expr:eSEMI
{:System.out.println(“=”+e)；：}；
expr==expr：elPLUSexpr：e2
{：RESULT=newInteger(e1．intValue()+e2.intValue())；:}
|expr：elMINUSexpr：e2
{：RESULT=newInteger(e1．intValue()-e2．intValue())；:}
|expr：elTIMESexpr：e2
{：RESULT=newInteger(e1．intValue()*e2．intValue())；：}
|expr：elDIVIDEexpr：e2
{：RESULT=newInteger(e1．intValue()／e2．intValue())；:}
|NUMBER：n
{：RESULT=n;:}
|LPARENexpr：eRPAREN
{：RESULT=e；：}；
2．2CUP源程序的分析
一个CUP源程序由预先声明、符号列表、优先级及结合性声明、语法规则四个部分组成。 1/3 1 2 3 下一页 尾页 |
