解析器生成器和词法分析生成器：javaCC

　　javaCC是一个解析器生成器和词法分析生成器。解析器和词法分析器用于处理输入的字符串。编译器和解释器被用来和解析器/词法分析器一起处理文件中的程序。但是解析器/词法分析器在实际中有更加广泛的应用，正如我在本文中希望介绍的一样。 那么，什么是解析器/词法分析器?词法分析器可以吧一个字符串分离成若干叫做“Token”的子字串，并同时对这些Token进行分类。考虑下面的程序：

　　int main(){

　　return 0;

　　}

　　一个C语言的词法分析器将会把这段代码分离成下列子串：

　　int \s main ( ) \s { \n \t

　　return \s 0 \s ; \n } \n \s

　　同时，它会对这些子串分类，在本例中分类结果是：

　　KWINT SPACE ID OPAR CPAR SPACE OBRACE SPACE SPACE

　　KWRETURN SPACE OCTALCONST SPACE SEMCOLON SPACE CBRACE SPACE EOF

　　EOF表示文件(输入)结束，这些Token串将会被送到解析器，在C语言中，解析器并不需要所有这些Token，本例中的分类为SPACE的token就被忽略了。解析器将会分析这些Token串来决定程序的结构。通常在编译器中，解析器输出的是程序的树状结构。这个树会被编译器中的代码生成模块处理。考虑程序中的一个语句：

　　F=32.0+9.0*C/5.0

　　解析器将分析这个语句并根据规则生产下面的树：

　　MISSING PIC

　　如果输入不符合目标词法和词法时，词法分析器和解析器同时也负责生产错误信息。 JavaCC本身并不是一个词法分析器或者解析器而是一个代码生成器，这意味着它可以根据输入的语言定义输出一个词法分析器和解析器。JavaCC输出的代码是合法的可编译Java代码。 解析器和词法分析器本身就是一个冗长而复杂的组件，手工编写一个这样的程序需要仔细考虑各条件的相互作用，例如分析C语言时，处理整数的代码不可能和处理浮点的代码相互独立，因为整数和浮点数的开头都是数字。而使用像JavaCC这样的分析器生成器时处理整数的规则和处理浮点数的规则是分开书写的，而两者之间的共享代码在代码生成是被自动添加了。这就增强了程序的模块性，同时也意味着定义文件较手工编写的Java代码来说更加易于编写，阅读和更改。通过 JavaCC这样的解析器生成器，程序员们能节省更多时间，同时也能增加编写的软件的质量。

　　第一个例子——我们来做加法吧!

　　作为第一个例子，我们将计算一连串整数的加法，请看下面的例子：

　　99+42+0+15

　　我们忽略所有数字和符号间的空格和换行符，除此之外，我们不接受除了10个数字和加号之外的其他字符。 这一节的剩下的部分中的代码都是文件adder.jj的一部分。这个文件包含了符合JavaCC词法的解析器/词法分析器的定义，并且将作为JavaCC 程序的输入文件。

　　选项和类定义

　　这个文件的第一部分是：

　　/*adder.jj 吧一堆数字相加*/

　　options{

　　STATIC = false;

　　}

　　PARSER_BEGIN(Adder)

　　public class Adder{

　　public static void main(String[] args) throws ParseException, TokenMgrError{//作者这里没有加public,这会在某些情况下产生错误(译注)

　　Adder parser = new Adder(System.in);

　　parser.Start();//方法名竟然是大写开头的，真不地道(翻译吐槽)

　　}

　　}

　　PARSER_END(Adder)

　　开头部分的options节说明了除了我们明确指定的STATIC选项，所有其他的JavaCC选项为都默认值。关于 JavaCC选项的详细信息，请参考JavaCC文档。接下来我们定义了一个名为Adder的Java类，但是我们并没有写出这个类的全部代码，JavaCC会在处理时自动生成其他的代码。main方法声明抛出的ParserException和TokenMgrError有可能在执行这些代码时被抛出。

　　指定一个词法解析器吧!

　　我们待会儿在看那个main函数，现在我们首先来定义一个词法分析器。在这个简单的例子中，词法分析器的定义只有下面4行：

　　SKIP:{“ “}

　　SKIP:{“\n”|”\r”|”\r\n”}

