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

あなたの＆＃8220;一般的な手順＆＃8221;間違って引用されています。ドラゴンブックからそれを取ります：

A := Aα | β

なる

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

＆＃8230;結果：

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