Javacc的获取

　　同lex和yacc一样，javacc也是一个免费可以获取的通用工具，它可以在很多JAVA相关的工具下载网站下载，当然，javacc所占的磁盘空间比起lex和yacc更大一些，里面有标准的文档和examples。相对lex和yacc来说，javacc做得更人性化，更容易一些。如果你实在找不到javacc，还是可以联系我，我这里有。现在最新的就是javacc 3.2版本。

　　Javacc的原理

　　Javacc可以同时完成对text的词法分析和语法分析的工作，使用起来相当方便。同样，它和lex和yacc一样，先输入一个按照它规定的格式的文件，然后javacc根据你输入的文件来生成相应的词法分析于语法分析程序。同时，新版本的Javacc除了常规的词法分析和语法分析以外，还提供JJTree等工具来帮助我们建立语法树。总之，Javacc在很多地方做得都比lex和yacc要人性化，这个在后面的输入文件格式中也能体现出来。

　　Javacc的输入文件

　　Javacc的输入文件格式做得比较简单。每个非终结符产生式对应一个Class中的函数，函数中可以嵌入相应的识别出该终结符文法时候的处理代码(也叫动作)。这个与YACC中是一致的。

　　Javacc的输入文件中，有一系列的系统参数，比如其中lookahead可以设置成大于1的整数，那么就是说，它可以为我们生成LL(k)算法(k>=1)，而不是简单的递归下降那样的LL(1)算法了。要知道，LL(2)文法比起前面讨论的LL(1)文法判断每个非终结符时候需要看前面两个记号而不是一个，那么对于文法形式的限制就更少。不过LL(2)的算法当然也比LL(1)算法慢了不少。作为一般的计算机程序设计语言，LL(1)算法已经是足够了。就算不是LL(1)算法，我们也可以通过前面讲的左提公因式把它变成一个LL(1)文法来处理。不过既然javacc都把lookahead选择做出来了，那么在某些特定的情况下，我们可以直接调整一个lookahead的参数就可以，而不必纠正我们的文法。

　　下面我们来看看Javacc中自带的example中的例子。

　　例5.1

　　这个例子可以在javacc-3.2/doc/examples/SimpleExamples/Simple1.jj看到

　　PARSER_BEGIN(Simple1)

　　public class Simple1 {

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

　　Simple1 parser = new Simple1(System.in);

　　parser.Input();

　　}

　　}

　　PARSER_END(Simple1)

　　void Input() :

　　{}

　　{

　　MatchedBraces() ("\n"|"\r")*

　　}

　　void MatchedBraces() :

　　{}

　　{

　　"{" [ MatchedBraces() ] "}"

　　}
 
　　设置好javacc的bin目录后，在命令提示符下输入

　　javacc Simple1.jj

　　然后 javacc 就会为你生成下面几个 java 源代码文件

　　Simple1.java

　　Simple1TokenManager.java

　　Simple1Constants.java

　　SimpleCharStream.java

　　Token.java

　　TokenMgrError.java
 
　　其中Simple1就是你的语法分析器的对象，它的构造函数参数就是要分析的输入流，这里的是System.in.class Simple1 就定义在标记 PARSER_BEGIN(Simple1)，PARSER_END(Simple1) 之间。但是必须清楚的是，PARSER_BEGIN和PARSER_END中的名字必须是词法分析器的名字(这里是Simple1)。PARSER_END下面的定义就是文法非终结符号的定义了。

　　Simple1的文法基本就是：

　　Input -> MatchedBraces ("\n"|"\r")*

　　MatchedBraces -> “ { “ MatchedBraces “ } ”

　　从它的定义我们可以看到，每个非终结符号对于一个过程。

　　比如Input的过程

　　void Input() :
　　{}

　　{

　　MatchedBraces() ("\n"|"\r")*

　　}
 
　　在定义void Input后面记住需要加上一个冒号 ”:”，然后接下来是两个块 {} 的定义。

　　第一个 {} 中的代码是定义数据，初试化数据的代码。第二个 {} 中的部分就是真正定义Input的产生式了。每个产生式之间用 ”|” 符号连接。

　　注意：这里的产生式并非需要严格BNF范式文法，它的文法既可以是BNF，同时还可以是混合了正则表达式中的定义方法。比如上面的　Input -> MatchedBraces ("\n"|"\r")* 中 (“\n”|”\r”)* 就是个正则表达式，表示的是 \n 或者 \r 的 0 个到无限个的重复的记号。而是javacc系统定义的记号 (TOKEN)，表示文件结束符号。除了，无论是系统定义的TOKEN，还是自定义的TOKEN，里面的TOKEN都是以的方式表示。

　　每个非终结符号 (Input 和 MatchedBraces) 都会在javacc生成的Simple1.java中形成Class Simple1的成员函数。当你在外部调用Simple1的Input，那么语法分析器就会开始进行语法分析了。

　　例 5.2

　　在javacc提供的example里面没有。javacc提供的example里面提供的例子中SimpleExamples过于简单，而其它例子又过于庞大。下面我以我们最常见的数学四则混合运算的文法来构造一个javacc的文法识别器。这个例子是我自己写的，十分简单。其中还包括了文法识别同时嵌入的构建语法树Parse-Tree的代码。不过由于篇幅的原因，我并没有给出全部的代码，这里只给了javacc输入部分相关的代码。 而Parse-tree就是一个普通的4叉树，3个child，1个next( 平行结点 )，相信大家在学习数据结构的时候应该都是学过的。所以这里就省略过去了。[SPAN]

　　在大家看这些输入代码之前，我先给出它所使用的文法定义，好让大家有个清楚的框架。