　　TOKEN:{< PLUS : “+”>}

　　TOKEN:{< NUMBER : ([“0”-“9”])+ >}

　　* 第一行说明了空格是一个token,但是会被忽略。于是乎解析器并不会收到任何单独的空格。

　　* 第二行也说了差不多的事情，只不过被忽略的是换行符，我们用一个小竖线分割了不同的匹配模式。

　　* 第三行告诉JavaCC一个单独的加号是一个token,并且给这个Token一个名字：PLUS。

　　* 最后一行叫JavaCC吧连续的数字当作一个token,命名为NUMBER,如果你使用过Perl或者 Java的正则表达式库，就应该能明白定义的含义。让我们仔细看一下这个表达式([“0”-“9”])+。圆括号中间的部分[“0”-“9”]是一个匹配所有数字字符的正则表达式(不过正则表达式好像不用引号 ——译者吐槽)，这表明所有unicode中的0-9之间的支付都能被匹配。其他的部分：(x)+可以匹配一连串符合模式x的字符。所以表达式 ([“0”-“9”])+就可以匹配一个或者多个连续的数字。这四行中的每一行都被称作一个“正则表达式结果(regular expression production)”

　　还有另一种可以被词法分析器生成的token，它的名字是EOF，正如其名，代表了输入的终止。不能，也不需要任何对EOF的匹配，JavaCC会自动生成他们。 考虑下面的输入：

　　“123 + 456\n”

　　我们定义的词法分析器将会找到7个token: NUMBER, 空格, PLUS, 又一个空格, 另一个数字,一个换行, 然后是EOF，当然，标记了SKIP的token不会被传到解析器。于是乎，我们还没出生的解析器会看到这些东西:

　　NUMBER, PLUS, NUMBER, EOF

　　现在试想一个我们没有想到的问题:如果有其他字符呢?例如：

　　“123 – 456\n”

　　在处理完第一个空格之后，我们的可爱的词法分析器将遇到一个不认识的字符：减号，由于没有任何token的定义可以容纳一个减号，词法分析器将会扔一个TokenMgrError出来以示抗议。 现在我们看看另一种情况：

　　“123++456\n”

　　我们的词法分析器会得出如下结论：

　　NUMBER,PLUS,PLUS,NUMBER,EOF

　　当然，词法分析器并不能知道这个token序列是否有意义，这通常是解析器的工作。我们接下来要定义的解析器会找到这个有两个加号的错误，然后完美的罢工。所以解析器实际上处理的只有：

　　NUMBER,PLUS,PLUS

　　同时，跳过(skip)一个token并不代表忽略(ignore)。考虑下列输入：

　　“123 456\n”

　　词法分析器会发现3个token:两个NUMBER和一个空格。然后解析器又会优美的罢工了……

　　出现吧，我的解析器!

　　解析器的定义使用了一种叫BNF范式的东西，这看起来有点像Java的方法定义：

　　void Start(): //马勒戈壁，BS不按标准写代码的(神秘的译者再吐槽)

　　{}

　　{

　　

　　(

　　

　　

　　)*

　　

　　}

　　这个BNF范式声明了一个有效的token序列的模式，从而避免了错误的语法。我们研究一下它的意思：一个以 NUMBER开头的序列，以EOF结束，中间存在若干以一个PLUS和一个NUMBER组成的子序列。 正如所见，一个解析器仅仅决定了一个输入序列是否合法，而没有吧数字们实际上加起来。待会儿我们会来调教这个解析器好让他能够好好的干活，但是首先我们先让我们目前的成果跑一下吧!

　　开始炼成解析器和词法分析器咯!

　　我们已经有一个叫adder.jj的文件了，接下来我们用JavaCC进行提炼。原作者罗嗦了一堆OS 相关的玩意儿我们掠过不表，直接看就行了：

　　E:\javacc-book>javacc adder.jj

　　Java Compiler Compiler Version 4.2 (Parser Generator)

　　(type "javacc" with no arguments for help)

　　Reading from file adder.jj . . .

　　File "TokenMgrError.java" does not exist. Will create one.

　　File "ParseException.java" does not exist. Will create one.

　　File "Token.java" does not exist. Will create one.

　　File "SimpleCharStream.java" does not exist. Will create one.

