Исключение левой рекурсии для 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′ | ϵ