为什么 ANTLR "over-reduce" 这个表达式没有？

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 压入堆栈，作为 reduce 因子 [=31] 的先决条件=] 到 expr。

ANTLR 是否仅在 null 严格 "required" 时移动 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;
...

为什么 ANTLR "over-reduce" 这个表达式没有？

Why doesn't ANTLR "over-reduce" this expression?

parsing

antlr

lr

antlr4