JAVACC 入門(轉載)

Java Flash IDEA 算法 Unix   

讀了JavaCC自帶文檔中的SimpleExamples之後，有一點心得，于是總結一下，以備遺忘。

JavaCC的輸入文檔是一個詞法和文法的規範檔案，其中也包括一些動作的描述，它的字尾應該是jj。

簡而言之，一個jj文檔由下面幾個部分構成：

l         Options{}部分：這個部分對産生的文法分析器的特性進行說明，例如向前看的token的個數（用來解除沖突）。這一部分是可以省略的，因為每一個選項都有預設值，當我們沒有對某個選項進行說明時，它就采用預設值。也可以把這些選項作為javacc指令的參數來啟動javacc，可以達到同樣的效果。

l         分析器類的聲明：這個部分指定了分析器類的名字，以及其他類中成員的聲明。這個部分是必須有的。這個部分的聲明如下：

PARSER_BEGIN(classname)

Class classname {

       ……

}

PARSER_END(classname)

l         詞法部分聲明：這裡面有四類：SKIP、TOKEN、SPECIAL_TOKEN、MORE。其中，SKIP用來說明被忽略的串，下面是一個例子：

SKIP {

       “ “

|

       “\n”

|

       “\r”

}

TOKEN用來說明在詞法層次上識别的token，下面是一個例子：

TOKEN {

       <ID: (“a”-“z”|”A”-“Z”)+>

|

       <NUM: (“0”-“9”)+>

}

       這個部分是可以省略的。

在詞法聲明部分，以#開頭的token隻是在詞法分析時使用，不能作為文法分析的輸入，也就是說，它相對詞法分析是局部的。

l         文法聲明和動作代碼：這一部分生成的代碼會直接插入分析器類聲明的結束括号之前。一般而言，文法中的每一個非終結符都對應一個函數，其中函數的形式如下：

Return_type function_name()

{     變量聲明和一些初始化的動作

}

{

       上下文無關文法的右部分，其中每個組成部分的形式如下：

       文法部分 {動作部分}

兩個部分都可以省略。文法部分可以是一個字元串（簡單的token常常可以這樣處理），TOKEN中聲明的token，或一個對某個非終結符對應的函數的調用。

}

以上說明的是jj檔案的組成部分，下面再說明一下jj檔案中文法的表示方法。Javacc中的文法表示吸收了UNIX中正規文法的一些記号，下面是一些：

l         []：其中的内容是可選的。

l         +：前面的内容出現一次或多次。

l         -：前後構成的閉區間。

l         *: 前面的内容出現0次或多次。

l         ?：前面的内容出現0次或一次。

l         ~：後面的内容的補。

l         |：前面或後面。

l         ()：改變運算的優先級，把其中的内容作為一個整體。

很遺憾的是，javacc有一些問題，即它采用的是自頂向下的分析方法，而且沒有回溯功能，是以如何解決沖突的問題，是程式員的責任。Javacc産生的程式采用的分析方法既不是純正的遞歸下降算法（可以回溯），也不是純正的LL算法，事實上，它和二者既有聯系又有差別。

與遞歸下降算法相比，它們的共同點是都采用了函數來表示對應的非終結符，通過函數調用來表示非終結符之間的組成關系。二者之間的不同點在于javacc沒有回溯能力，也就是說，如何展開非終結符在編譯時就已經确定了。

與LL算法算法相比，它們的共同點是如何展開非終結符都是靜态确定的（javacc是函數調用，LL是展開表），事實上，采用預設選項的javacc的語言是LL(1)的語言。不同之處在于，前者采用的是函數調用，後者采用的是棧上展開的方法。

因為javacc的基礎是自頂向下的分析方法，是以必須要解決的下面的兩個問題：左遞歸和公因子。關于左遞歸的問題，一般采用經典的修改文法的方法解決。關于公因子的問題，可以改寫算法（提取公因子），也可以通過展望（look ahead）更多符号的方法來解決。但是因為javacc擴充了經典的BNF，是以它面臨更多的問題。總之，當在編譯時碰到沖突問題時，就說到了一個choice point。

可以将javacc中choice point歸結為以下幾類：

l         由選擇算子|引入的沖突，

l         由可省略算子[]或？引入的沖突

l         由重複算子*引入的沖突

l         由重複算子+引入的沖突

當在javacc中碰到沖突時，可以采用下面的方法之一解決問題：

l         修改文法，使之成為LL(1)文法。這個方法有一個問題：修改後的文法可能非常不直覺了L

l         在jj檔案中給javacc一些提示。這些提示可以根據展望的作用域分成全局提示和部分提示。要采用全局提示，隻要将LOOKAHEAD=k寫到Options塊中即可（當然也可以寫到javacc的指令行裡），這樣javacc産生的分析器就可以分析LL(K)文法生成的語言。也可以設定一個局部的LOOKAHEAD，這樣既保持了LL(1)的高效性，又可以解決choice point中的。LOOKAHEAD的局部聲明形式是LOOKAHEAD(…)，其中括号中的可以是數字（說明向後看多少個記号），或者是一個表示文法的串（當成功時選擇）。LOOKAHEAD的完整形式為LOOKAHEAD(amount, expansion, {java語言裡的邏輯表達式})，它的含義是，如果到達amount個記号後，expansion如果仍然成立，且邏輯表達式也成立，則執行下面的展開。

采用第一種方法的好處是效率非常高，對機器友好，易于維護，采用第二種方法的好處是文法更加直覺，但是卻不易維護。有時候采用第一種方法是無法解決沖突的，第二種方法是唯一的選擇。