ANTLR4 взаимная левая рекурсивная грамматика

Question

Я прочитал много вопросов здесь, в StackOverflow о проблемах с левой левой рекурсией в парсерах LL (k). Я нашел общий алгоритм для удаления левой рекурсии:

A : Aa | b ; 

становится

A : bR ; 
R : (aA)? ; 

Однако, я не могу понять, как применить его к моей ситуации. У меня есть

left_exp: IDENT | exp DOT IDENT ; 
exp  : handful 
     | of 
     | other rules 
     | left_exp ; 

«несколько других правил» содержит регулярные рекурсию, такие как exp : exp PLUS exp и т.д., и нет никаких проблем. Проблема заключается в том, что left_exp и exp являются взаимно рекурсивными.

Я думал о том, просто добавив IDENT и exp DOT IDENT к exp правилам, но бывают ситуации, когда другие действующие exp правила не применяются, где left_exp будет действительным.

EDIT

У меня есть следующее правило, которое вызывает для левого выражения с последующим назначением.

assign_statement: left_exp (COLON IDENT)? EQUAL exp SEMI ; 

Поскольку регулярное выражение только левое выражение, если оно сопровождается DOT IDENT, кажется, что я не могу просто добавить

| IDENT 
| exp DOT IDENT 

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

Answer 1

подхода я применяю обычно выглядит следующим образом:

A: Aa | b; 

становится:

A: b (a)*; 

Или вообще: все альты без левой рекурсии следует все альты с (удалено) левой рекурсией с неограниченное количество (выражается через оператор kleene). Пример:

A: Aa | Ab | c | d | Ae; 

становится:

А: (C |) (а | Ь | е) *;

Вы можете проверить это легко заменить непрерывно A:

A: Aa | b; 
A: (Aa | b)a | b; 
A: Aaa | ba | b; 
A: (Aa | b)aa | ba | b; 
A: Aaaa | baa | ba | b; 

т.д.

В вашем примере, однако у вас есть опосредованная левая рекурсия (через 2 правил). ANTLR не принимается. Решением является перемещение альтов от left_exp к правилу exp, а затем применить описанный выше алгоритм.