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.