　　Parser generated successfully.

　　这个操作生成了7个Java类，每个都在独立的java文件中：

　　* TokenMgrError是一个简单的错误类;用于表示词法分析器参数的错误，父类是java.lang.Throwable

　　* ParserException 是另一个代表错误的异常类;表示解析器罢工的情况，父类是java.lang.Excpetion

　　* Token是表示token的类，每个Token对象都有一个int类型的字段：kind，表示它的类型(PLUS,NUMBER或者EOF)(其实应该用enum的，不过JDk1.5以前是没有的，所以将就了吧——翻译的技术性吐槽)和一个String类型的字段：image，存储了token所代表的内容。

　　* SimpleCharStream 是一个辅助类，用于吧输入的字符串传给词法分析器

　　* AdderConstants 是一个包含了常量的辅助性接口

　　* AdderTokenManager 就是传说中的词法分析器咯

　　* Adder就是可爱的解析器

　　现在我们可以把它们编译一下咯～

　　E:\javacc-book>javac *.java

　　注意：Adder.java 使用了未经检查或不安全的操作。

　　注意：要了解详细信息，请使用 -Xlint:unchecked 重新编译。

　　终于要运行咯!

　　现在我们来回头看看 Adder这个类吧。

　　static void main(String[] args) throws ParseException,TokenMgrError{

　　Adder parser = new Adder(System.in);

　　parser.Start();//方法名竟然是大写开头的，真不地道(翻译吐槽)

　　}

　　首先注意，这里的方法声明直接抛出了ParseException和TokenMgrError，事实上这不是一个好习惯，我们应该捕捉这些异常并进行一定的处理(哪怕是简单的报错)，但是为了节约篇幅，这些玩意儿统统不要了。

　　* 第一个语句创建了一个解析器实例，构建函数使用了自动生成的接受一个java.io.InputStream的重载。其实还有一个(更好的)接受Reader实例的重载(java建议在处理字符串时尽量使用 Reader(Writer)而不是InputStream(OutputStream),这样能更好的避免字符编码带来的问题——翻译如是说)。这个构建函数创建了一个SimpleCharStream对象和我们的词法分析器AdderTokenManager的实例。于是乎，词法分析器通过 SimpleCharStream顺利的获取到了我们的输入。

　　* 第二句调用了一个由 JavaCC生成的方法Start()，对于每个BNF范式来说JavaCC都会生成一个对应的方法。这个方法负责尝试在输入序列中寻找符合模式的输入，例如，调用Start时会使解析器试图寻找一个匹配下面模式的输入序列：

　　()*

　　让我们来准备一个合适的输入然后运行这个程序吧!

　　E:\javacc-book>java Adder

　　我们运行程序，输入表达式以后，会出现下面3中不同情况：

　　1. 出现词法错误：本例中，词法错误只出现在遇到未知字符时，我们可以通过下面的输入引发一个词法错误：

　　“123-456\n”

　　这种情况下，程序会完美的罢工并扔个 TokenMrgError出来以示抗议，这个异常的message是：

　　Lexical error at line 1, column 4. Encountered: "-" (45), after : ""

　　1. 出现一个解析错误：这发生在输入序列不符合Start的BNF范式时，例如

　　“123++456\n”

　　或者

　　“123 456\n”

　　或者

　　“\n”

　　这时，程序会扔一个ParseException出来，像这样：

　　Exception in thread "main" ParseException: Encountered " "1 "" at line 2, column 1.

　　Was expecting one of:

　　

　　"+" ...

　　1. 输入的串完美的符合了Start的定义，这时，程序什么都不做(囧——翻译又忍不住吐槽了)

　　由于解析器除了挑错什么都不做，所有现在这个程序除了检查输入合法性以外什么都做不了，在下一节，我们将调教这个程序让他能为我们做我们爱做的事情，敬请期待，次回もお楽しみに。

　　看一下我们的劳动成果吧!

　　要了解JavaCC生成的代码是如何工作的，最好的办法是看看他生成的代码是什么。

　　final public void Start() throws ParseException {

　　jj_consume_token(NUMBER);

　　label_1:

　　while (true) {

　　switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {

　　case PLUS:

　　;

　　break;

　　default:

　　jj_la1[0] = jj_gen;

　　break label_1;

　　}

　　jj_consume_token(PLUS);

　　jj_consume_token(NUMBER);

　　}

　　jj_consume_token(0);

　　}

