CODEWITHSUNDEEP
left-recursion
Doh
Doh

Reputation: 113

Left recursion elimination issue

So I have this left recursive grammar

E → E Op1 E2 | E2

As it stand, it is left recursion, so I eliminated the left recursion by putting in another step:

E → X E2
X → E Op1 E2 | ε

I have a sinking feeling however that I eliminated it wrongly, because if I trace it then the FIRST set of E is still going to be starting with E. Am I correct? Or am I missing something? This question is a part of a bigger grammar set, FYI.

Upvotes: 1

Views: 59

Answers (1)

András Hummer
András Hummer

Reputation: 972

What you're missing is the second part of recursion elimination: instead of 

X → E Op1 E2 | ε

you need

X → Op1 E2 X | ε

Upvotes: 1

Related Questions