爲什麼ANTLR不會「過度減少」這個表達式？

Question

我有以下語法：

expr : factor op ; 
op 
    : '+' factor op 
    | // Blank rule for left-recursion elimination 
    ; 

factor 
    : NUM 
    | '(' expr ')' 
    ; 

NUM : ('0'..'9')+ ; 

我公司供應2 + 3，使用expr的開始規則。 ANTLR產生的分析樹是正確的;不過，我認爲我誤解了它使用的轉換縮減方法。

我希望下面的情況發生：

Step # | Parse Stack | Lookahead | Unscanned | Action 
1  |    | NUM  | + 3  | Shift 
2  | NUM   | +   | 3   | Reduce by factor -> NUM 
3  | factor  | +   | 3   | Shift a 'null'? 
4  | factor null | +   | 3   | Reduce by op -> null 
5  | factor op  | +   | 3   | Reduce by expr -> factor op 
6  | expr   | +   | 3   | Shift 
7  | expr +  | NUM  |   | Shift 
8  | expr + NUM |   |   | Reduce by factor -> NUM 
9  | expr + factor |   |   | ERROR (no production) 

我會一直期待一個錯誤在第3步中出現wherin解析器將shift一個null到堆棧的前提reduce荷蘭國際集團的因素「 up「爲expr。

當ANTLR嚴格「要求」時，ANTLR是否只轉換null，因爲生成的reduce將滿足語法？

Answer 1

在我看來，ANTLR不使用shift-reduce分析器;生成的解析器使用任意數量的lookahead進行遞歸下降。

解析器的步驟是這樣的：

Rule   | Consummed | Input 
--------------+-----------+------ 
expr   |   | 2 + 3 
..factor  |   | 2 + 3 
....NUM  | 2   | + 3 
..op   | 2   | + 3 
....'+'  | 2 +  | 3 
....factor | 2 +  | 3 
......NUM  | 2 + 3  | 
....op  | 2 + 3  | 
......(empty) | 2 + 3  | 

從我瞭解ANTLR，你可以有以下改動原來的語法達到同樣的效果：

expr: factor op*; 
op: '+' factor; 
...