regole ANTLR AST fallire con RewriteEmptyStreamException

Question

Ho una semplice grammatica:

grammar sample; 
options { output = AST; } 
assignment 
    : IDENT ':=' expr ';' 
    ; 
expr  
    : factor ('*' factor)* 
    ; 
factor 
    : primary ('+' primary)* 
    ; 
primary 
    : NUM 
    | '(' expr ')' 
    ; 
IDENT : ('a'..'z')+ ; 
NUM : ('0'..'9')+ ; 
WS : (' '|'\n'|'\t'|'\r')+ {$channel=HIDDEN;} ; 

Ora voglio aggiungere alcune regole di riscrittura per generare un AST. Da quello che ho letto on-line e nel libro modelli di linguaggio, dovrei essere in grado di modificare la grammatica in questo modo:

assignment 
    : IDENT ':=' expr ';' -> ^(':=' IDENT expr) 
    ; 
expr  
    : factor ('*' factor)* -> ^('*' factor+) 
    ; 
factor 
    : primary ('+' primary)* -> ^('+' primary+) 
    ; 
primary 
    : NUM 
    | '(' expr ')' -> ^(expr) 
    ; 

Ma non funziona. Sebbene compili bene, quando eseguo il parser ottengo un errore RewriteEmptyStreamException. Ecco dove le cose si fanno strane.

Se definisco i token Pseudo ADD e MULT e li utilizzo al posto dei letterali del nodo dell'albero, funziona senza errori.

tokens { ADD; MULT; } 

expr  
    : factor ('*' factor)* -> ^(MULT factor+) 
    ; 
factor 
    : primary ('+' primary)* -> ^(ADD primary+) 
    ; 

In alternativa, se uso la notazione suffisso nodo, sembra anche funzionare bene:

expr  
    : factor ('*'^ factor)* 
    ; 
factor 
    : primary ('+'^ primary)* 
    ; 

È questa discrepanza nel comportamento un bug?

Answer 1

No, non un bug, AFAIK. Prendete la vostra regola expr ad esempio:

expr  
    : factor ('*' factor)* -> ^('*' factor+) 
    ; 

dal momento che il * potrebbero non essere presenti, dovrebbe anche non essere in regola di riscrittura AST. Quindi, quanto sopra è errato e ANTLR lamentarsi di questo è corretto.

Ora, se si inserisce un gettone immaginario come MULT invece:

expr  
    : factor ('*' factor)* -> ^(MULT factor+) 
    ; 

tutto va bene in quanto la regola sarà sempre produrre una o più factor s'.

Ciò che probabilmente si intende fare è qualcosa di simile:

expr  
    : (factor -> factor) ('*' f=factor -> ^('*' $expr $f))* 
    ; 

vedere anche Capitolo 7: Albero Edilizia da The Definitive ANTLR Reference. In particolare i paragrafi Regole di riscrittura nelle sottoregole (pagina 173) e Riferimento alle regole AST precedenti nelle regole di riscrittura (pagina 174/175).

Answer 2

Se si desidera generare un albero n-ario per l'operatore '*' con tutti i bambini allo stesso livello si può fare questo:

expr 
    : (s=factor -> factor) (('*' factor)+ -> ^('*' $s factor+))? 
    ; 

Ecco alcuni esempi di ciò che questo tornerà:

Tokens: AST 
factor: factor 
factor '*' factor: ^('*' factor factor) 
factor '*' factor '*' factor: ^('*' factor factor factor) 

terzo esempio di Bart sopra produrrà un albero annidata, poiché il risultato di $ expr per ogni iterazione successiva è un nodo con due figli, in questo modo:

factor * factor * factor: ^('*' factor ^('*' factor factor)) 

che probabilmente non è necessario poiché la moltiplicazione è commutativa.