Obtenir la construction d'arbre avec ANTLR

Question

Comme demandé et répondu à Removing Left Recursion in ANTLR, je pouvais retirer la récursivité gauche

 
E -> E + T|T 
T -> T * F|F 
F -> INT | (E) 

Après gauche retrait de récursivité, je suis la suivante

 
E -> TE' 
E' -> null | + TE' 
T -> FT' 
T' -> null | * FT' 

Alors, comment faire la construction de l'arbre avec la grammaire modifiée? Avec l'entrée 1 + 2, je veux avoir un arbre

^('+' ^(INT 1) ^(INT 2))

. Ou similaire.

 
grammar T; 

options { 
    output=AST; 
    language=Python; 
    ASTLabelType=CommonTree; 
} 

start : e -> e 
    ; 
e : t ep -> ??? 
    ; 
ep : 
    | '+' t ep -> ??? 
    ; 
t : f tp -> ??? 
    ; 
tp : 
    | '*' f tp -> ??? 
    ; 
f : INT 
    | '(' e ')' -> e 
    ; 

INT : '0'..'9'+ ; 
WS: (' '|'\n'|'\r')+ {$channel=HIDDEN;} ; 

Answer 1

Un peu d'avis: bien qu'il est parfois possible de passer d'une grammaire LR à une grammaire LL, comme vous l'avez fait, le résultat est pas aussi idiomatiques et peut sembler une étrange façon de définir votre grammaire à quelqu'un de familier avec les grammaires LL.

Par exemple, considérons l'extrait suivant du dessus:

tp : 
    | '*' f tp -> ??? 

L'accepte au-dessus d'un * suivi d'un f dont la première série contiendra INT ou (, le début de lui-même comme son droit récursive. Ainsi, vous ne verrez jamais le début de l'expression que vous voulez enraciner à *, ce qui rendra beaucoup plus difficile que nécessaire la construction de l'arbre que vous voulez. Pour faciliter la création de cet AST dans ANTLR, vous voulez avoir à la fois les opérandes et l'opérateur.

add: 
    INT '+'^ INT; 

Le caret, ^ fait la + la racine de l'arbre et les deux INT s deviennent ses enfants.

L'exemple Bart K linked to est un grand exemple de la façon dont je pense que cela se fasse avec une grammaire LL ... et échelles pour soutenir les opérateurs de priorités différentes.