Eliminating Left Recursion from a Grammar

Before Eliminating Left Recursion from a Grammar, I want to share with you recursion types.

Recursion can be classified into three types.

Left Recursion
Right Recursion
General Recursion

Left Recursion

A production of grammar is Left recursive if the leftmost variable (Non-Terminal) of its RHS is similar to a variable of its LHS.
Left Recursive Grammar is a grammar having a left recursion.

Example of Eliminating Left Recursion from a Grammar

How to find the first and follow functions for the given CFG with Left Recursive production rules.?

S → H

H → aF / H d

F → b

C → t

The given grammar is left recursive. So, we first remove the left recursion from the given grammar.

After the elimination of left recursion, we get the following grammar.

S → H

H → a F H’

H’ → d H’ / ∈

F → b

C → t

The first and follow functions are described below;

First Functions

First(S) = First(H) = { a }
First(H) = { a }
First(H’) = { d , ∈ }
First(F) = { b }
First(C) = { t }

Follow Functions

Follow(S) = { $ }
Follow(H) = Follow(S) = { $ }
Follow(H’) = Follow(H) = { $ }
Follow(F) = { First(A’) – ∈ } ∪ Follow(A) = { d , $ }
Follow(C) = NA

Problem with Left Recursion

If a left recursion is present in any grammar then, it can lead to an infinite loop.

Example 2 of Removing Left Recursion from a CFG

How to find the first and follow functions for the given CFG with Left Recursive production rules.?

P→ P + Q / Q

Q → Q d F / F

F → (P) / id

Solution-

The given grammar is left recursive. So, we first remove the left recursion from the given grammar.

After the elimination of left recursion, we get the following grammar.

P → Q P’

P’ → + Q P’ / ∈

Q → F Q’

Q’ → d F Q’ / ∈