Eliminación de la izquierda para E: = EE + | EE- | id

Question

¿Cómo eliminar la recursión izquierda para la siguiente gramática?

E := EE+|EE-|id

Utilizando el procedimiento común:

A := Aa|b

se traduce en:

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

Aplicando esto a la gramática original obtenemos:

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

Por lo tanto:

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

Pero esta gramática parece incorrecta porque

ϵE+ -> ϵ id +

sería válido pero esa es una expresión incorrecta de postfix.

Answer 1

Su "procedimiento común" se cita mal. Tomándolo del Libro del Dragón:

A := Aα | β

se convierte en

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

... que produce:

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