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

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

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

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

Hint

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

Practice

1. What is the main purpose of left factoring in compiler design?

easy

A. To remove common prefixes from grammar rules to simplify parsing

B. To eliminate left recursion from grammar rules

C. To optimize the speed of code execution

D. To convert grammar rules into machine code

Solution

1. Step 1: Understand left factoring concept

   Left factoring is used to remove common prefixes from grammar rules to make parsing decisions easier.

2. Step 2: Differentiate from other grammar techniques

   Unlike eliminating left recursion or code optimization, left factoring focuses on simplifying grammar by factoring out common starts.

3. Final Answer:

   To remove common prefixes from grammar rules to simplify parsing -> Option A

4. Quick Check:

   Left factoring = remove common prefixes [OK]

Hint: Left factoring removes common starts in grammar rules [OK]

Common Mistakes:

• Confusing left factoring with left recursion elimination
• Thinking it optimizes runtime code
• Assuming it generates machine code

2. Which of the following is the correct left factored form of the grammar rule:
A -> a b | a c?

easy

A. A -> b | c

B. A -> (a b) | c

C. A -> a b c

D. A -> a (b | c)

Solution

1. Step 1: Identify common prefix in rules

   Both alternatives start with 'a', so 'a' is the common prefix.

2. Step 2: Factor out the common prefix

   Rewrite as A -> a (b | c) to factor out 'a'.

3. Final Answer:

   A -> a (b | c) -> Option D

4. Quick Check:

   Common prefix 'a' factored out [OK]

Hint: Factor out the common start before alternatives [OK]

Common Mistakes:

• Not factoring out the common prefix 'a'
• Combining alternatives incorrectly
• Removing essential parts of the rule

3. Given the grammar rule:
S -> if E then S else S | if E then S
What is the left factored form?

medium

A. S -> if E then S (else S | ε)

B. S -> if E then S else S | if E then S

C. S -> if (E then S else S | E then S)

D. S -> if E then (S else S | S)

Solution

1. Step 1: Identify common prefix in alternatives

   Both alternatives start with if E then S.

2. Step 2: Factor out the common prefix

   Rewrite as S -> if E then S (else S | ε), where ε means empty (no else).

3. Final Answer:

   S -> if E then S (else S | ε) -> Option A

4. Quick Check:

   Common prefix factored with optional else [OK]

Hint: Factor out full common start, use ε for optional parts [OK]

Common Mistakes:

• Not factoring out the entire common prefix
• Misplacing parentheses
• Ignoring the optional else part

4. Identify the error in the following left factoring attempt:
Original: A -> a b | a c d
Attempted: A -> a (b | c d)

medium

A. Incorrect grouping; 'c d' should be separated

B. Correct left factoring, no error

C. Missing a new rule for 'c d'

D. Should factor out 'a b' instead of 'a'

Solution

1. Step 1: Analyze the original and attempted factoring

   Original rules share common prefix 'a'. Alternatives are 'b' and 'c d'.

2. Step 2: Verify correctness

   The attempt A -> a (b | c d) is correct: it generates a b and a c d. Sequences like 'c d' are valid in alternatives.

3. Final Answer:

   Correct left factoring, no error -> Option B

4. Quick Check:

   Same language generated [OK]

Hint: Check if grouped parts are single tokens or sequences [OK]

Common Mistakes:

• Confusing left factoring with left recursion elimination
• Thinking it optimizes runtime code
• Assuming it generates machine code

5. Given the grammar:
Expr -> Expr + Term | Expr - Term | Term
Apply left factoring to this grammar.

hard

A. Expr -> Term + Term | Term - Term

B. Expr -> (Expr + Term) | (Expr - Term) | Term

C. Expr -> Term Expr'; Expr' -> (+ | -) Term Expr' | ε

D. Expr -> Term ( + Term | - Term )

Solution

1. Step 1: Identify left recursion and common prefix

   The rule is left recursive: Expr -> Expr + Term | Expr - Term | Term.

2. Step 2: Remove left recursion and apply left factoring

   Rewrite as:
   Expr -> Term Expr'
Expr' -> (+ | -) Term Expr' | ε to factor out common prefix and remove recursion.

3. Final Answer:

   Expr -> Term Expr'; Expr' -> (+ | -) Term Expr' | ε -> Option C

4. Quick Check:

   Left recursion removed and common prefix factored [OK]

Hint: Remove left recursion first, then factor common prefixes [OK]

Common Mistakes:

• Not removing left recursion before factoring
• Incorrectly grouping alternatives
• Ignoring the ε (empty) option