ANTLR4 互左递归文法

问题描述

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

I have read many questions here on StackOverflow about mutual left-recursion issues in LL(k) parsers. I found the general algorithm for removing left-recursion:

A : Aa | b ;

变成

A : bR ;
R : (aA)? ;

但是，我不知道如何将其应用于我的情况.我有

However, I cannot figure out how to apply it to my situation. I have

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

少数其他规则"都包含正则递归，比如exp : exp PLUS exp 等，没有问题.问题在于 left_exp 和 exp 是相互递归的.

The "handful of other rules" all contain regular recursion, such as exp : exp PLUS exp, etc. and have no issues. The issue is with left_exp and exp being mutually recursive.

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

I thought about just adding IDENT and exp DOT IDENT to the exp rules, but there are some situations where the other valid exp rules do not apply, where left_exp would be valid.

编辑

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

I also have the following rule, which calls for a left expression followed by assignment.

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

由于正则表达式后面只有DOT IDENT才算左表达式，看来不能随便加

Since a regular expression is only a left expression if it is followed by DOT IDENT, it seems that I can't just add

| IDENT
| exp DOT IDENT

对于我的表达式定义，因为然后赋值会接受左侧的任何其他有效表达式，而不仅仅是这两个表达式中的一个.

to my expression definition, because then assignment would accept any other valid expression on the left side, rather than only one of those two.

推荐答案

我采用的方法通常是这样的:

The approach I apply usually goes like this:

A: Aa | b;

变成:

A: b (a)*;

或者一般来说:所有没有左递归的alt，然后是所有带有(删除)左递归的alt，出现次数不受限制(通过kleene算子表示).示例:

Or in general: all alts without left recursion followed by all alts with a (removed) left recursion with unlimited occurences (expressed via the kleene operator). Example:

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

变成:

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

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

您可以通过不断替换 A 来轻松检查:

You can check this easily by continuosly replacing 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 规则，然后应用我上面描述的算法.

In your example however you have an indirect left recursion (via 2 rules). This is not accepted by ANTLR. A solution is to move the alts from left_exp to the exp rule and then apply the algorithm I described above.

这篇关于ANTLR4 互左递归文法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！