Left factoring in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of left factoring

Why is left factoring applied to a grammar in compiler design?

A To remove ambiguity by eliminating common prefixes in productions

B To convert a grammar into Chomsky Normal Form

C To increase the number of productions for better parsing

D To remove left recursion from the grammar

💡 Hint

Think about what problem left factoring solves in top-down parsers.

Left factoring is used to remove common prefixes in productions to make the grammar suitable for predictive parsing by eliminating ambiguity caused by those prefixes.

🚀 Application

intermediate

Applying left factoring to a grammar

Given the grammar:
S -> if E then S else S | if E then S | other
Which is the correct left factored form?

A S -> if E then S else S | other

B S -> if E then S S' | other<br>S' -> else S | ε

C S -> if E then S else S | if E then S | other

D S -> if E then S else S else S | other

💡 Hint

Look for the common prefix in the productions and factor it out.

The productions starting with 'if E then S' share a common prefix. Left factoring extracts this prefix and introduces a new production S' to handle the optional 'else S'.

🔍 Analysis

advanced

Identifying when left factoring is necessary

Consider the grammar:
A -> a B | a C | d
Which problem does this grammar present for a predictive parser?

A It has unreachable productions

B It contains left recursion

C It is ambiguous due to multiple start symbols

D It has common prefixes causing parsing conflicts

💡 Hint

Check if productions start with the same symbol.

The productions 'a B' and 'a C' share the prefix 'a', which causes predictive parsing conflicts. Left factoring is needed to resolve this.

❓ Comparison

advanced

Comparing left factoring and left recursion removal

Which statement correctly distinguishes left factoring from left recursion removal?

A Left factoring removes common prefixes; left recursion removal eliminates productions where a non-terminal calls itself on the left

B Both techniques remove ambiguity by the same method

C Left factoring eliminates left recursion; left recursion removal removes common prefixes

D Left factoring and left recursion removal are identical processes

💡 Hint

Consider what each technique targets in grammar transformations.

Left factoring targets common prefixes to help predictive parsing, while left recursion removal targets productions where a non-terminal calls itself first to avoid infinite recursion.

❓ Reasoning

expert

Effect of left factoring on FIRST sets

After applying left factoring to a grammar, what is the effect on the FIRST sets of the affected non-terminals?

A The FIRST sets become empty because productions are split

B The FIRST sets always become larger due to added productions

C The FIRST sets remain the same because left factoring only restructures productions without changing terminals

D The FIRST sets become disjoint sets to avoid conflicts

💡 Hint

Think about whether left factoring changes the terminals that can appear first.

Left factoring restructures productions by factoring out common prefixes but does not change the set of terminals that can appear first, so FIRST sets remain unchanged.

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