ANTLR4 erreur récursive mutuelle gauche lors de l’parsing

J’ai cette grammaire ANTLR 4:

constantFixedExpresion : term (('+'|'-') term)+; term : factor (('*'|'//'|'REM')factor)+; factor : ('+'|'-')* ( wholeNumberConstant | constantFixedExpresion | 'TOFIXED' (ssortingngConstant | bitCodeConstant) | identifier) ('FIT'constantFixedExpresion)*;

Je reçois l’erreur suivante:

error (119): LanguageA.g4 ::: Les ensembles de règles suivants sont mutuellement gauches-récursifs [constantFixedExpresion, factor, term]

J’ai essayé de nombreuses façons mais je ne peux pas le réparer. Quel est le problème et comment puis-je le résoudre?

Antlr est un parsingur syntaxique LL (*), qui est à bien des égards “meilleur” qu’un parsingur syntaxique LL (k) , mais qui présente encore de nombreux inconvénients. L’un d’entre eux est le fait qu’il ne peut pas gérer la récursivité à gauche (en fait, la version 4 peut traiter de la récursivité à gauche dans la même règle). Ce que l’erreur dit, c’est que vous avez une récursion à gauche d’une grammaire, un fléau pour les parsingurs syntaxiques LL.

Ceci est causé par cette construction dans votre grammaire:

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

Puisque l’opérateur * signifie 0 ou plus, je peux l’instancier avec 0. L’parsingur syntaxique procédera ainsi: “try constantFixedExpression , il doit donc essayer term , il doit donc essayer factor , il doit donc essayer constantFixedEXpression , donc […] “et vous avez une boucle infinie.

Heureusement, les grammaires formelles sans contexte ont une transformation équivalente pour supprimer la récursion gauche! Il peut être exprimé de manière générique par:

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

Ou en notation Antlr:

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

Vous trouverez plus d’informations sur ce processus dans les livres automates / grammaires ou dans Wikipedia .

Je vais laisser corriger votre grammaire avec la refactoration pour supprimer la récursion gauche comme votre travail. Cependant, je veux aborder un autre point: Antlr 4 peut faire une récursion à gauche! Comme je l’ai mentionné, la version 4 peut traiter de la récursion gauche dans la même règle . Il existe des moyens d’indiquer la priorité et l’associativité des opérateurs autres que directement dans l’parsing syntaxique, comme vous le faites dans Antlr4. Voyons voir comment ça fonctionne:

 expr: NUMBER | expr '^' expr | expr '*' expr | expr '/' expr | expr '+' expr | expr '-' expr;

Ceci est un exemple de grammaire de base d’une calculasortingce. Les opérateurs situés en haut sont ceux qui ont la priorité la plus élevée et ceux qui se trouvent en bas ont la priorité la plus basse. Cela signifie que 2+2*3 seront analysés comme 2+(2*3) plutôt que (2+2)*3 . La construction signifie que l’opérateur est en droit-associatif, ainsi 1^2^3 sera analysé comme 1^(2^3) plutôt que (1^2)^3 .

Comme vous pouvez le constater, il est beaucoup plus facile de spécifier des opérateurs avec une récursion à gauche. Antlr 4 est donc d’une grande aide dans ces moments! Je recommande de réécrire votre grammaire pour utiliser cette fonctionnalité.