Left recursion elimination in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify if a grammar rule is left recursive.

Compiler Design

if production.startswith([1]):
    print("Left recursion detected")

Drag options to blanks, or click blank then click option'

Aepsilon

Bterminal

Cnon_terminal

Ddigit

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing terminal with non-terminal symbols.

The left recursion occurs when the production starts with the same non-terminal symbol on the left side.

2fill in blank

medium

Complete the code to remove immediate left recursion from a grammar rule.

Compiler Design

A -> A [1] | beta
Rewrite as:
A -> beta A'
A' -> [2] A' | epsilon

Drag options to blanks, or click blank then click option'

Aalpha

Bbeta

Cepsilon

Dgamma

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up alpha and beta parts.

Immediate left recursion is removed by factoring out the left recursive part 'alpha'.

3fill in blank

hard

Fix the error in the code that eliminates left recursion.

Compiler Design

while productions and productions[0].startswith([1]):
    left_recursive.append(productions.pop(0))

Drag options to blanks, or click blank then click option'

Aterminal

Bnon_terminal

Cbeta

Dalpha

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for terminal or beta instead of non-terminal.

The code checks if the production starts with the non-terminal symbol to find left recursion.

4fill in blank

hard

Fill both blanks to correctly rewrite a left recursive grammar rule.

Compiler Design

A -> [1] A'
A' -> [2] A' | epsilon

Drag options to blanks, or click blank then click option'

Abeta

Balpha

Cgamma

Ddelta

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping alpha and beta parts.

The non-left-recursive part is 'beta', and the recursive part is 'alpha' used in A'.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that eliminates left recursion.

Compiler Design

new_productions = { [1]: [2] for [3] in productions if not [3].startswith(non_terminal) }

Drag options to blanks, or click blank then click option'

Aprod

Bproductions[prod]

Dnon_terminal

Attempts:

3 left

💡 Hint

Common Mistakes

Using inconsistent variable names or wrong filtering condition.

The comprehension iterates over productions using 'prod', maps keys to productions[prod], and filters out left recursive productions starting with the non-terminal.

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