ANTLR4 errore reciprocamente sinistra-ricorsivo quando analizza

Question

ho questo ANTLR 4 grammatica:

constantFixedExpresion : term (('+'|'-') term)+; 

term : factor (('*'|'//'|'REM')factor)+; 

factor : ('+'|'-')* 
      (wholeNumberConstant 
      | constantFixedExpresion 
      | 'TOFIXED' (stringConstant | bitCodeConstant)  
      | identifier) 
     ('FIT'constantFixedExpresion)*; 

ottengo il seguente errore:

error(119): LanguageA.g4::: The following sets of rules are mutually left-recursive [constantFixedExpresion, factor, term]

ho provato tanti modi, ma non può risolvere il problema. Qual è il problema e come posso risolverlo?

Answer 1

Antlr è un parser LL (*), che è in molti modi "migliore" di uno LL(k) parser, ma ha ancora molti dei suoi disavaggi. Uno di questi è il fatto che non può gestire la ricorsione a sinistra (infatti, la versione 4 può occuparsi della ricorsione a sinistra all'interno della stessa regola). Quello che l'errore sta dicendo è che hai una ricorsione a sinistra di una grammatica, una rovina per i parser LL.

questo è causato da questa costruzione nella tua grammatica:

constantFixedExpression: term ...; 
term: factor ...; 
factor: ('+' | '-')* (constantFixedExpression | ...) ...; 

Dal momento che l'operatore * significa 0 o più, posso istanziare con 0, quindi il parser farà questo: "provare constantFixedExpression, quindi ha bisogno di provare term, quindi ha bisogno di provare factor, quindi ha bisogno di provare constantFixedEXpression, quindi [...] "e hai te stesso un ciclo infinito.

---

Fortunatamente, le grammatiche formali contestuali hanno una trasformazione equivalente per rimuovere la ricorsione a sinistra! Può essere espressa genericamente con:

A -> Aa | b 
-- becomes -- 
A -> bR 
R -> aA | ε 

O in Antlr notazione:

A: Aa | b; 
// becomes 
A: bR; 
R: (aA)?; 

Maggiori informazioni su questo processo può essere trovato in automa/grammatiche libri o nel Wikipedia.

---

Lascerò correggere la grammatica con il refactoring per rimuovere la ricorsione a sinistra come lavoro. Tuttavia, voglio toccare un altro punto: Antlr 4 può fare la ricorsione a sinistra! Come ho già detto, la versione 4 può gestire la ricorsione a sinistra all'interno della stessa regola. Ci sono modi per indicare la precedenza e l'associatività degli operatori oltre che direttamente nell'analisi, come si fa, in Antlr4. Vediamo come funziona:

expr: NUMBER 
     |<assoc=right> expr '^' expr 
     | expr '*' expr 
     | expr '/' expr 
     | expr '+' expr 
     | expr '-' expr; 

Questo è un esempio di grammatica di base della calcolatrice. Gli operatori in alto sono quelli con la precedenza più alta e quelli in basso hanno precedenza più bassa. Ciò significa che 2+2*3 verrà analizzato come 2+(2*3) anziché (2+2)*3. La costruzione <assoc=right> indica l'operatore in associazione destra, pertanto 1^2^3 verrà analizzato come 1^(2^3) anziché (1^2)^3.

Come potete vedere, è molto più semplice specificare gli operatori con ricorsione a sinistra, quindi Antlr 4 è di grande aiuto in questi momenti! Raccomando di riscrivere la tua grammatica per utilizzare questa funzione.