views:

234

answers:

1

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.

+6  A: 

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′ | ϵ
Konrad Rudolph
How do you input math symbols??
Absolute0
Absolute0: simple trick: I use a character table. I’m on OS X which has got a tool for that. On Windows, you can use `charmap.exe` which is hidden in the “Accessories” main menu (must be switched to Unicode, though).
Konrad Rudolph