parsing - 消除 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

您的“通用程序”被引用错误。取自龙书：

A := Aα | β

变成

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

…产生：

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