消除E:= EE + | EE- | id的左递归
题
如何消除以下语法的左递归?
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 +
是有效的 但这是一个不正确的后缀表达式。
解决方案
您的常规程序”被引错了。从龙书中取出:
A := Aα | β
变为
A := βA′
A′ := αA′ | ϵ
…产生:
E := id E′
E′ := (E + | E -) E′ | ϵ
不隶属于 StackOverflow