　　方法jj_consume_token将试图从输入中读取一个指定类型的token，如果得到的token与期望的类型不符，则抛出一个异常。表达式(jj_ntk==-1)?jj_ntk():jj_ntk计算下一个未读token的类型。而最后一行则要求匹配EOF的token。

　　让我们调教解析器吧!

　　向上文中提到的start方法一样的，由JavaCC根据BNF文法生成的方法，在默认情况下仅仅是检查了输入是否符合规则，但是我们可以教BNF做更多事情，我们可以在BNF中间夹杂Java代码，JavaCC为我们提供了骨骼，而我们要为他提供肌肉。 下面我们来给adder.jj中的BNF做些许改动，添加的代码用黑体表示：

　　int start() throws NumberFormatException:

　　{

　　Token t;

　　int i;

　　int value;

　　}

　　{

　　t=

　　{i=Integer.parseInt(t.image);}

　　{value=i;}

　　(

　　

　　t=

　　{i=Integer.parseInt(t.image);}

　　{value+=I;}

　　)*

　　

　　{return value;}

　　}

　　首先，我们定义了BNF结果的返回类型，然后还声明了NumberFormatException可能在处理时抛出。然后我们定义了一个叫t的Token变量，我们想要获取BNF匹配结果时可以这样用：

　　t=

　　在BNF中的大括号里，我们可以在里面写任何Java语句，这些语句会原封不动的copy到生产的代码里面。

　　由于更改了start的返回类型，我们有必要更改一下我们的 main函数：

　　public static void main(String[] args) throws ParseException,TokenMgrError{

　　Adder parser = new Adder(System.in);

　　System.out.println(parser.Start());//方法名竟然是大写开头的，真不地道(翻译吐槽)

　　}

　　在结束这个例子前，我们再做一点小小的改进，下面的代码在start中出现了两次：

　　{i=Integer.parseInt(t.image);}

　　{value=i;}

　　为了避免代码重复，最好把它们独立出来，我们把提取出来的范式称作Primary,那么我们应该如此这般的更改我们的代码：

　　int start() throws NumberFormatException:

　　{

　　Token t;

　　int i;

　　int value;

　　}

　　{

　　value=Primary()

　　(

　　

　　i= Primary()

　　{value+=I;}

　　)*

　　

　　{return value;}

　　}

　　int Primary() throws NumberFormatException:

　　{

　　Token t;

　　}

　　{

　　t=

　　{return Integer.parseInt(t.image);}

　　}

　　这时我们再来看看JavaCC所生成的代码：

　　final public int start() throws ParseException, NumberFormatException {

　　Token t;

　　int i;

　　int value;

　　value = Primary();

　　label_1:

　　while (true) {

　　switch ((jj_ntk==-1)?jj_ntk():jj_ntk) {

　　case PLUS:

　　;

　　break;

　　default:

　　jj_la1[0] = jj_gen;

　　break label_1;

　　}

　　jj_consume_token(PLUS);

　　i = Primary();

　　value+=I;

　　}

　　jj_consume_token(0);

　　{if (true) return value;}

　　throw new Error("Missing return statement in function");

　　}

　　final public int Primary() throws ParseException, NumberFormatException {

　　Token t;

　　t = jj_consume_token(NUMBER);

　　{if (true) return Integer.parseInt(t.image);}

　　throw new Error("Missing return statement in function");

　　}

　　待会儿我们还能看到如何向BNF传递参数。

　　第二个例子——大家来学算术

　　接下来，我们继续改进我们的adder,使它成为一个简易的四则运算计算器。 首先，作为开始，我们先让它能够和我们进行交互，每行作为一个单独的表达式进行计算输出。

　　选项和类定义

　　calculator0.jj的开头如下：

　　options {

　　STATIC = false;

　　}

　　PARSER_BEGIN(Calculator)

　　import java.io.PrintStream

　　public class Calculator {

　　public static void main( String[] args ) throws ParseException, TokenMgrError, NumberFormatException {

　　Calculator parser = new Calculator( System.in );

　　parser.Start( System.out );

　　}

　　double previousValue = 0.0;

　　}

