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

Need a 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

Need a 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

Need a 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

Need a hint?

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