What is left recursion and how do you eliminate left recursion?

Left recursion

A grammar in the form G = (V, T, S, P) is said to be in left recursive form if it has the production rules of the form A → A α |β.

• In the production rule above, the variable in the left side occurs at the first position on the right side production, due to which the left recursion occurs.

• If we have a left recursion in our grammar, then it leads to infinite recursion, due to which we cannot generate the given string.

How to eliminate left recursion

We can eliminate left recursion by replacing a pair of production with:

A → βA′

A′ → αA′|ϵ

Example:

i) E → E+T|T

ii) T → T*F|F

iii) F → (E)|id

The left and right variables are the same in the production rules above, that is, E and T.

So to eliminate the left recursion, we have to change the production rules to a different form.

In the production rules above:

i) E → E+T|T

α=+T and  β=T

E → TE′

E′→ +TE′|ϵ

In the production rule above, we still have left recursion:

ii) T → T*F|F 

α=*F and  β=F

T → FT′

T′→ *FT′|ϵ

After eliminating the left recursion, the final production rules are as follows:

E → TE′

E′→ +TE′|ϵ

T → FT′

T′→ *FT′|ϵ

F → (E)|id