Left Recursion | Left Recursion Elimination

Recursion-

Recursion can be classified into following three types-

1. Left Recursion
2. Right Recursion
3. General Recursion

1. Left Recursion-

• A production of grammar is said to have left recursion if the leftmost variable of its RHS is same as variable of its LHS.
• A grammar containing a production having left recursion is called as Left Recursive Grammar.

Example-

S → Sa /

(Left Recursive Grammar)

• Left recursion is considered to be a problematic situation for Top down parsers.
• Therefore, left recursion has to be eliminated from the grammar.

Elimination of Left Recursion

Left recursion is eliminated by converting the grammar into a right recursive grammar.

If we have the left-recursive pair of productions-

Aα / β

(Left Recursive Grammar)

where β does not begin with an A.

Then, we can eliminate left recursion by replacing the pair of productions with-

→ βA’

A’ → αA’ / ∈

(Right Recursive Grammar)

This right recursive grammar functions same as left recursive grammar.

2. Right Recursion-

• A production of grammar is said to have right recursion if the rightmost variable of its RHS is same as variable of its LHS.
• A grammar containing a production having right recursion is called as Right Recursive Grammar.

Example-

S → aS /

(Right Recursive Grammar)

• Right recursion does not create any problem for the Top down parsers.
• Therefore, there is no need of eliminating right recursion from the grammar.

Also Read- Types of Recursive Grammar

3. General Recursion-

• The recursion which is neither left recursion nor right recursion is called as general recursion.

S → aSb /

Problem-01:

Consider the following grammar and eliminate left recursion-

A → ABd / Aa / a

B → Be / b

Solution-

The grammar after eliminating left recursion is-

A → aA’

A’ → BdA’ / aA’ /

B → bB’

B’ → eB’ /

Problem-02:

Consider the following grammar and eliminate left recursion-

E → E + E / E x E / a

Solution-

The grammar after eliminating left recursion is-

E → aA

A → +EA / xEA /

Problem-03:

Consider the following grammar and eliminate left recursion-

E → E + T / T

T → T x F / F

F → id

Solution-

The grammar after eliminating left recursion is-

E → TE’

E’ → +TE’ /

T → FT’

T’ → xFT’ /

F → id

Problem-04:

Consider the following grammar and eliminate left recursion-

S → (L) / a

L → L , S / S

Solution-

The grammar after eliminating left recursion is-

S → (L) / a

L → SL’

L’ → ,SL’ /

Problem-05:

Consider the following grammar and eliminate left recursion-

S → S0S1S / 01

Solution-

The grammar after eliminating left recursion is-

S → 01A

A → 0S1SA /

Problem-06:

Consider the following grammar and eliminate left recursion-

S → A

A → Ad / Ae / aB / ac

B → bBc / f

Solution-

The grammar after eliminating left recursion is-

S → A

A → aBA’ / acA’

A’ → dA’ / eA’ /

B → bBc / f

Problem-07:

Consider the following grammar and eliminate left recursion-

A → AAα / β

Solution-

The grammar after eliminating left recursion is-

A → βA’

A’ → AαA’ /

Problem-08:

Consider the following grammar and eliminate left recursion-

A → Ba / Aa / c

B → Bb / Ab / d

Solution-

This is a case of indirect left recursion.

Step-01:

First let us eliminate left recursion from A → Ba / Aa / c

Eliminating left recursion from here, we get-

A → BaA’ / cA’

A’ → aA’ /

Now, given grammar becomes-

A → BaA’ / cA’

A’ → aA’ /

B → Bb / Ab / d

Step-02:

Substituting the productions of A in B → Ab, we get the following grammar-

A → BaA’ / cA’

A’ → aA’ /

B → Bb / BaA’b / cA’b / d

Step-03:

Now, eliminating left recursion from the productions of B, we get the following grammar-

A → BaA’ / cA’

A’ → aA’ /

B → cA’bB’ / dB’

B’ → bB’ / aA’bB’ /

This is the final grammar after eliminating left recursion.

Problem-09:

Consider the following grammar and eliminate left recursion-

X → XSb / Sa / b

S → Sb / Xa / a

Solution-

This is a case of indirect left recursion.

Step-01:

First let us eliminate left recursion from X → XSb / Sa / b

Eliminating left recursion from here, we get-

X → SaX’ / bX’

X’ → SbX’ /

Now, given grammar becomes-

X → SaX’ / bX’

X’ → SbX’ /

S → Sb / Xa / a

Step-02:

Substituting the productions of X in S → Xa, we get the following grammar-

X → SaX’ / bX’

X’ → SbX’ /

S → Sb / SaX’a / bX’a / a

Step-03:

Now, eliminating left recursion from the productions of S, we get the following grammar-

X → SaX’ / bX’

X’ → SbX’ /

S → bX’aS’ / aS’

S’ → bS’ / aX’aS’ /

This is the final grammar after eliminating left recursion.

Problem-10:

Consider the following grammar and eliminate left recursion-

S → Aa / b

A → Ac / Sd /

Solution-

This is a case of indirect left recursion.

Step-01:

First let us eliminate left recursion from S → Aa / b

This is already free from left recursion.

Step-02:

Substituting the productions of S in A → Sd, we get the following grammar-

S → Aa / b

A → Ac / Aad / bd /

Step-03:

Now, eliminating left recursion from the productions of A, we get the following grammar-

S → Aa / b

A → bdA’ / A’

A’ → cA’ / adA’ /

This is the final grammar after eliminating left recursion.

Also Read- Left Factoring

To gain better understanding about Left Recursion Elimination,

Watch this Video Lecture

Next Article- Types of Grammars

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Article Name
Left Recursion | Left Recursion Elimination
Description
Left Recursion- A production of grammar is said to have left recursion if leftmost variable of RHS is same as variable of LHS. Left Recursion Elimination. Examples on how to eliminate left recursion.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-