Left factoring in Compiler Design - Step-by-Step Execution

Concept Flow - Left factoring

Start with grammar

↓

Identify common prefixes

↓

Extract common prefix

↓

Rewrite grammar rules

↓

Check if grammar is left factored

No↓

Repeat process

Yes↓

End

Left factoring rewrites grammar rules by extracting common prefixes to remove ambiguity and make parsing easier.

Execution Sample

Compiler Design

A -> a b c | a b d
Rewrite as:
A -> a b A'
A' -> c | d

This example shows how to factor out the common prefix 'a b' from two alternatives.

Analysis Table

Step	Grammar Rule	Common Prefix Found	Action Taken	Resulting Rule
1	A -> a b c | a b d	a b	Extract prefix 'a b'	A -> a b A'
2	A' -> c | d	None	Define new rule for suffixes	A' -> c | d
3	Check for more prefixes	None	No more common prefixes	Grammar is left factored
4	End	-	-	Process complete

💡 No more common prefixes found; grammar is left factored.

State Tracker

Variable	Start	After Step 1	After Step 2	Final
Grammar Rules	A -> a b c | a b d	A -> a b A'	A -> a b A'	A -> a b A' and A' -> c | d
Common Prefix	None	a b	None	None

Key Insights - 2 Insights

Why do we extract the common prefix 'a b' instead of rewriting each alternative separately?

Extracting the common prefix 'a b' groups shared parts to avoid ambiguity and make parsing decisions easier, as shown in execution_table step 1.

What happens if there are no common prefixes in the grammar?

If no common prefixes exist, the grammar is already left factored and no changes are needed, as seen in execution_table step 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what common prefix is extracted?

A "a"

B "a b"

C "b c"

D "c d"

💡 Hint

Check the 'Common Prefix Found' column in step 1 of execution_table.

At which step does the grammar become left factored according to the execution_table?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look at the 'Resulting Rule' column for the step indicating grammar is left factored.

If the original grammar had no common prefixes, how would the execution_table change?

A Step 2 would extract a prefix anyway.

B The process would repeat indefinitely.

C Step 1 would show 'None' for common prefix and no extraction.

D A new rule would be created regardless.

💡 Hint

Refer to key_moments about what happens when no common prefixes exist.

Concept Snapshot

Left factoring removes common prefixes from grammar rules.
It rewrites rules to factor out shared beginnings.
This helps parsers decide which rule to use.
Process repeats until no common prefixes remain.
Example: A -> a b c | a b d becomes A -> a b A', A' -> c | d.

Full Transcript

Left factoring is a technique used in grammar design to remove ambiguity by extracting common prefixes from alternatives. The process starts by identifying common prefixes in grammar rules. When a common prefix is found, it is extracted and a new rule is created for the differing suffixes. This rewriting continues until no common prefixes remain, resulting in a left factored grammar that is easier for parsers to handle. For example, the rule A -> a b c | a b d is rewritten as A -> a b A' and A' -> c | d, factoring out the common prefix 'a b'. This process ensures the grammar is unambiguous and suitable for top-down parsing.

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