构建编译器的工具
第一部分: JFlex 和 CUP
by Richard A. Sevenich, Department of Computer Science, Eastern Washington University
March 25, 1999
在UNIX世界里，传统上有两种在功能上互补的编译器构造工具存在。
一种用来构造编译器的词法分析程序（又称为“词法分析器”或者是“词法扫描程序”）例如：lex、JLex、JFlex等
另一种则是用来构造分析程序语法的程序（通常称为“语法分析器”或者“词法分析器”、“词法程序”）例如：byacc、bison、CUP
这些工具，在Linux/GNU平台上你都可以轻易找到，而且通常是GPL版权的自由软件。（比较广泛使用的编译器生成工具还有PCCTS和Antlr ?）需要指出的是，词法分析和语法分析只是一个语言解释器的基本部分。一个使用上述工具构造的出来的词法分析器和语法分析器无法完成另一件至关紧要的事——生成目标代码。不过这些工具通常提供给编程者一些被称为“钩子”的接口，使用者可以使用它将代码生成部分和词法及语法分析器合为一体。
在以后的文章中，我将简单介绍两种具有代表性的编译工具：JFlex和CUP。我要在选修我的编译器设计课程的学生中选一些来帮助我共同完成这篇文章。最终。我希望能够使那些对这些工具还不十分熟悉的人能够熟练的使用它们。之所以选取JFlex和CUP是因为它们可以用来实现基于JAVA语言的编译器，这也是我学习JAVA的一个好机会。同样，对JAVA的不了解也成为我的“替罪羊”（委过的猪肉? ）。当我犯错误时，我可以归罪于对JAVA不熟悉。
第一部分将为以后的内容提供一个背景介绍。下一部分将告诉你如何得到这些工具以及如何安装和使用，我还会提供一个简单的创建应用的例子。第三部分将给一个实际的应用实例（在下面会介绍）。如果第三部分过大而无法一次刊出，会将它分成几个部分依次刊登。
词法分析器
语言转换器的作用是将某种语言的源代码转换成另一种语言的目标代码。传统的编译器一般是将[url=http://www.pccode.net].net" class="wordstyle"源码转换成汇编语言或机器语言——但这并不是我们在以后的文章中所要讨论的重点。语言转换器处理过程的第一步一般是做类似于英文教师检查一篇英文短文，确定文中是否存在单词拼写错误这样的一个动作。所不同的是词法分析器代替了英文教师的角色，而检查的对象就是源代码。词法分析器挨个检查那些符号是否构成合法的单词。词法分析器将：
辨认出“while”是一个关键字
辨认出“47452”是一个十进制数字
报告字符串“fr%$glp:) ”是一个无法辨认的字符串
词法分析器就类似一个源代码的拼写检查器
一个象JFlex这样的词法工具，从一个指定的文件中读入词法规则，然后生成相应的词法分析器。我们不妨假设某个程序员需要定义一个名为pronto的语言，于是他将语言pronto的有效词法规则写在一个叫'pronto.flex'的文件中。然后再以命令行方式执行操作：'JFlex pronto.flex'。这样他就可以得到一个叫'Lexer.java'的JAVA程序，这个程序就是一个JAVA版本的pronto的词法分析器。
当然，这样一个单独的词法分析器仅有简单的功能，它除了可以告诉你程序是不是完全由合法的单词组成之外不能完成任何其他事情。我们要讨论的词法分析器可以做更多的事情。它们和句法程序共同完成一些任务（在下一个标题中我们会讨论这个问题）。在典型的应用中，词法分析器实际上是被句法程序调用以完成以下任务：
辨认出一个词，并将该词相对应的标志值返回给句法程序；
传送给句法程序与这个被辨认出来的字符串相关的信息，或者是这个整数的数值；
在辨认出单词之后，调用一些可编程的函数。
这三项任务中的第一项使得词法分析器可以支持句法程序完成它的最重要的工作，句法分析。而其余两项任务对于句法程序最终生成目标文件是相当有用的。
句法分析器（又称句法程序）
继续上一节的话题，如同词法分析器检查拼写错误一样，句法分析器通过检查源文件来保证所有的“单词”都是按照有效的语法规则排列的。举例来说，对于某种“新”语言，词法分析器将会判断下面六个单词有效，并将它们报告给句法程序：
{if + while }} -词法分析器只关心单词和符号的有效性，而不在乎它们出现的地方。不过，句法程序将会指出‘{ if + while }}'是一个不合法的组合。这就好象是词法分析器只检查拼写错误，而句法程序检查句法错误。
[注意：实际编译器中的词法规则都是通过非常简单的所谓“正则语法”表达式描述的，而语法分析器的语法规则则是通过较为简单的“上下文无关语法”表达式描述的。相关描述可以参照Chomsky hierachy的Typical compiler design books一书中有相关的理论介绍（国内的朋友可以参考编译原理的相关书籍?）]
象CUP这样的工具，是通过从指定的文件中读入相应语言的语法规则的定义来生成对应的句法程序。我们继续使用虚构的新语言pronto，程序员需要将语法规则写入指定的文件‘pronto.cup'内，然后在命令行下执行‘java java_cup.Main < pronto.cup'，它会生成多个文件。其中有一个文件就是语言pronto的JAVA版的句法分析器，‘parser.java'。
当然了，这样一个简单的句法分析器除了能告诉你程序是不是符合语言的语法之外，什么也做不了。我们所要讨论的句法程序将要完成更多的任务。在判断程序正确与否的同时，程序还要调用相应的代码来进行一些编码（例如，读到变量定义的地方时，需要对定义的变量进行记录? ）。‘钩子函数'一般以两种方式来支持目标代码的生成：
在句法分析完成之后再生成执行代码；
在句法分析的同时就生成可执行的代码。
（这里提到可执行代码，还是指编译器而言，而不是前文所称的语言传换器? ）
面向应用语言
我们所要讨论的这些工具可以被用来开发那些成熟语言的转换器，如C,Pascal,FORTRAN,Perl等等。它们组成了主要的开发项目。这里我想讨论那些为“专用应用语言（ASL）”所编写的程序转换器，这是很时髦的项目，同时，也是很有用处的。我要通过两个例子来向你们说明“专用应用语言”的含义。
例子之一：一个通用的工业控制语言
让我们假设一个虚构的人物——Fred，他为一家生产工业控制器的公司工作。当Fred被雇佣的时候，公司已经开发出一个强大的、用途广泛的、基于广泛应用的并行机制的控制语言。但是最终成为这些语言的使用者的是客户，这些客户可能是化学工程师，或者机械工程师，或技术员等等。他们即没有热情也没有兴趣去学习一门新的用途广泛的编程语言。公司产品的应用范围十分广泛，在多个工业领域内得到使用——汽车、石油工业、卫星控制等等。
Fred被派去为所有可以应用的工业领域做语言的前端（front end）工作。在每一个工作任务中，语言都要被改造，以适应该领域的客户，让他们可以很容易的掌握和使用它。换而言之，前端的性质类似是一个GUI，用户要填入各种变动以利用控制语言达到自己的应用目的。总之，这些不同的前端都是完全不同的新的语言，它们的目标语言就是公司的多用途的控制语言。每一个前端就是一个很好“专用应用语言（ASL）”的例子。通过使用编译构造工具，给Fred带来了很多好处：
可以检查用户源代码的语法和词法错误，并返回有意义的错误信息；
构造每一个专用语言的过程都是相似的；
那些语法和词法描述文件都具有高度可重用性。
例子之二：基于模糊逻辑的通用决策包
模糊逻辑被证明不仅仅是在它的传统领域——工业控制，而且在决策领域也是非常有用的。它可以用在股票市场的分析（可以使你减少损失？）或者帮助企业选择研究和市场战略，以预测各种可能的情况。
让我们假设另外一个Fred——Sally，编制了一个通用的模糊决策系统。它可以根据不同的初始化数据文件对不同的问题作出决策。Sally希望将这个产品应用到不同的领域内。但是，以前的用户占用了Sally的大量时间。这个问题大大的困扰了Sally。产品的用户都是各自领域的专家，他们编制初始化的数据文件以供模糊逻辑模型作出判断。但随着时间的推移，专家们又有新的知识希望加入到模型内，这就需要不断的对初始文件进行修改。由于初始文件的格式是较为严苛的，需要仔细编写。而这些用户只是各自领域的专家，而不是程序员，于是在准备数据文件时就十分容易犯错误。然后他们就很经常的和Sally联系，希望能够得到她的帮助。他们往往需要Sally在很短的时间内解决问题，而为了自己的声誉和商业利益，Sally不得不去解决这些问题。
她的解决方案是编制一个可以自动生成初始文件的“傻瓜”前端，这个前端根据不同领域客户的术语和问题空间进行定制。这个前端就是一个以初始化文件为目标语言的“专用应用语言（ASL）”。这个转换器可以利用编译工具进行创作。就象Fred为工业控制语言所做的那样。转换器将保证数据文件在词法或者句法上都保持正确。
如果这个转换器做的十分出色，用户将会发现它是很有用的。请注意：这些客户在自己领域内的问题的描述方法是十分清楚的。对于这些描述方法，作为一个程序员，Sally几乎是一无所知。客户将问题用自己的描述方法表达出来，而传换器将它翻译成正确的初始化数据文件。
结语
以上两个例子明显有一个共同的主题。Sally和Fred在设计前端“专用应用语言（ASL）”时必须和相应领域的客户紧密合作。毕竟，这些ASL对那些不熟悉编程的领域专家来说也是相当重要的。如果合作不成功，这个ASL就不会被接受，也就不可能开拓进一步的市场。
这个模糊逻辑的例子将是这个学期编译设计课的Project。假设Sally不介意我们这样做。