　　Expression -> Term{ Addop Term }
　　Addop -> "+" | "-"

　　Term -> Factor { Mulop Factor }

　　Mulop -> "*" | "/"

　　Factor -> ID | NUM | "("Expression")"
 
　　这里的文法可能和BNF范式有点不同。{}的意思就是0次到无限次重复，它跟我们在学习正则表达式的时候的”*”符号相同，所以，在Javacc中的文法表示的时候，{…}部分的就是用(…)*来表示。

　　为了让词法分析做得更简单，我们通常都不会在文法分析的时候，使用 ”(”,”)“ 等字符号串来表示终结符号，而需要转而使用 LPAREN，RPAREN这样的整型符号来表示。

　　PARSER_BEGIN(Grammar)
　　public class Grammar implements NodeType {

　　public ParseTreeNode GetParseTree(InputStream in) throws ParseException

　　{

　　Grammar parser =new Grammar(in);

　　return parser.Expression();

　　}

　　}

　　PARSER_END(Grammar)

　　SKIP :

　　{

　　" " | "\t" | "\n" | "\r"

　　}

　　TOKEN :

　　{

　　< ID: ["a"-"z","A"-"Z","_"] ( ["a"-"z","A"-"Z","_","0"-"9"] )* >

　　| < NUM: ( ["0"-"9"] )+ >

　　| < PLUS: "+" >

　　| < MINUS: "-" >

　　| < TIMERS: "*" >

　　| < OVER: "/" >

　　| < LPAREN: "(" >

　　| < RPAREN: ")" >

　　}

　　ParseTreeNode Expression() :

　　{

　　ParseTreeNode ParseTree = null;

　　ParseTreeNode node;

　　}

　　{

　　( node=Simple_Expression()

　　{

　　if(ParseTree == null)

　　ParseTree =node;

　　else

　　{

　　ParseTreeNode t;

　　t= ParseTree;

　　while(t.next != null)

　　t=t.next;

　　t.next = node;

　　}

　　}

　　)*

　　{ return ParseTree;}

　　}

　　ParseTreeNode Simple_Expression() :

　　{

　　ParseTreeNode node;

　　ParseTreeNode t;

　　int op;

　　}

　　{

　　node=Term(){}

　　(

　　op=addop() t=Term()

　　{

　　ParseTreeNode newNode = new ParseTreeNode();

　　newNode.nodetype = op;

　　newNode.child[0] = node;

　　newNode.child[1] = t;

　　switch(op)

　　{

　　case PlusOP:

　　newNode.name = "Operator: +";

　　break;

　　case MinusOP:

　　newNode.name = "Operator: -";

　　break;

　　}

　　node = newNode;

　　}

　　)*

　　{ return node; }

　　}[SPAN]

　　int addop() : {}

　　{

　　 { return PlusOP; }

　　| { return MinusOP; }

　　}

　　ParseTreeNode Term() :

　　{

　　ParseTreeNode node;

　　ParseTreeNode t;

　　int op;

　　}

　　{

　　node=Factor(){}

　　(

　　op=mulop() t=Factor()

　　{

　　ParseTreeNode newNode = new ParseTreeNode();

　　newNode.nodetype = op;

　　newNode.child[0] = node;

　　newNode.child[1] = t;

　　switch(op)

　　{

　　case TimersOP:

　　newNode.name = "Operator: *";

　　break;

　　case OverOP:

　　newNode.name = "Operator: /";

　　break;

　　}

　　node = newNode;

　　}

　　)*

　　{

　　return node;

　　}

　　}

　　int mulop() :{}

　　{

　　 { return TimersOP; }

　　| { return OverOP; }

　　}

　　ParseTreeNode Factor() :

　　{

　　ParseTreeNode node;

　　Token t;

　　}

　　{

　　t=

　　{

　　node=new ParseTreeNode();

　　node.nodetype= IDstmt;

　　node.name = t.image;

　　return node;

　　}

　　|

　　t=

　　{

　　node=new ParseTreeNode();

　　node.nodetype= NUMstmt;

　　node.name = t.image;

　　node.value= Integer.parseInt(t.image);

　　return node;

　　}

　　|

　　 node=Simple_Expression()

　　{

　　return node;

　　}

　　}

　　其中SKIP中的定义就是在进行词法分析的同时，忽略掉的记号。TOKEN中的，就是需要在做词法分析的时候，识别的词法记号。当然， 这一切都是以正则表达式来表示的。

　　这个例子就有多个非终结符号，可以看出，我们需要为每个非终结符号写出一个过程。不同的非终结符号的识别过程中可以互相调用。

　　以Simple_Expression()过程为例，它的产生式是Expression -> Term { addop Term }，而在javacc的输入文件格式是，它的识别是这样写的node=Term(){} ( op=addop() t=Term(){ … })* 前面说过，这里的 ”*” 符号和正则表达式是一样的，就是0次到无限次的重复 。那么Simple_Expression等于文法Term Addop Term Addop Term Addop Term … 而Addop也就相当于PLUS和MINUS两个运算符号。这里我们在写Expression的文法的时候，同时还使用了赋值表达式，因为这个和Yacc不同的时候，Javacc把文法识别完全地做到了函数过程中，那么如果我们要识别Simple_Expression的文法，就相当于按顺序识别Term和Addop两个文法，而识别那个文法，就相当于调用那两个非终结符的识别函数。正是这一点，我觉得Javacc的文法识别处理上就很接近程序的操作过程，我们不需要像YACC那样使用严格的文法表示格式，复杂的系统参数了。