Élimination gauche récursivité pour E: = EE + | EE- | id

Question

Comment éliminer la récursion gauche de la grammaire suivante?

E := EE+|EE-|id

En utilisant la procédure commune:

A := Aa|b

se traduit par:

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

En appliquant ceci à la grammaire originale, nous obtenons:

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

Par conséquent:

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

Mais cette grammaire semble incorrecte car

ϵE+ -> ϵ id +

serait valide mais c'est une expression postfixe incorrecte.

Answer 1

Votre "procédure commune" est mal citée. Tirant du livre du dragon:

A := Aα | β

devient

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

… qui donne:

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