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′ | ϵ