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",&quot;_"] ( ["a"-"z","A"-"Z","_&quot;,"0"-"9"] )* >

　　| < NUM: ( [&quot;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那樣使用嚴格的文法表示格式，復雜的系統參數了。