Left factoring in Compiler Design - Mini Project: Build & Apply

Left Factoring a Grammar

📖 Scenario: You are working on a simple compiler design task. You have a grammar with some rules that have common prefixes. To make the grammar easier to parse, you need to apply left factoring.

🎯 Goal: Transform a given grammar rule by applying left factoring to remove common prefixes.

📋 What You'll Learn

Create a dictionary called grammar with one rule named stmt and its productions as a list of strings

Create a variable called common_prefix to hold the common prefix string

Create a new dictionary called factored_grammar that applies left factoring to the stmt rule

Add a new rule called stmt_prime to the factored_grammar dictionary to complete the left factoring

💡 Why This Matters

🌍 Real World

Left factoring is used in compiler design to transform grammars so that parsers can decide which rule to apply by looking at the next input symbol.

💼 Career

Understanding left factoring helps in building efficient parsers and is a key skill for compiler engineers and language designers.

1

DATA SETUP: Define the initial grammar

Create a dictionary called grammar with one key 'stmt' and its value as a list of strings: 'if expr then stmt', 'if expr then stmt else stmt', and 'other'.

Compiler Design

# Create the grammar dictionary with the 'stmt' rule and its productions
# Your code here

Need a hint?

Use a dictionary with key 'stmt' and a list of the exact strings as values.

2

CONFIGURATION: Identify the common prefix

Create a variable called common_prefix and set it to the string 'if expr then stmt' which is the common prefix in the stmt productions.

Compiler Design

grammar = {
    'stmt': ['if expr then stmt', 'if expr then stmt else stmt', 'other']
}

# Define the common prefix string
# Your code here

Need a hint?

Assign the exact string 'if expr then stmt' to the variable common_prefix.

3

CORE LOGIC: Apply left factoring to create a new grammar dictionary

Create a new dictionary called factored_grammar. For the key 'stmt', assign a list with two elements: the common_prefix string and the string stmt_prime. For the key 'stmt_prime', assign a list with two elements: the string 'else stmt' and the string '' (empty string).

Compiler Design

grammar = {
    'stmt': ['if expr then stmt', 'if expr then stmt else stmt', 'other']
}

common_prefix = 'if expr then stmt'

# Create the factored_grammar dictionary applying left factoring
# Your code here

Need a hint?

Use the variable common_prefix and create the new keys and lists exactly as described.

4

COMPLETION: Finalize the left factored grammar

Ensure the factored_grammar dictionary includes the keys 'stmt' and 'stmt_prime' with their respective lists as defined. This completes the left factoring transformation.

Compiler Design

grammar = {
    'stmt': ['if expr then stmt', 'if expr then stmt else stmt', 'other']
}

common_prefix = 'if expr then stmt'

factored_grammar = {
    'stmt': [common_prefix, 'stmt_prime'],
    'stmt_prime': ['else stmt', '']
}

# Final check: the factored_grammar dictionary is complete
# Your code here

Need a hint?

Make sure the dictionary factored_grammar has the exact keys and values as before.