　　PARSER_END(Calculator)

　　变量previousValue 用于保存最后一个计算的表达式的值。我们待会儿将允许在表达式中使用一个$符号表示这个值。import语句可以写在PARSER_BEGIN和 PARSER_END中间，他们将被复制到生成的类文件中，包定义同样也在这时声明。

　　词法定义

　　词法定义的改变不大，首先，换行符不再被忽略，而声明成一个token，这使得换行可以被解析器处理。

　　SKIP:{" "}

　　TOKEN:{< EOL : "\n"|"\r"|"\r\n" >}

　　TOKEN:{< PLUS : "+">}

　　第二，我们将允许小数参与运算，所以我们要更改Number的定义使得它允许小数点被匹配，这一共有4中形式：没有小数部分，既有小数部分又有整数部分，只有小数点和小数部分，只有整数部分和小数点。于是我们声明如下：

　　TOKEN:{< NUMBER :

　　(["0"-"9"])+|

　　(["0"-"9"])+”.” (["0"-"9"])+ |

　　(["0"-"9"])+”.”|

　　”.” (["0"-"9"])+

　　>}

　　我们又发现相同的正则表达式出现了好多次，这显然不是个好现象，所有我们可以给一部分表达式起一个名字，这个名字仅仅在这个词法分析器中有效，而且不代表任何token类型，定义起来类似这样：

　　TOKEN:{< NUMBER : | ”.” | ”.”|”.” >}

