Left recursion elimination in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is left recursion in grammar rules?

Left recursion occurs when a grammar rule refers to itself as the first symbol on the right side, causing potential infinite loops in parsers.

beginner

Why must left recursion be eliminated in top-down parsers?

Because top-down parsers like recursive descent can get stuck in infinite loops when processing left-recursive rules.

intermediate

What is the general approach to eliminate immediate left recursion?

Rewrite the rule A → Aα | β as A → βA' and A' → αA' | ε, where A' is a new rule and ε means empty string.

beginner

What does ε represent in grammar rules after left recursion elimination?

ε represents the empty string, meaning the rule can end without producing any symbol.

intermediate

How is indirect left recursion different from immediate left recursion?

Indirect left recursion happens when a rule refers to another rule that eventually refers back to the first rule on the left side, unlike immediate left recursion which is direct self-reference.

What problem does left recursion cause in top-down parsers?

A Syntax errors

B Infinite recursion or loops

C Memory overflow

D Faster parsing

Left recursion causes the parser to call itself repeatedly without progress, leading to infinite loops.

Which of the following is a correct way to eliminate immediate left recursion from A → Aα | β?

A A → βA' and A' → αA' | ε

B A → Aβ and β → α

C A → αA and A → β

D A → α | β

The standard method introduces a new rule A' to remove left recursion by factoring out the recursive part.

In left recursion elimination, what does the new rule A' typically represent?

A A helper rule to handle repeated patterns

B The original rule unchanged

C A terminal symbol

D An error state

A' is a new rule that helps rewrite the grammar to avoid left recursion by handling repetitions.

What does ε stand for in grammar rules?

A Start symbol

B Error

C End of input

D Empty string

ε means the rule can produce nothing, allowing the parser to stop recursion.

Indirect left recursion involves:

A No recursion at all

B A rule referring to itself directly

C Multiple rules referring back to the original rule

D Only terminal symbols

Indirect left recursion happens when recursion occurs through a chain of rules, not directly.

Explain why left recursion must be eliminated for top-down parsers and describe the general method to remove immediate left recursion.

Think about how recursive calls behave in top-down parsing.

Describe the difference between immediate and indirect left recursion and why indirect left recursion is more complex to eliminate.

Consider how rules refer to each other in a grammar.

Practice

1. What is the main reason to eliminate left recursion in a grammar?

easy

A. To simplify bottom-up parsing

B. To make the grammar ambiguous

C. To increase the number of production rules

D. To prevent infinite loops in top-down parsers

Solution

1. Step 1: Understand left recursion impact

   Left recursion causes a parser to repeatedly call the same rule without consuming input, leading to infinite loops in top-down parsers.

2. Step 2: Identify the goal of elimination

   Eliminating left recursion removes this infinite loop problem, making the grammar usable for top-down parsing methods like recursive descent.

3. Final Answer:

   To prevent infinite loops in top-down parsers -> Option D

4. Quick Check:

   Left recursion causes infinite loops = Prevent infinite loops [OK]

Hint: Left recursion causes infinite loops; remove it for top-down parsing [OK]

Common Mistakes:

• Thinking left recursion improves parsing speed
• Confusing left recursion with ambiguity
• Believing bottom-up parsers require left recursion elimination

2. Which of the following is the correct way to start eliminating immediate left recursion from a rule A -> A α | β?

easy

A. Rewrite as A -> β A' and A' -> α A' | ε

B. Rewrite as A -> α A | β

C. Rewrite as A -> β | α A' and A' -> ε

D. Rewrite as A -> A' β and A' -> α | ε

Solution

1. Step 1: Identify immediate left recursion pattern

   The rule A -> A α | β has immediate left recursion because A appears on the left side of its own production.

2. Step 2: Apply standard elimination method

   Rewrite as A -> β A' and A' -> α A' | ε to remove left recursion by introducing a new non-terminal A'.

3. Final Answer:

   Rewrite as A -> β A' and A' -> α A' | ε -> Option A

4. Quick Check:

   Immediate left recursion elimination uses new non-terminal A' [OK]

Hint: Use new non-terminal and right recursion to remove immediate left recursion [OK]

Common Mistakes:

• Not introducing a new non-terminal
• Swapping α and β incorrectly
• Leaving left recursion in the rewritten rules

3. Given the grammar rule E -> E + T | T, after eliminating left recursion, what is the correct equivalent set of productions?

medium

A. E -> T E'E' -> + T E' | ε

B. E -> E' + TE' -> T | ε

C. E -> T + E'E' -> T | ε

D. E -> T | E' + TE' -> + T | ε

Solution

1. Step 1: Identify left recursion in E -> E + T | T

   The rule is immediately left recursive because E appears on the left side of its own production.

2. Step 2: Apply left recursion elimination formula

   Rewrite as E -> T E' and E' -> + T E' | ε where E' is a new non-terminal handling the recursion on the right side.

3. Final Answer:

   E -> T E' and E' -> + T E' | ε -> Option A

4. Quick Check:

   Left recursion removed by new non-terminal E' [OK]

Hint: Rewrite left recursion as right recursion with new non-terminal [OK]

Common Mistakes:

• Placing '+' before T incorrectly
• Not adding epsilon (ε) to new rule
• Mixing order of productions

4. Consider the grammar rule S -> S a | b. Which of the following corrected versions properly eliminates left recursion?

medium

A. S -> S' bS' -> a | ε

B. S -> b | a S'S' -> S | ε

C. S -> b S'S' -> a S' | ε

D. S -> b a S'S' -> S | ε

Solution

1. Step 1: Identify immediate left recursion in S -> S a | b

   The rule is left recursive because S appears on the left side of its own production.

2. Step 2: Rewrite to remove left recursion

   Rewrite as S -> b S' and S' -> a S' | ε introducing new non-terminal S' to handle recursion on the right side.

3. Final Answer:

   S -> b S' and S' -> a S' | ε -> Option C

4. Quick Check:

   Left recursion removed by new non-terminal S' [OK]

Hint: New non-terminal after base case removes left recursion [OK]

Common Mistakes:

• Placing recursion on the left side again
• Not including epsilon (ε) in new rule
• Swapping terminals and non-terminals incorrectly

5. Given the indirect left recursion in the grammar:
A -> B a | c
B -> A b | d
Which of the following is the correct first step to eliminate left recursion?

hard

A. Remove B from the grammar

B. Substitute B in A's productions to get immediate left recursion

C. Replace B with d in all rules

D. Directly rewrite A as A -> c A' and A' -> a A' | ε

Solution

1. Step 1: Identify indirect left recursion

   Here, A calls B and B calls A, causing indirect left recursion.

2. Step 2: Substitute B's productions into A

   Replace B in A -> B a | c with A b | d to get A -> A b a | d a | c, creating immediate left recursion.

3. Step 3: Eliminate immediate left recursion

   Now apply immediate left recursion elimination on A.

4. Final Answer:

   Substitute B in A's productions to get immediate left recursion -> Option B

5. Quick Check:

   Indirect recursion -> substitution -> immediate recursion [OK]

Hint: Convert indirect to immediate recursion by substitution first [OK]

Common Mistakes:

• Trying to eliminate without substitution
• Removing non-terminals incorrectly
• Ignoring indirect recursion