Взаимная левая рекурсия ANTLR 4

Question

Мне жаль задавать еще один вопрос о взаимной левой рекурсии, я чувствую, что мой характерен только для моей ситуации, или, по крайней мере, я не могу понять достаточно, чтобы связать его с грамматикой всех остальных. Я немного новичок в мире компьютерных технологий (я самоучка в java, который является моим целевым языком, а теперь и ANTLR4), поэтому, если возможно, опишите вещи в терминах непрофессионала, а не в терминах CS.

Я пишу программу, которая требует алгебры и символических производных, и, конечно, требует, чтобы вещи были проанализированы, и деревья оперировались, но я даже не буду беспокоиться об этом, потому что я думал, что ANTLR4 поддерживает прямую левую рекурсию, но по-видимому, это не так. На выходе он говорит мне, что мой метод [выражение] является взаимно рекурсивным и, по-видимому, это не разрешено...? МОИ ВОПРОСЫ:

1) Может ли кто-нибудь объяснить левую рекурсию / разницу между взаимной и прямой левой рекурсией, если она есть?

2) Объясните, что в моей грамматике вызывает это рекурсивное раздражение, и как это исправить? И я не уверен, если это по теме:

3) Люди говорят что-то об альтернативах и маркируют альтернативы (я думаю, что они имеют в виду обозначение #label). Для чего это?

grammar MathProcessor;
@header {package utils;}
END: ';';
EQUALS: '=';
SIN: 'sin(';
COS: 'cos(';
TAN: 'tan(';
SEC: 'sec(';
CSC: 'csc(';
COT: 'cot(';
LN: 'ln(';
EPOW: 'pow(';
RPAREN: '(';
LPAREN: ')';
EXP: '^';
MULT: '*';
DIV: '/';
ADD: '+';
SUBT: '-';
VAR: ('a'..'z'|'A'..'Z');
INT: ('0'..'9')+;
mathobj: ((equation|expression) END) EOF;
equation: (expression '=' expression);

expression: 
((RPAREN|SIN|COS|TAN|SEC|CSC|COT|LN|EPOW) expression (RPAREN)) #parenOps
| (expression EXP expression) #exponent
| (expression (MULT|DIV) expression) #multiplyDivide 
| (expression (ADD|SUBT) expression) #addSubtract
| (VAR|INT) #varInt
;

Answer 1

Ваша грамматика фактически будет работать с ANTLR 4, если вы просто удалите несколько случаев ненужных скобок в вашей грамматике. Алгоритм исключения левой рекурсии работает только с прямой левой рекурсией, что показано в следующем примере:

a
  : B
  | a B  // the reference to 'a' here is direct left recursion
  ;

Основной другой тип рекурсии - косвенная левая рекурсия, которая обычно демонстрируется с использованием двух отдельных правил.

a
  : B
  | c
  ;

c
  : a B // the reference back to 'a' is indirect left recursion
  ;

В случае вашей грамматики ANTLR лечит (...) как анонимное подправило, поэтому код, подобный следующему, определяется как косвенная левая рекурсия. Если вы удалите скобки из примера, он будет вести себя как в первом случае.

a
  : B
  | (a B)
  ;

Чтобы ответить на ваш последний вопрос, #label синтаксис изменяет сгенерированный класс дерева разбора для этой альтернативы. Например, вместо генерации простого ExpressionContext объект, выражение 3 будет генерировать VarIntContext, Это позволяет вам различать разные альтернативы в правиле автоматически генерируемых слушателей и посетителей.