使用JavaCC做語法分析

　　前言

　　本系列的文章的宗旨是讓大家能夠寫出自己的編譯器解釋器或者腳本引擎所以每到理論介紹到一個程度後我都會來討論實踐問題理論方面編譯原理的教材已經是夠多了而實踐的問題卻很少討論

　　前幾節文章只討論到了詞法分析和LL文法分析關鍵的LR文法分析這裡卻還沒有講我們先不要管復雜的LR文法和算法讓我們使用LL算法來實際做一些東西後再說本文將介紹一個在JAVA上廣泛使用的LL算法分析工具Javacc（這是我唯一能找到的使用LL算法的語法分析器構造工具）這一節的文章並非只針對JAVA開發者如果你是C/C++開發者那麼也請你來看看這個JAVA下的優秀工具或許你將來也用得著它

　　Lex 和yacc這兩個工具是經典的詞法分析和語法分析工具但是它們都是基於C語言下面的工具而使用JAVA的朋友們就用不上了但是JAVA下已經有了lex和yacc的替代品javacc（ Java Compiler Compiler ） 同時javacc也是使用LL算法的工具我們也可以實踐一下前面學的LL算法

　　首先聲明我不是一個JAVA專家我也是剛剛才接觸JAVAJava裡面或許有很多類似javacc一樣的工具但是據我所知javacc還是最廣泛最標准的JAVA下的詞法語法分析器

　　Javacc 的獲取同lex和yacc一樣javacc也是一個免費可以獲取的通用工具它可以在很多JAVA相關的工具下載網站下載當然javacc所占的磁盤空間比起lex和yacc更大一些裡面有標准的文檔和examples相對lex和yacc來說javacc做得更人性化更容易一些如果你實在找不到javacc還是可以聯系我我這裡有現在最新的就是javacc 版本

　　Javacc 的原理

　　Javacc 可以同時完成對text的詞法分析和語法分析的工作使用起來相當方便同樣它和lex和yacc一樣先輸入一個按照它規定的格式的文件然後javacc根據你輸入的文件來生成相應的詞法分析於語法分析程序同時新版本的Javacc除了常規的詞法分析和語法分析以外還提供JJTree等工具來幫助我們建立語法樹總之Javacc在很多地方做得都比lex和yacc要人性化這個在後面的輸入文件格式中也能體現出來

　　Javacc 的輸入文件

　　Javacc 的輸入文件格式做得比較簡單每個非終結符產生式對應一個Class中的函數函數中可以嵌入相應的識別出該終結符文法時候的處理代碼（也叫動作）這個與YACC中是一致的

　　Javacc 的輸入文件中有一系列的系統參數比如其中lookahead可以設置成大於的整數那麼就是說它可以為我們生成LL（k）算法（k>=）而不是簡單的遞歸下降那樣的LL（）算法了要知道LL（）文法比起前面討論的LL（）文法判斷每個非終結符時候需要看前面兩個記號而不是一個那麼對於文法形式的限制就更少不過LL（）的算法當然也比LL（）算法慢了不少作為一般的計算機程序設計語言LL（）算法已經是足夠了就算不是LL（）算法我們也可以通過前面講的左提公因式把它變成一個LL（）文法來處理不過既然javacc都把lookahead選擇做出來了那麼在某些特定的情況下我們可以直接調整一個lookahead的參數就可以而不必糾正我們的文法

　　下面我們來看看Javacc中自帶的example中的例子

　　例

　　這個例子可以在javacc/doc/examples/SimpleExamples/Simplejj看到

　　 PARSER_BEGIN(Simple) 

public class Simple { 

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

    Simple parser = new Simple(Systemin); 

    parserInput(); 

  } 

} 

PARSER_END(Simple) 

void Input() : 

{} 

{ 

  MatchedBraces() (\n|\r)* <EOF> 

} 

void MatchedBraces() : 

{} 

{ 

{ [ MatchedBraces() ] } 

}

　　設置好javacc的bin目錄後在命令提示符下輸入

　　javacc Simplejj

　　然後 javacc 就會為你生成下面幾個 java 源代碼文件

　　 Simplejava 

SimpleTokenManagerjava 

SimpleConstantsjava 

SimpleCharStreamjava 

Tokenjava 

