ANTLR regola priorità

Question

Innanzitutto so che questa grammatica non ha senso, ma è stato creato per testare la regola ANTLR comportamento di priorità

grammar test; 

options 
{ 

output=AST; 
backtrack=true; 
memoize=true; 

} 

rule_list_in_order : 
    (
    first_rule 
    | second_rule 
    | any_left_over_tokens)+ 
    ; 


first_rule 
    : 
    FIRST_TOKEN 
    ; 


second_rule:  
    FIRST_TOKEN NEW_LINE SECOND_TOKEN NEW_LINE; 


any_left_over_tokens 
    : 
    NEW_LINE 
    | FIRST_TOKEN 
    | SECOND_TOKEN; 



FIRST_TOKEN 
    : 'First token here' 
    ; 

SECOND_TOKEN 
    : 'Second token here'; 

NEW_LINE 
    : ('\r'?'\n') ; 

WS : (' '|'\t'|'\u000C') 
    {$channel=HIDDEN;} 
    ; 

Quando do questa grammatica l'ingresso 'primo token qui \ nSecond gettone qui ', corrisponde alla seconda_rula.

Mi sarei aspettato che corrispondesse alla prima regola di any_left_over_tokens perché la prima_rola compare prima della seconda_regola nella lista_ordine_ordine che è il punto iniziale. Qualcuno può spiegare perché questo accade?

Acclamazioni

Answer 1

Prima di tutto, lexer di ANTLR si tokenize l'input da cima a fondo. Quindi i token definiti per primi hanno una precedenza più alta di quelli sotto di esso. E nel caso in cui la regola abbia token sovrapposti, la regola che corrisponde al maggior numero di caratteri avrà la precedenza (corrispondenza avida).

Lo stesso principio vale per le regole del parser. Anche le regole definite per prime verranno confrontate per prime. Per esempio, in regola foo, sub-regola a verrà prima provato prima b:

foo 
    : a 
    | b 
    ; 

Si noti che nel tuo caso, la regola 2 ° non corrisponde, ma cerca di farlo, e fallisce perché non c'è un'interruzione di riga finale, producendo l'errore:

line 0:-1 mismatched input '<EOF>' expecting NEW_LINE 

Quindi, niente è stato abbinato. Ma che è dispari. Perché tu hai impostato il backtrack=true, dovrebbe almeno fare marcia indietro e partita:

1. first_rule("primo token qui")
2. any_left_over_tokens("linea-break")
3. any_left_over_tokens("Secondo token qui")

se non corrisponde allo first_rule in primo luogo e nemmeno provare a far corrispondere second_rule per cominciare.

Una demo rapida durante l'esecuzione manuale dei predicati (e disattivazione di backtrack nelle opzioni {...} sezione) sarà simile:

grammar T; 

options { 
    output=AST; 
    //backtrack=true; 
    memoize=true; 
} 

rule_list_in_order 
    : ((first_rule)=> first_rule {System.out.println("first_rule=[" + $first_rule.text + "]");} 
    | (second_rule)=> second_rule {System.out.println("second_rule=[" + $second_rule.text + "]");} 
    | any_left_over_tokens  {System.out.println("any_left_over_tokens=[" + $any_left_over_tokens.text + "]");} 
    )+ 
    ; 

first_rule 
    : FIRST_TOKEN 
    ; 

second_rule 
    : FIRST_TOKEN NEW_LINE SECOND_TOKEN NEW_LINE 
    ; 

any_left_over_tokens 
    : NEW_LINE 
    | FIRST_TOKEN 
    | SECOND_TOKEN 
    ; 

FIRST_TOKEN : 'First token here'; 
SECOND_TOKEN : 'Second token here'; 
NEW_LINE  : ('\r'?'\n'); 
WS   : (' '|'\t'|'\u000C') {$channel=HIDDEN;}; 

che possono essere testati con la classe:

import org.antlr.runtime.*; 

public class Main { 
    public static void main(String[] args) throws Exception { 
     String source = "First token here\nSecond token here"; 
     ANTLRStringStream in = new ANTLRStringStream(source); 
     TLexer lexer = new TLexer(in); 
     CommonTokenStream tokens = new CommonTokenStream(lexer); 
     TParser parser = new TParser(tokens); 
     parser.rule_list_in_order(); 
    } 
} 

che produce l'uscita prevista:

first_rule=[First token here] 
any_left_over_tokens=[ 
] 
any_left_over_tokens=[Second token here] 

Si noti che non importa se si utilizza:

rule_list_in_order 
    : ((first_rule)=> first_rule 
    | (second_rule)=> second_rule 
    | any_left_over_tokens 
    )+ 
    ; 

.210

o

rule_list_in_order 
    : ((second_rule)=> second_rule // <--+--- swapped 
    | (first_rule)=> first_rule // <-/ 
    | any_left_over_tokens 
    )+ 
    ; 

, sia produrrà i risultati attesi.

Quindi, la mia ipotesi è che potresti aver trovato un bug.

Yout potrebbe provare la mailing list ANTLR, nel caso in cui si desideri una risposta definitiva (Terence Parr frequenta lì più spesso di quanto faccia qui).

Buona fortuna!

PS. Ho provato questo con ANTLR v3.2