我在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
将是有效的。
编辑
我还有下面的规则,它要求一个左表达式,然后是赋值。
assign_statement: left_exp ( COLON IDENT )? EQUAL exp SEMI ;
因为正则表达式如果后面跟着DOT IDENT,那么它只是一个左表达式,所以我似乎不能仅仅添加
| IDENT
| exp DOT IDENT
对于我的表达式定义,因为赋值将接受左边的任何其他有效表达式,而不是仅接受这两个表达式中的一个。
发布于 2017-01-22 01:00:01
我采用的方法通常是这样的:
A: Aa | b;
变成:
A: b (a)*;
或者一般情况下:所有没有左递归的all,以及所有具有(已删除的)左递归且无限制发生的all (通过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
规则,然后应用我前面描述的算法。
https://stackoverflow.com/questions/41788100
复制相似问题