Почему ANTLR «чрезмерно уменьшает» это выражение?

Question

У меня есть следующая грамматика:

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

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

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

I поставку 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 анализатор будет shiftnull в стек в качестве предварительного условия для reduce ИНГ фактор " вверх "до expr.

Имеет ли ANTLR только сдвиг null, когда он строго «требуется», потому что полученный reduce будет удовлетворять грамматике?

Answer 1

Мне кажется, что ANTLR не использует парсер с уменьшением сдвига; сгенерированные парсеры являются рекурсивным спусками, используя произвольное количество запросов.

Этапы синтаксического анализа будет что-то вроде:

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