Left factoring in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is left factoring in compiler design?

Left factoring is a grammar transformation technique used to remove common prefixes from alternatives in a production rule to make the grammar suitable for top-down parsing.

beginner

Why is left factoring important in parsing?

Left factoring helps eliminate ambiguity caused by common prefixes in grammar rules, enabling predictive parsers to decide which production to use by looking at the next input symbol.

intermediate

Given the grammar rule:
A → αβ | αγ
How would left factoring transform this rule?

The rule is transformed to:
A → αA'
A' → β | γ
This removes the common prefix α from the alternatives.

intermediate

What problem does left recursion cause that left factoring helps to avoid?

Left recursion causes infinite recursion in top-down parsers. Left factoring does not remove left recursion but helps by making choices clear when alternatives share prefixes.

advanced

Can left factoring be applied multiple times on the same grammar? Why?

Yes, left factoring can be applied repeatedly until no two alternatives in a production share a common prefix, ensuring the grammar is fully factored for predictive parsing.

What is the main goal of left factoring in grammar rules?

A To add more production rules

B To remove common prefixes from alternatives

C To eliminate left recursion

D To convert grammar to Chomsky Normal Form

Left factoring removes common prefixes so parsers can decide which alternative to use by looking ahead.

Which type of parser benefits most from left factoring?

A LR parsers

B Bottom-up parsers

C Top-down predictive parsers

D Shift-reduce parsers

Top-down predictive parsers need left factoring to handle common prefixes and make parsing decisions.

Given the rule: S → if E then S else S | if E then S, what transformation does left factoring perform?

A S → if E then S S'<br>S' → else S | ε

B S → if E then S else S | if E then S

C S → if E then S else S

D No transformation needed

Left factoring extracts the common prefix 'if E then S' and creates a new rule S' for the alternatives.

Does left factoring remove left recursion from a grammar?

A Only for immediate left recursion

B Yes, always

C Only for indirect left recursion

D No, it only removes common prefixes

Left factoring does not remove left recursion; it only removes common prefixes to help predictive parsing.

What symbol is commonly introduced during left factoring to represent the factored part?

A A prime (A')

B A star (*)

C A plus (+)

D A question mark (?)

A prime (like A') is used to represent the new non-terminal holding the alternatives after factoring.

Explain what left factoring is and why it is used in compiler design.

Think about how parsers decide which rule to apply when alternatives start the same way.

Describe the steps to left factor the grammar rule: A → αβ | αγ | δ.

Focus on extracting the shared beginning part of the alternatives.

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