Left recursion elimination in Compiler Design - Mini Project: Build & Apply

Left Recursion Elimination in Grammar Rules

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

Removing left recursion is essential in compiler design to prepare grammar rules for top-down parsers like recursive descent parsers.

💼 Career

Understanding and eliminating left recursion is a fundamental skill for compiler engineers and language designers.

1

Create the initial grammar with left recursion

Create a dictionary called grammar with one entry: the key is 'A' and the value is a list of productions ['A a', 'b'] representing the left-recursive rule A -> A a | b.

Compiler Design

# Create the grammar dictionary with the left-recursive rule
# Your code here

Hint

Remember, the grammar dictionary key is the non-terminal symbol, and the value is a list of strings representing productions.

2

Set the non-terminal to eliminate left recursion from

Create a variable called non_terminal and set it to the string 'A', which is the symbol with left recursion in the grammar.

Compiler Design

grammar = {'A': ['A a', 'b']}
# Set the non-terminal symbol to 'A'
# Your code here

Hint

This variable helps focus on the rule that needs left recursion elimination.

3

Eliminate immediate left recursion from the grammar

Write code to eliminate the immediate left recursion from the rule for non_terminal. Create two lists: alpha for productions starting with non_terminal (left recursive), and beta for others. Then create new productions for non_terminal and a new symbol A_prime to remove left recursion.

Compiler Design

grammar = {'A': ['A a', 'b']}
non_terminal = 'A'
# Eliminate left recursion from grammar[non_terminal]
# Your code here

Hint

Separate productions into those that start with the non-terminal (alpha) and those that don't (beta). Then rewrite the grammar using a new symbol to remove left recursion.

4

Print the final updated grammar without left recursion

Print the grammar dictionary to verify that left recursion has been successfully eliminated. The output should show rules for 'A' and 'A\''.

Compiler Design

grammar = {'A': ['A a', 'b']}
non_terminal = 'A'
alpha = []
beta = []
for production in grammar[non_terminal]:
    if production.startswith(non_terminal):
        alpha.append(production[len(non_terminal):].strip())
    else:
        beta.append(production)
A_prime = non_terminal + "'"
grammar[non_terminal] = [b + ' ' + A_prime for b in beta]
grammar[A_prime] = [a + ' ' + A_prime for a in alpha] + ['ε']
# Print the grammar to verify
# Your code here

Hint

Use print(grammar) to display the updated grammar dictionary.

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