Scribd
Upload
15 views5 pages

Eliminating Left Recursion in Grammar

The document explains left recursion in grammar, defining it as a situation where the leftmost variable of a production's right-hand side matches the left-hand side variable. It details the process of eliminating left recursion by converting left-recursive grammars into right-recursive ones, providing examples and solutions for specific grammars. The final transformed grammars are presented after the elimination of left recursion.

Uploaded by

devansh kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
15 views5 pages

Eliminating Left Recursion in Grammar

The document explains left recursion in grammar, defining it as a situation where the leftmost variable of a production's right-hand side matches the left-hand side variable. It details the process of eliminating left recursion by converting left-recursive grammars into right-recursive ones, providing examples and solutions for specific grammars. The final transformed grammars are presented after the elimination of left recursion.

Uploaded by

devansh kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Program-2

Wap to remove left recursion.


Left 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
• 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’ / ∈
Problem:

• Consider the following grammar and eliminate left recursion-


• E→E+T/T
• T→TxF/F
• F → id
• Solution-
A → Aα / β
1)A → βA’
2)A’ → αA’ / ∈

• The grammar after eliminating left recursion is-


• E → TE’
• E’ → +TE’ / ∈
• T → FT’
• T’ → xFT’ / ∈
• F → id
Problem:

:
• Consider the following grammar and eliminate left recursion-
• A → ABd / Aa / a
• B → Be / b
• Solution-
• A → Aα / β
1)A → βA’
2)A’ → αA’ / ∈

• The grammar after eliminating left recursion is-


• A → aA’
• A’ → BdA’ / aA’ / ∈
• B → bB’
• B’ → eB’ / ∈

You might also like