　　TOKEN : {< #DIGITS : (["0"-"9"])+ >}

　　看起来简单多了，不是么?

　　解析器定义

　　解析器的输入包括了数个行序列，每行都包含一个表达式，使用BNF表示这种结构就是：

　　Start ->(Expression EOL)* EOF

　　这就可以引出我们的BNF定义了：

　　void Start():

　　{}

　　{

　　(

　　Expression()

　　

　　)*

　　

　　}

　　我们另外添加了一些Java代码，让他能打印出每行表达式的值：

　　void Start(PrintStream PS) throws NumberFormatException :

　　{}

　　{

　　(

　　previousValue = Expression()

　　

　　ps.println(previousValue);

　　)*

　　

　　}

　　每个表达式都包括了一个或者多个数字和加号(目前它还只认加号)组成的序列，用BNF表示如下：

　　expression -> primary (PLUS primary)*

　　这里的primary表示数字，这个BNF翻译成JavaCC格式就是：

　　double Expression() throws NumberFormatException :

　　{

　　double i;

　　double value;

　　}

　　{

　　value= primary()

　　(

　　

　　i=primary()

　　{ value+=I;}

　　)*

　　{ return value;}

　　}

　　这个和adder.jj中start的定义惊人的相似啊，不过我们吧int改成了double。 primary的定义也和adder.jj中的差不多，用BNF表示为：

　　Primary -> NUMBER

　　所有JavaCC的代码除了类型什么都不变:

　　double primary() throws NumberFormatException:

　　{

　　Token t;

　　}

　　{

　　t=

　　{return Double.parseDouble(t.image);}

　　}

　　总结一下我们得到的BNF吧：

　　Start ->(Expression EOL)* EOF expression -> primary (PLUS primary)* Primary -> NUMBER

　　现在我们的calculator.jj已经可以做一些加法运算了哦～

　　教它学减法吧!

　　现在我们来教他如何做减法，首先要让他认识减法操作符——减号，然后还要有乘号和除号。不过我们还是先从减号开始吧，给词法定义里加一句：

　　TOKEN :{ < MINUS : "-" > }

　　在定义EOL和NUMBER时我们使用了小竖线分割不同选项，现在我们要使用同样的方法吧减号添加进 EXPRESSION的定义中，我们的BNF如下：

　　Expression -> Primary((PLUS|MINUS) Primary)*

　　还有另外一种形式：

　　Expression -> Primary(PLUS Primary |MINUS Primary)*

　　因为第二种形式处理起来更简单些，所有我们用第二种形式。这样我们就可以得到新的JavaCC代码了：

　　double Expression() throws NumberFormatException :

　　{

　　double i;

　　double value;

　　}

　　{

　　value= primary()

　　(

　　

　　i=primary()

　　{ value+=I;}

　　|

　　

　　i=primary()

　　{ value-=I;}

　　)*

　　{ return value;}

　　}

　　还有乘法和除法呢～

　　要教会它计算乘和除是件很简单是事情，我们直接上代码了。

　　TOKEN:{< TIMES : "*" > }

　　TOKEN:{< DIVIDE : "/" > }

　　我们还应该更改Expression的定义，现在他的BNF是：

　　Expression -> Primary(PLUS Primary | MINUS Primary | TIMES Primary| DIVIDE Primary)*

　　从存储的句法角度看，这一点错没有，但是他并不能正确的表达我们的意思，因为没有考虑运算优先级，例如我们输入

　　2*3+4*5

　　我们希望得到的是(2*3)+(4*5)但是我们却得到了((2*3)+4)*5!所有我们不得不使用另外的两个表达方式：

　　Expression -> Term (PLUS Term |MINUS Term)* Term -> Primary(TIMES Primary |DIVIDE Primary)*

　　这样表达式被分成了一连串的加减运算，加减的元素是Term. 我们要做的仅仅是吧Expression中的Primary改成Term:

　　double Expression() throws NumberFormatException :

　　{

　　double i;

　　double value;

　　}

　　{

　　value= primary()

　　(

　　

　　i=term()

　　{ value+=I;}

　　|

　　

　　i=term()

　　{ value-=I;}

　　)*

　　{ return value;}

　　}

　　随后，我们给出term的定义：

　　double term() throws NumberFormatException :

　　{

　　double i;

　　double value;

　　}

　　{

　　value= primary()

　　(

　　

　　i=term()

　　{ value*=I;}

　　|

　　

　　i=term()

　　{ value/=I;}

　　)*

　　{ return value;}

　　}

　　括号，单目操作符和历史记录

　　现在我们还需要添加少许其他功能使它变成一个真正的有用的计算器，我们需要括号支持，负数支持，还要允许使用$表示上一次表达式计算的值。 显然，我们又要更改词法定义了，翠花，上酸菜～

　　TOKEN:{< OPEN_PAR : "(" > }

　　TOKEN:{< CLOSE_PAR : ")" > }

　　TOKEN:{< PREVIOUS : "$" > }

　　我们不需要为取负做任何词法更改，因为我们只需要用到减号(MINUS)而已。 现在要改变的是Primary的规则，一共有4种可能性：一个数，一个$，一个括号包起来的表达式，或者一个符号和一个Primary 使用BNF表示就是：

　　Primary -> NUMBER

　　| PERIVOUS

　　| OPEN_PAR Expression CLOSE_PAR

　　| MINUS Primary

　　这个BNF有两路递归，最后一个是直接递归，倒是第二个是间接递归。在BNF中使用递归是允许的，但是有若干限制。考虑下列表达式：

　　- - 22

　　这将会被理解成：

　　[-[-[22]]]

　　在解析表达式时，每个方括号被当成一个Primary，例如

　　12 * ( 42 + 19 )

　　将会被理解成

　　12 * [([42]+[19])]

　　通过这个我们可以看到，Primary这个BNF是如何被递归调用的。 现在我们给出Primary的完整定义：

　　double Primary() throws NumberFormatException:

　　{

　　Token t;

　　double d;

　　}

　　{

　　t=

　　{return Double.parseDouble(t.image);}

　　|

　　

　　{ return previousValue;}

　　|

　　 d=Expression()

　　{ return d;}

　　|

　　 d=Primary()

　　{return d;}

　　}

　　终于，我们完成了我们的计算器，现在整个的calcualtor.jj就可以正常的工作了，当然，我们能做的改进仍然很多，比如添加新的操作符，这些工作就留给各位看官了。 这种计算结果的方式被称做“直接解释”，也就是说解析器自己吧输入解析成数值然后运算掉了。对于简单的表达式来讲，这工作的很好，但是对于复杂的表达式来讲远远不够，比如我们需要引入某种循环，考虑下面的表达式：

　　sum I : 1..10 of i*i

　　这就是一个典型的数学上的求和运算，这时直接求值就不能使用了，因为i*i没有任何数字可供计算。

　　对于这种情况，最好的办法就是让解析器吧表达式表示成其他什么形式，比如树，或者某种字节码，然后再解析完成后再计算。