ANTLR4 für beide Seiten linksrekursive Fehler beim

Question

Parsen Ich habe diese ANTLR 4 Grammatik:

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

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

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

ich die folgende Fehlermeldung erhalten:

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

Ich habe versucht, so viele Möglichkeiten, aber kann es nicht reparieren. Was ist das Problem und wie kann ich es lösen?

Answer 1

Antlr ist ein LL (*) Parser, der in vielerlei Hinsicht "besser" ist als ein LL(k) parser, aber immer noch viele seiner Nachteile hat. Eine davon ist die Tatsache, dass sie nicht mit der Linksrekursion umgehen kann (tatsächlich kann die Version 4 mit der Linksrekursion innerhalb derselben Regel umgehen). Was der Fehler sagt, ist, dass Sie eine Linksrekursion einer Grammatik haben, ein Fluch für die LL-Parser.

Dies wird durch diese Konstruktion in der Grammatik verursacht:

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

Da die * Betreiber bedeutet 0 oder mehr, ich habe es mit 0 instanziieren kann, so dass der Parser dies tun: „constantFixedExpression versuchen, es so muss term versuchen, also muss es factor versuchen, also muss es versuchen constantFixedEXpression, also es [...] "und Sie haben sich eine Endlosschleife.

---

Glücklicherweise haben kontextfreie formale Grammatiken eine äquivalente Transformation zum Entfernen von Links-Rekursion! Es kann allgemein ausgedrückt werden durch:

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

Oder in Antlr Notation:

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

Weitere Informationen zu diesem Prozess finden Sie in Automaten zu finden/Grammatiken Bücher oder in der Wikipedia.

---

Ich werde verlassen Korrektur Ihrer Grammatik mit der Refactoration zu linken Rekursion als Ihre Arbeit zu entfernen. Ich möchte jedoch einen anderen Punkt erwähnen: Antlr 4 kann eine Linksrekursion machen! Wie ich bereits erwähnt habe, kann die Version 4 mit der Linksrekursion innerhalb derselben Regel umgehen. Wie Sie in Antlr4 tun, gibt es Möglichkeiten, die Vorrangstellung und Assoziativität von Operatoren anders als direkt beim Parsen anzugeben. Mal sehen, wie es funktioniert:

Dies ist ein Beispiel für eine grundlegende Rechner Grammatik. Die obersten Operatoren haben die höchste Priorität, und die unteren haben die niedrigere Priorität. Dies bedeutet, dass 2+2*3 als 2+(2*3) anstelle von (2+2)*3 geparst wird. Die <assoc=right> Konstruktion bedeutet, dass der Operator rechtsassoziativ ist, so dass 1^2^3 als 1^(2^3) anstelle von (1^2)^3 geparst wird.

Wie Sie sehen können, ist es viel einfacher, Operatoren mit Linksrekursion zu spezifizieren, so dass Antlr 4 in diesen Momenten eine große Hilfe ist! Ich empfehle Ihnen, Ihre Grammatik neu zu schreiben, um diese Funktion zu nutzen.