TokenMgrErrorjava

　　其中Simple就是你的語法分析器的對象它的構造函數參數就是要分析的輸入流這裡的是Systemin

　　class Simple 就定義在標記 PARSER_BEGIN（Simple）

　　PARSER_END（Simple） 之間

　　但是必須清楚的是PARSER_BEGIN和PARSER_END中的名字必須是詞法分析器的名字（這裡是Simple）

　　PARSER_END 下面的定義就是文法非終結符號的定義了

　　Simple 的文法基本就是

　　Input > MatchedBraces （\n|\r）* <EOF>

　　MatchedBraces > { MatchedBraces }

　　從它的定義我們可以看到 每個非終結符號對於一個過程

　　比如 Input 的過程

　　 void Input() : 

{} 

{ 

  MatchedBraces() (\n|\r)* <EOF> 

} 

　　在定義 void Input 後面記住需要加上一個冒號 然後接下來是兩個塊 {} 的定義

　　第一個 {} 中的代碼是定義數據 初試化數據的代碼 第二個 {} 中的部分就是真正定義 Input 的產生式了

　　每個產生式之間用 | 符號連接

　　注意 這裡的產生式並非需要嚴格 BNF 范式文法 它的文法既可以是 BNF 同時還可以是混合了正則表達式中的定義方法 比如上面的

　　Input > MatchedBraces （\n|\r）* <EOF>

　　中 （\n|\r）* 就是個正則表達式 表示的是 \n 或者 \r 的 個到無限個的重復的記號

　　而 <EOF> 是 javacc 系統定義的記號 （TOKEN） 表示文件結束符號

　　除了 <EOF> 無論是系統定義的 TOKEN 還是自定義的 TOKEN 裡面的 TOKEN 都是以 <tokens name> 的方式表示

　　每個非終結符號 （Input 和 MatchedBraces） 都會在 javacc 生成的 Simplejava 中形成 Class Simple 的成員函數 當你在外部調用 Simple 的 Input 那麼語法分析器就會開始進行語法分析了

　　例

　　在 javacc 提供的 example 裡面沒有 javacc 提供的 example 裡面提供的例子中 SimpleExamples 過於簡單 而其它例子又過於龐大 下面我以我們最常見的數學四則混合運算的文法來構造一個 javacc 的文法識別器 這個例子是我自己寫的 十分簡單 其中還包括了文法識別同時嵌入的構建語法樹 ParseTree 的代碼 不過由於篇幅的原因 我並沒有給出全部的代碼 這裡只給了 javacc 輸入部分相關的代碼 而 Parsetree 就是一個普通的 叉樹 個 child 個 next（ 平行結點 ） 相信大家在學習數據結構的時候應該都是學過的 所以這裡就省略過去了

　　在大家看這些輸入代碼之前 我先給出它所使用的文法定義 好讓大家有個清楚的框架

　　 Expression > Term{ Addop Term }
Addop > + | 
Term > Factor { Mulop Factor }
Mulop > * | /
Factor > ID | NUM | (Expression) 

　　這裡的文法可能和BNF范式有點不同{}的意思就是次到無限次重復它跟我們在學習正則表達式的時候的*符號相同所以在Javacc中的文法表示的時候{…}部分的就是用（…）*來表示

　　為了讓詞法分析做得更簡單 我們通常都不會在文法分析的時候 使用 （） 等字符號串來表示終結符號 而需要轉而使用 LPAREN RPAREN 這樣的整型符號來表示

　　 PARSER_BEGIN(Grammar) 

public class Grammar implements NodeType { 

  public ParseTreeNode GetParseTree(InputStream in) throws ParseException 

  { 

       Grammar parser =new Grammar(in); 

       return parserExpression(); 

  } 

  

} 

PARSER_END(Grammar) 

SKIP : 

{ 

    | \t | \n | \r 

} 

TOKEN : 

{ 

  < ID: [azAZ_] ( [azAZ_] )* > 

|  < NUM: ( [] )+ > 

|  < 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(tnext != null) 

                   t=tnext; 

               tnext = node; 

    } 

 } 

)* 

  { return ParseTree;} 

  <EOF> 

} 

ParseTreeNode Simple_Expression() : 

