ANTLR4 互左递归文法

Question

我在 Whosebug 上阅读了很多关于 LL(k) 解析器中的相互左递归问题的问题。我找到了删除左递归的通用算法：

A : Aa | b ;

变成

A : bR ;
R : (aA)? ;

但是，我不知道如何将它应用到我的情况中。我有

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

"handful of other rules"都包含正则递归，如exp : exp PLUS exp等，没有问题。问题在于 left_exp 和 exp 是相互递归的。

我考虑过将 IDENT 和 exp DOT IDENT 添加到 exp 规则中，但在某些情况下其他有效的 exp 规则不适用，其中left_exp 有效。

编辑

我还有以下规则，它要求左表达式后跟赋值。

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;

变成：

A: (c | d) (a | b | e)*;

您可以通过不断替换 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 接受。一个解决方案是将 alts 从 left_exp 移动到 exp 规则，然后应用我上面描述的算法。

ANTLR4 mutual left recursion grammar