ANTLR4 взаимно леворекурсивная ошибка при разборе

У меня есть эта грамматика ANTLR 4:

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

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

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

Я получаю следующую ошибку:

error (119): LanguageA.g4: Следующие наборы правил являются взаимно леворекурсивными [constantFixedExpresion, factor, term]

Я пробовал так много способов, но не могу это исправить. В чем проблема и как я могу ее решить?

Ответы

Ответ 1

Antlr - это анализатор LL (*), который во многих отношениях "лучше", чем анализатор LL (k), но все же имеет много недостатков. Одним из них является тот факт, что он не может иметь дело с левой рекурсией (фактически, версия 4 может иметь дело с левой рекурсией в рамках того же правила). Ошибка говорит о том, что у вас есть левая рекурсия грамматики, проклятие для парсеров LL.

Это вызвано этой конструкцией в вашей грамматике:

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

Так как оператор * означает 0 или более, я могу создать его экземпляр с 0, поэтому синтаксический анализатор сделает это: "try constantFixedExpression, поэтому ему нужно попробовать term, поэтому ему нужно попробовать factor, поэтому ему нужно попробовать constantFixedEXpression, поэтому [...] "и у вас есть бесконечный цикл.

К счастью, у контекстно-свободных формальных грамматик есть эквивалентное преобразование для удаления левой рекурсии! Это может быть выражено в общем:

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

Или в нотации Antlr:

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

Более подробную информацию об этом процессе можно найти в книгах по автоматике/грамматике или в Википедии.

Я оставлю исправление вашей грамматики с помощью рефакторации, чтобы убрать левую рекурсию как вашу работу. Однако я хочу затронуть еще один момент: Antlr 4 может выполнять левую рекурсию! Как я уже говорил, версия 4 может иметь дело с левой рекурсией в рамках того же правила. Есть способы указать приоритет и ассоциативность операторов, отличных от непосредственного анализа, как вы делаете в Antlr4. Давайте посмотрим, как это работает:

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

Это пример базовой грамматики калькулятора. Операторы вверху - это операторы с наивысшим приоритетом, а операторы внизу - с более низким приоритетом. Это означает, что 2+2*3 будет анализироваться как 2+(2*3) а не (2+2)*3. Конструкция <assoc=right> означает оператор в правой ассоциативности, поэтому 1^2^3 будет проанализирован как 1^(2^3) а не (1^2)^3.

Как вы можете видеть, гораздо проще указывать операторы с левой рекурсией, поэтому Antlr 4 очень помогает в эти моменты! Я рекомендую переписать вашу грамматику, чтобы использовать эту функцию.