ANTLR4互左递归语法 [英] ANTLR4 mutual left recursion grammar

问题描述

我在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)*;

或一般而言:所有没有左递归的替代，然后是所有具有(除去)左递归且无限制出现的替代(通过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互左递归语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！