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.
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