Eliminazione sinistra ricorsione per E: = EE + | EE- | id

Question

Come eliminare la ricorsione a sinistra per la seguente grammatica?

E := EE+|EE-|id

Utilizzando la procedura comune:

A := Aa|b

si traduce in:

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

Applicando questo alla grammatica originale otteniamo:

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

Quindi:

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

Ma questa grammatica sembra errata perché

ϵE+ -> ϵ id +

sarebbe valido ma questa è un'espressione postfix errata.

Answer 1

La tua & # 8220; procedura comune & # 8221; è citato male. Prendendolo dal Libro del Drago:

A := Aα | β

diventa

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

& # 8230; che produce:

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