Eliminação deixou recursão para E: = EE + | EE | id

Question

Como eliminar a recursão esquerda para a seguinte gramática?

E := EE+|EE-|id

Usando o procedimento comum:

A := Aa|b

traduz em:

A := b|A'
A' := ϵ| Aa 

A aplicação deste à gramática originais obtemos:

A = E, a = (E+|E-) and b = id

Por isso:

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

Mas essa gramática parece porque incorreta

ϵE+ -> ϵ id +

seria válida mas isso é uma expressão postfix incorreta.

Answer 1

O seu “procedimento comum” é citado errado. Tomando-lo a partir do livro Dragon:

A := Aα | β

se torna

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

... que produz:

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