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â€™ / âˆˆ

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 , + , $ , ) }