{ 

         ParseTreeNode node; 

         ParseTreeNode t; 

         int op; 

} 

{ 

  node=Term(){} 

  ( 

  op=addop() t=Term() 

{ 

                   ParseTreeNode newNode = new ParseTreeNode(); 

                   newNodenodetype = op; 

                   newNodechild[] = node; 

                   newNodechild[] = t; 

                   switch(op) 

                   { 

                            case PlusOP: 

                            newNodename = Operator: +; 

                            break; 

                            case MinusOP: 

                            newNodename = Operator: ; 

                            break; 

                   } 

                   node = newNode; 

         } 

  )* 

  { return node; } 

} 

int addop() : {} 

{ 

         <PLUS> { return PlusOP; } 

|   <MINUS> { return MinusOP; } 

} 

ParseTreeNode Term() : 

{ 

         ParseTreeNode node; 

         ParseTreeNode t; 

         int op; 

} 

{ 

  node=Factor(){} 

  ( 

  op=mulop() t=Factor() 

{ 

                   ParseTreeNode newNode = new ParseTreeNode(); 

                   newNodenodetype = op; 

                   newNodechild[] = node; 

                   newNodechild[] = t; 

                   switch(op) 

                   { 

                            case TimersOP: 

                            newNodename = Operator: *; 

                            break; 

                            case OverOP: 

                            newNodename = Operator: /; 

                            break; 

                   } 

                   node = newNode; 

         } 

  )* 

  { 

       return node; 

  } 

} 

int mulop() :{} 

{ 

         <TIMERS> { return TimersOP; } 

         | <OVER> { return OverOP;   } 

} 

ParseTreeNode Factor() : 

{ 

         ParseTreeNode node; 

         Token t; 

} 

{ 

  t=<ID> 

{ 

           node=new ParseTreeNode(); 

           nodenodetype= IDstmt; 

           nodename = timage; 

           return node; 

         } 

  | 

  t=<NUM> 

  { 

      node=new ParseTreeNode(); 

           nodenodetype= NUMstmt; 

           nodename = timage; 

           nodevalue= IntegerparseInt(timage); 

           return node; 

    } 

  | 

  <LPAREN> node=Simple_Expression() <RPAREN> 

   { 

         return node; 

  } 

}

　　其中 SKIP 中的定義就是在進行詞法分析的同時 忽略掉的記號 TOKEN 中的 就是需要在做詞法分析的時候 識別的詞法記號 當然 這一切都是以正則表達式來表示的

　　這個例子就有多個非終結符號 可以看出 我們需要為每個非終結符號寫出一個過程 不同的非終結符號的識別過程中可以互相調用

　　以 Simple_Expression（） 過程為例 它的產生式是 Expression > Term { addop Term } 而在 javacc 的輸入文件格式是它的識別是這樣寫的 node=Term（）{} （ op=addop（） t=Term（）{ … }）* 前面說過這裡的 * 符號和正則表達式是一樣的就是 次到無限次的重復 那麼 Simple_Expression 等於文法 Term Addop Term Addop Term Addop Term … 而 Addop 也就相當於 PLUS 和 MINUS 兩個運算符號 這裡我們在寫 Expression 的文法的時候同時還使用了賦值表達式因為這個和 Yacc 不同的時候 Javacc 把文法識別完全地做到了函數過程中那麼如果我們要識別 Simple_Expression 的文法就相當於按順序識別 Term 和 Addop 兩個文法 而識別那個文法就相當於調用那兩個非終結符的識別函數 正是這一點我覺得 Javacc 的文法識別處理上就很接近程序的操作過程 我們不需要像 YACC 那樣使用嚴格的文法表示格式復雜的系統參數了

　　關於 Yacc 的使用其實比 Javacc 要復雜還需要考慮到和詞法分析器接口的問題這個我會在以後細細講到

　　至於其它的文法操作解釋我就不再多說了 如果要說 就是再寫上十篇這樣的文章也寫不完 本文只能給讀者們一個方向 至於深入的研究 還是請大家看 javacc 提供的官方文檔資料

　　JavaCC 的下載地址是同時它已經包含了很多語言的grammar模版了譬如htmlxmlpythonvb………等等可以到下載

From:http://tw.wingwit.com/Article/program/Java/JSP/201311/19412.html