CODEWITHSUNDEEP
parsingcompiler-constructiongrammarcontext-free-grammarlexical-analysis
TheOne
TheOne

Reputation: 11159

Elimination left recursion for E := EE+|EE-|id

How to eliminate left recursion for the following grammar?

E := EE+|EE-|id

Using the common procedure:

A := Aa|b

translates to:

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

Applying this to the original grammar we get:

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

Therefore:

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

But this grammar seems incorrect because

ϵE+ -> ϵ id +

would be valid but that is an incorrect postfix expression.

Upvotes: 4

Views: 4006

Answers (1)

Konrad Rudolph
Konrad Rudolph

Reputation: 545488

Your “common procedure” is cited wrong. Taking it from the Dragon Book:

A := Aα | β

becomes

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

… which yields:

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

Upvotes: 11

Related Questions