πŸŽ“ Computer Science & Engineering Portal

Master Engineering Disciplines with Structured Notes

Comprehensive academic lecture notes, exam-oriented unit summaries, laboratory manuals, and previous year question papers designed strictly for university students.

πŸ“‘

University Syllabi

AKTU & AICTE aligned semester credit guidelines.

πŸ“

Exam Question Papers

Previous 5 years solved university semester papers.

πŸ’‘

Lab Manuals & Viva

Practical codes with outputs and interview questions.

πŸ“š All Topics & Units Directory

Click on any subject tag to open its genuine notes directly

Loading your subjects directory...

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 β†’ 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’ β†’ Ξ±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.

 

3. General Recursion- The recursion which is neither left recursion nor right recursion is called as general recursion.

 

Example- 

S β†’ aSb / βˆˆ

 

PRACTICE PROBLEMS BASED ON LEFT RECURSION ELIMINATION-

 

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.

Labels: ,

Discussion & Queries (<$I18NNumComments$>):

<$CommentPager$>
<$I18NAtCommentTimeWithPermalink$>, <$I18NCommentAuthorSaid$>

<$BlogCommentBody$>

<$BlogCommentDeleteIcon$>
<$CommentPager$>