消除E：= EE + | EE- | id的左递归

Question

如何消除以下语法的左递归？

E := EE+|EE-|id

使用常用程序：

A := Aa|b

转换为：

A := b|A'
A' := ϵ| Aa 

将它应用于我们得到的原始语法：

A = E, a = (E+|E-) and b = id

因此：

E := id|E'
E' := ϵ|E(E+|E-)

但是这个语法似乎不正确，因为

ϵE+ -> ϵ id +

是有效的 但这是一个不正确的后缀表达式。

Answer 1

您的常规程序＆＃8221;被引错了。从龙书中取出：

A := Aα | β

变为

A  := βA′
A′ := αA′ | ϵ

＆＃8230;产生：

E  := id E′
E′ := (E + | E -) E′ | ϵ