Eliminating Left Recursion Examples
In this class, We discuss Eliminating Left Recursion Examples.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of Eliminating Left Recursion procedure. Click Here.
Example 1:
S – S0S1S | 01
The above grammar is left recursive.
The above grammar is of the form A – Aα | β
α = 0S1S and β = 01
We can write the left recursive grammar as
A – aA’
A’ – bA’ | ε
Final grammar with out left recursion
S – 01S’
S’ – 0S1SS’ | ε
Example 2:
A – ABd | Aa | a
B – Be | b
Production A has left recursion in two options.
The two options are written as A – A(Bd | a) | a
Now the production A is of the form A – Aα | β
Now, we can eliminate left recursion using the above equation in example 1.
A – aA’
A’ – BdA’ | aA’ | ε
Similarly, production B also converted.
B – bB’
B’ – eB’ | ε
Example 3:
S – Aa | b
A – Ac | Sd | c
We have an indirect possibility of left recursion.
Now we substitute S and eliminate left recursion in A.
After substituting S, we get A – Ac | Aad | bd | c
From the second example, we can eliminate left recursion for production A.
A – A(c | ad) | bd | c
The above production is of the form A – Aα | β
Now we eliminate left recursion using the equation given in example 1.
A – bdA’ | cA’
A’ – cA’ | adA’ | ε