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’ | ε