ANTLR4 wzajemnie lewej rekurencyjne błąd podczas parsowania

Question

mam ten antlr 4 Gramatyka:

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

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

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

pojawia się następujący błąd:

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

Próbowałem tak wiele sposobów, ale nie może naprawić. Jaki jest problem i jak mogę go rozwiązać?

Answer 1

Antlr jest parserem LL (*), który pod wieloma względami jest "lepszy" niż LL(k) parser, ale wciąż ma wiele jego wad. Jednym z nich jest fakt, że nie radzi sobie z rekursją lewą (w rzeczywistości wersja 4 może zajmować się rekursją lewą w ramach tej samej reguły). Błąd mówi, że masz lewą rekursję gramatyki, zmora dla parserów LL.

Jest to spowodowane tym budowy w swojej gramatyki:

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

Ponieważ operator * oznacza 0 lub więcej, mogę instancję 0, więc parser będzie to zrobić: „spróbuj constantFixedExpression, więc musi spróbować term, więc musi spróbować factor, więc musi spróbować constantFixedEXpression, więc [...] "i masz sobie nieskończoną pętlę.

---

Na szczęście gramatyki formalne bezkontekstowe mają równoważną transformację do usuwania lewej rekursji! To może być wyrażona rodzajowo przez:

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

Albo w notacji antlr:

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

Więcej informacji na temat tego procesu można znaleźć w automat/gramatyk książek lub w Wikipedia.

---

Zostawię korektę twojej gramatyki z refaktoryzacją, aby usunąć lewą rekursję jako twoją pracę. Jednak chcę dotknąć w innym punkcie: Antlr 4 może wykonać lewą rekursję! Jak już wspomniałem, wersja 4 może zajmować się lewą rekurencją w ramach tej samej reguły. Istnieją sposoby wskazywania pierwszeństwa i asocjatywności operatorów innych niż bezpośrednio w analizie, tak jak to robisz, w Antlr4. Zobaczmy, jak to działa:

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

To jest przykład gramatyki podstawowego kalkulatora. Operatory na górze to te o najwyższym priorytecie, a te na dole mają niższy priorytet. Oznacza to, że 2+2*3 będzie przetwarzany jako 2+(2*3) zamiast (2+2)*3. Konstrukcja <assoc=right> oznacza, że ​​operator jest skojarzony prawostronnie, więc będzie przetwarzany jako 1^(2^3), a nie .

Jak widać, znacznie łatwiej jest określić operatorów z lewą rekurencją, więc Antlr 4 jest bardzo pomocny w tych chwilach! Zalecam ponowne napisanie gramatyki, aby móc korzystać z tej funkcji.