Warum "überreduziert" ANTLR diesen Ausdruck nicht?

Question

Ich habe die folgende Grammatik:

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

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

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

Ich liefere 2 + 3, expr als Startregel. Der resultierende Parse-Baum von ANTLR ist korrekt; Ich glaube jedoch, dass ich die von ihm verwendeten Shift-Reduce-Methoden falsch verstehe.

Ich würde erwarten, dass die folgenden geschehen:

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) 

Ich würde einen Fehler zu erwarten habe in Schritt 3 auftreten wherin der Parser shift ein null auf den Stapel als Voraussetzung für reduce den Faktor ing "würde up "zu einem expr.

Verschiebt ANTLR nur eine null, wenn es streng "erforderlich" ist, weil die resultierende reduce die Grammatik erfüllen wird?

Answer 1

Es scheint mir, dass ANTLR keinen Shift-Reduce-Parser verwendet; die erzeugten Parser sind rekursive Abstiegsvorgänge unter Verwendung einer willkürlichen Menge von Lookahead.

Die Schritte des Parsers wäre so etwas wie sein:

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  | 

Von dem, was ich über ANTLR lesen Sie das gleiche Ergebnis mit den folgenden Änderungen an der ursprünglichen Grammatik erreichen könnte:

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