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 

Applyi开发者_开发知识库ng 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.

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′ | ϵ