Eliminating Left Recursion from a Grammar

By: Prof. Dr. Fazal Rehman | Last updated: March 3, 2022

Recursion can be classified into three types.

1. Left Recursion
2. Right Recursion
3. 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’ / ∈ F → (P) / id The first and follow functions are described below; First Functions

• First(P) = First(Q) = First(F) = { ( , id }
• First(P’) = { + , ∈ }
• First(Q) = First(F) = { ( , id }
• First(Q’) = { d , ∈ }
• First(F) = { ( , id }

Follow Functions

• Follow(P) = { $ , ) }
• Follow(P’) = Follow(E) = { $ , ) }
• Follow(Q) = { First(P’) – ∈ } ∪ Follow(P) ∪ Follow(P’) = { + , $ , ) }
• Follow(Q’) = Follow(Q) = { + , $ , ) }
• Follow(F) = { First(Q’) – ∈ } ∪ Follow(Q) ∪ Follow(Q’) = { d , + , $ , ) }