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.