Eliminating Left Recursion in Compiler

In this class, We discuss Eliminating Left Recursion in Compiler.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of eliminating left recursion from the Theory of computation. Click Here.

Here we understand the use of eliminating left recursion in the compiler.

The below example grammar is our expression grammar for identifying expressions.

E – E + T | T

T – T * F | F

F – id | (E)

The below derivation tree helps in understanding the need to eliminate left recursion.

E is expanded for the first time.

Second time E is expanded. This expansion keeps going on.

Where did we need to stop expanding? Unable to identify.

So we need to eliminate left recursion.

Example of left recursive grammar:

A – Aα | β the production is in left recursion.

The below grammar shows the equivalent grammar after eliminating left recursion.

A – βA’

A’ – αA’ | ε

Expression grammar after eliminating left recursion:

E – E+T | T

E is considered as A

+T is considered as α

T is considered as β

E – TE’

E’ – +TE’ | ε

T – FT’

T’ – *FT’

F – id

F – (E)