Left Recursion
Left recursion is eliminated by converting the grammar into a right
recursive grammar.
If we have the left-recursive pair of productions-
A → Aα / β where β does not begin with an A.
Then, we can eliminate left recursion by replacing the pair of productions
with-
A → βA’
A’ → αA’ / ∈
Problem-01:
Consider the following grammar and eliminate left recursion-
A → ABd / Aa / a
B → Be / b
Solution-
The grammar after eliminating left recursion is-
A → aA’
A’ → BdA’ / aA’ / ∈
B → bB’
B’ → eB’ / ∈
Problem-02:
Consider the following grammar and eliminate left recursion-
E→E+E/ExE/a
Solution-
The grammar after eliminating left recursion is-
E → aA
A → +EA / xEA / ∈
Problem-03:
Consider the following grammar and eliminate left recursion-
E→E+T/T
T→TxF/F
F → id
Solution-
The grammar after eliminating left recursion is-
E → TE’
E’ → +TE’ / ∈
T → FT’
T’ → xFT’ / ∈
F → id
Problem-04:
S → (L) / a
L→L,S/S
Solution-
The grammar after eliminating left recursion is-
S → (L) / a
L → SL’
L’ → ,SL’ / ∈
Consider the following grammar and eliminate left recursion-
S → S0S1S / 01
Solution-
The grammar after eliminating left recursion is-
S → 01A
A → 0S1SA / ∈
Consider the following grammar and eliminate left recursion-
S→A
A → Ad / Ae / aB / ac
B → bBc / f
Solution-
S→A
A → aBA’ / acA’
A’ → dA’ / eA’ / ∈
B → bBc / f
A → Ba / Aa / c
B → Bb / Ab / d
Step-01:
First let us eliminate left recursion from A → Ba / Aa / c
A → BaA’ / cA’
A’ → aA’ / ∈
Now, given grammar becomes-
A → BaA’ / cA’
A’ → aA’ / ∈
B → Bb / Ab / d
Step-02:
Substituting the productions of A in B → Ab, we get the following grammar-
A → BaA’ / cA’
A’ → aA’ / ∈
B → Bb / BaA’b / cA’b / d
Step-03:
Now, eliminating left recursion from the productions of B, we get the
following grammar-
A → BaA’ / cA’
A’ → aA’ / ∈
B → cA’bB’ / dB’
B’ → bB’ / aA’bB’ / ∈
Left factoring
S → bSSaaS / bSSaSb / bSb / a
