为什么ANTLR不“过度减少”这个表达？

Question

我有以下语法：

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

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

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

我提供2 + 3，使用expr作为开始规则。来自ANTLR的解析树是正确的；但是，我认为我误解了它使用的shift-reduce方法。

我预计会发生以下情况：

 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中会出现一个错误，在这个步骤中，解析器将shift一个null放到堆栈上，作为将因子“向上”放到expr的先决条件。

ANTLR是否只在严格“需要”时才移动null，因为最终的reduce将满足语法要求？

Answer 1

在我看来，ANTLR不使用shift-reduce解析器；生成的解析器是递归下降的，使用任意数量的前瞻性。

解析器的步骤如下所示：

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;
...