为什么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; 
...