Pourquoi ANTLR ne "sur-réduit" pas cette expression?

Question

J'ai la grammaire suivante:

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

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

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

I Alimentation 2 + 3, en utilisant expr comme la règle de départ. L'arborescence d'analyse résultante de ANTLR est correcte; Cependant, je pense que je ne comprends pas les méthodes de changement-réduction qu'il utilise.

Je me attends à ce qui suit pour se produire:

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) 

J'ai attendu une erreur de se produire à l'étape 3 wherin l'analyseur serait shift un null sur la pile comme condition préalable à reduce le facteur ing " jusqu'à "expr.

Est-ce que ANTLR ne décale que null quand c'est strictement "requis" parce que le résultat reduce satisfera la grammaire?

Answer 1

Il me semble que ANTLR n'utilise pas d'analyseur shift-reduce; les parseurs générés sont une descente récursive utilisant une quantité arbitraire de lookahead.

Les étapes de l'analyseur serait quelque chose comme:

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  | 

D'après ce que je lis sur ANTLR, vous pouvez obtenir le même résultat avec les modifications suivantes à la grammaire originale:

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