javacc-LOOKAHEAD MiniTutorial 翻譯1、LOOKAHEAD是什麼2、javacc裡面的選擇點3、預設的選擇點算法4、選擇點沖突解決算法5、設定全局LOOKAHEAD6、設定局部LOOKAHEAD 7、文法上的LOOKAHEAD8、語義上的LOOKAHEAD9、LOOKAHEAD結構總結

       本文翻譯自\javacc-5.0\doc\lookahead.html章節。

上文：

         lookahead就是當文法分析器從詞法分析器裡取token時，需要取多少個才能讓分析器正确的走下去。

例一

在這個文法中，隻能比對“abc”和“abcc”。

  假設我們現在把“abc”當成輸入字元，來看javacc是如何工作的。

1、第一個字元是‘a’，這裡沒什麼疑問，比對“a”

2、讀取下一個字元‘b’，毫無疑問進入BC(),剛好比對‘b’

3、讀取下一個自稱‘c’，在這一步，我們看到了一個選擇點，即是比對[‘c‘]呢，還是跳出BC()，比對最後一個‘c’。這裡假定我們選擇了[...],那麼繼續往下走。

4、因為現在我們已經跳出了BC(),但是Input說現在還需要一個‘c’，但我們已經沒有字元了，是以宣告失敗。

5、在遇到這種問題時，就說明我們在前面的選擇點的地方可能選擇了一個錯誤的決定，是以需要回溯到[...]

6、這個時候我們就應該選擇Input裡面的‘c’，這時候才能正确執行。

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

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

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

 3. 由重複算子 * 引入的沖突

 4. 由重複算子 + 引入的沖突

看文法：

 if (next token is "(") {

   choose Choice 2

 } else if (next token is "new") {

   choose Choice 3

 } else if (next token is <ID>) {

   choose Choice 1

 } else {

   produce an error message

 }

上面文法是沒有什麼沖突的，假如改成如下文法：

就會報如下沖突資訊：

意思就是說在預設的選擇算法在這種情況下不能正确執行，因為1和4都是以ID開頭的，這就是我們上面說的左因子。

 1.修改文法，使之成為LL(1)文法。

 2.隻要将LOOKAHEAD=k寫到Options塊中即可,javacc産生的分析器就可以分析LL(K)文法生成的語言

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

全局的lookahead是在jj檔案中的options中指定的，可以指定為非負整數，javacc自動生成LL(K)算法。這種方法是不提倡的，因為這會在每個選擇點都進行LL(K)算法，即多向前看k個token，但大部分選擇點都是一個（預設）就可以了。

假定這時把lookahead設定成2，那麼在上面的3中的第二個文法就會變成:

        當下來的兩個token是<ID> 和"("時，那麼選擇點1，

        如果下來的兩個token是<ID> and "."時，那麼就選擇點4。

這樣就能讓上面的文法正常執行。

可以通過設定局部的lookahea方法，使文法分析器隻在需要的時候向前看K個字元，别的情況下隻用看一個就可以了，這種情況下，效率自然比通過全局設定好。

可以把上面文法改下：

通過以上設定，隻使第一個選擇點使用LOOKAHEAD(2)。這種情況下工作邏輯如下：

這裡假定ClassDeclaration定義為在class的前面可以出現無數多次的public，final，而InterfaceDeclaration的定義也是前面可以出現出現無數多次的public，final。那麼問題就出現了，因為當分析器在工作時，并不知道到底有多少個public或者fianl，也就不知道到底需要向前看多不個token，才能确定到底是選擇ClassDeclaration還是InterfaceDeclaration。

顯然簡單的方法就是向前看無數多個，如下：

但這樣顯示是不合理的，合理的做法應該是下面的方法：

意思就是說，還是一直向前看，如果ClassDeclaration()能夠比對成功，則就用ClassDeclaration()，否則的話進入InterfaceDeclaration()。即：

當然還有一種優化的方法，見下：

工作過程就是：

即如果下面的一些列token比對( "abstract" | "final" | "public" )* "class"，那麼就選擇ClassDeclaration()，否則選擇InterfaceDeclaration()。

當然還有一種更加優化的方法，見下：

在這種情況下，具體的工作過程就是，這時lookahead最多向前看10個token，如果超過10token後，還比對( "abstract" | "final" | "public" )* "class"的話，那麼就進入選擇點ClassDeclaration()。

其實當不設定10的時候，預設的值就是最大值，即2147483647。

為了解決上面說到的回溯問題，我們可以使用如下的文法：

意思就是：

首先把‘c’封裝成一個label C，便于我們在lookahead裡面引用它，即如果下來的第一個token是C和第二個不是C，那麼選擇[..],否則跳出BC。

其實上面的改寫還可以使用下面的形式：

即同時使用文法和語義上的lookahead。第一個c為文法上的lookahead，第二個為語義上面的lookahead。

通用的格式為：

amount：即設定向前看的token個數；

expansion：即指定的文法上的lookahead，

boolean_expression：即指定的語義上的lookahead。

格式中的3個部分，至少指定一個部分，如果同時出現多個部分，則使用逗号分隔。