Elimination Linksrekursion für E: = EE + | EE- | id

Question

Wie Linksrekursion für die folgende Grammatik beseitigen?

E := EE+|EE-|id

das gemeinsame Verfahren:

A := Aa|b

übersetzt:

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

Angewandt auf die ursprüngliche Grammatik erhalten wir:

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

Deshalb:

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

Aber diese Grammatik scheint falsch, da

ϵE+ -> ϵ id +

wäre gültig aber das ist ein falscher Ausdruck postfix.

Answer 1

Ihr „einheitliches Verfahren“ wird falsch zitiert. Taking es aus dem Drachenbuch:

A := Aα | β

wird

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

... was ergibt:

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