Left recursion elimination in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why is left recursion problematic in top-down parsers?

Consider a top-down parser trying to parse a grammar with left recursion. Why does left recursion cause issues?

A It makes the parser run slower but does not affect correctness.

B It makes the parser skip some input tokens, leading to incorrect parsing.

C It causes the parser to reject all inputs, even valid ones.

D It causes the parser to enter an infinite loop because it keeps expanding the same rule without consuming input.

💡 Hint

Think about what happens when a parser tries to apply a rule that calls itself first.

Left recursion means a rule calls itself as the first step. A top-down parser tries to expand this rule repeatedly without moving forward in the input, causing an infinite loop.

📋 Factual

intermediate

Identify the left-recursive grammar rule

Which of the following grammar rules is left-recursive?

A A → A α | β

B A → β A | α

C A → α β | γ

D A → β | γ α

💡 Hint

Left recursion occurs when the rule's first symbol on the right side is the same as the left side.

Rule A → A α | β is left-recursive because the first symbol on the right side is the same as the left side non-terminal A.

🚀 Application

advanced

Eliminate left recursion from the grammar

Given the grammar rule: A → A α | β, which of the following is the correct equivalent grammar after eliminating left recursion?

A A → β | α A

B A → β A'<br>A' → α A' | ε

C A → β α | A'

D A → α A' | β

💡 Hint

Use the standard left recursion elimination formula: A → β A', A' → α A' | ε

To remove left recursion, we create a new non-terminal A' and rewrite the grammar as A → β A' and A' → α A' | ε, where ε means empty string.

🔍 Analysis

advanced

Determine the number of productions after elimination

Starting with the grammar rule S → S a | S b | c, how many productions will the grammar have after eliminating left recursion?

A 4

B 3

C 2

D 5

💡 Hint

First identify the left recursion, then apply elimination creating a new non-terminal.

The original rule has three productions. After elimination, it becomes S → c S' and S' → a S' | b S' | ε, totaling 4 productions.

❓ Reasoning

expert

Predict parser behavior with indirect left recursion

Consider the grammar:
A → B a | b
B → A c | d
Does this grammar contain left recursion? If yes, what kind?

A Yes, it contains direct left recursion because A calls B and B calls A directly.

B No, it does not contain left recursion because no rule starts with itself directly.

C Yes, it contains indirect left recursion because A calls B and B calls A starting with A again.

D No, it contains right recursion only.

💡 Hint

Check if a non-terminal can eventually call itself as the first symbol on the right side through other rules.

Indirect left recursion occurs when a non-terminal calls another non-terminal which eventually calls the first non-terminal again as the first symbol. Here, A → B a and B → A c form indirect left recursion.

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