Left Factoring

Learn how to remove ambiguity in top-down parsing caused by multiple productions sharing the same prefix — by factoring out the common part into a new rule.

The Problem — Choosing Between Productions

A predictive (top-down) parser must decide which production rule to use after seeing only the next token in the input (called the lookahead). This works when each rule starts with a different token.

But what if two productions start with the same symbol?

Example

stmt → if ( expr ) stmt

| if ( expr ) stmt else stmt

When the parser sees if, it cannot tell whether to use the first or second production — both start with if ( expr ) stmt. It has to look ahead further to decide, which breaks the simple one-token lookahead model.

Another example:

Example

A → a b c

| a b d

The parser sees a — should it use rule 1 or rule 2? It cannot decide until it sees the third token (c or d). A single-token lookahead is not enough.

Left factoring solves this by pulling out the common prefix into a new rule, so the choice is deferred until after the shared part is consumed.

How Left Factoring Works

Left factoring rewrites productions that share a common prefix. The common prefix becomes one rule, and the differing suffixes become alternatives in a helper non-terminal.

The General Pattern

Before (problem — common prefix α):

Example

A → α β₁

| α β₂

| α β₃

| γ ← this one does not share the prefix

After left factoring:

Example

A → α A' | γ

A' → β₁ | β₂ | β₃

Now when the parser sees the start of α, it uses A → α A'. After consuming α, the lookahead determines which A' production to use.

Example 1 — Simple Case

Original:

Example

A → a b c

| a b d

Common prefix: a b

After left factoring:

Example

A → a b A'

A' → c | d

Now the parser reads a b, then looks at the next token:

If it sees c → use A' → c
If it sees d → use A' → d

One token of lookahead is enough.

Example 2 — The Dangling Else

Original:

Example

stmt → if ( expr ) stmt

| if ( expr ) stmt else stmt

| other

Common prefix: if ( expr ) stmt

After left factoring:

Example

stmt → if ( expr ) stmt stmt'

| other

stmt' → else stmt

| ε

Now:

After parsing if ( expr ) stmt, look at the next token.
If it is else → use stmt' → else stmt
Otherwise → use stmt' → ε (no else branch)

The Left Factoring Algorithm

The algorithm to left-factor a grammar systematically:

Example

For each non-terminal A:

1. Find the longest common prefix α shared by two or more productions of A.

2. If such a prefix exists:

a. Create a new non-terminal A'.

b. Replace all productions that start with α:

A → α A' (plus any productions that did not share the prefix)

A' → β₁ | β₂ | ... (the parts after the shared prefix α)

3. Repeat until no two productions share a prefix.

Example — Multi-step Left Factoring

Original grammar:

Example

A → a | a b | a b c | d

Step 1 — Common prefix of first three: a

Example

A → a A' | d

A' → ε | b | b c

Step 2 — A' still has common prefix b:

Example

A' → ε | b A''

A'' → ε | c

Final grammar:

Example

A → a A' | d

A' → ε | b A''

A'' → ε | c

The derivation of "abc":

Example

A → a A' → a b A'' → a b c

The derivation of "a":

Example

A → a A' → a ε = a

Left Factoring vs. Left Recursion Elimination

Students often confuse these two transformations. They are different problems with different solutions.

Concept	Problem	Solution
Left recursion	A non-terminal starts with itself: `A → A α`	Introduce right-recursive helper `A'`
Left factoring	Two productions share a common prefix: `A → α β₁	α β₂`

Left recursion example (needs elimination, not factoring):

Example

E → E + T | T

↑ E starts with E — this is left recursion

Left factoring example (needs factoring, not recursion elimination):

Example

A → a b | a c

↑ both start with 'a' — this is a common prefix

Can a Grammar Need Both?

Yes. A grammar can simultaneously have left recursion AND require left factoring. In that case:

First eliminate left recursion.
Then apply left factoring.

Both must be done before a grammar is suitable for LL(1) parsing.

Worked Example — Complete Transformation

Let's transform a grammar that needs both left recursion elimination and left factoring.

Original grammar:

Example

stmt → stmt ; stmt

| id := expr

| print ( expr )

expr → expr + id

| expr - id

| id

Step 1 — Eliminate left recursion in stmt:

Left-recursive rule: stmt → stmt ; stmt (α = ; stmt) Non-left-recursive: id := expr, print ( expr )

Example

stmt → id := expr stmt'

| print ( expr ) stmt'

stmt' → ; stmt stmt' | ε

Step 2 — Eliminate left recursion in expr:

Left-recursive: expr → expr + id, expr → expr - id (α = + id or - id) Non-left-recursive: expr → id

Example

expr → id expr'

expr' → + id expr'

| - id expr'

| ε

Step 3 — Check for common prefixes in stmt:

stmt → id := expr stmt' and … only the id production starts with id. No factoring needed here.

Final grammar (ready for LL parsing):

Example

stmt → id := expr stmt' | print ( expr ) stmt'

stmt' → ; stmt stmt' | ε

expr → id expr'

expr' → + id expr' | - id expr' | ε

Every production now starts with a different token, so a one-token lookahead is enough.

The Problem — Choosing Between Productions

But what if two productions start with the same symbol?

Example

stmt → if ( expr ) stmt

| if ( expr ) stmt else stmt

Another example:

Example

A → a b c

| a b d

The parser sees a — should it use rule 1 or rule 2? It cannot decide until it sees the third token (c or d). A single-token lookahead is not enough.

Left factoring solves this by pulling out the common prefix into a new rule, so the choice is deferred until after the shared part is consumed.

How Left Factoring Works

Left factoring rewrites productions that share a common prefix. The common prefix becomes one rule, and the differing suffixes become alternatives in a helper non-terminal.

The General Pattern

Before (problem — common prefix α):

Example

A → α β₁

| α β₂

| α β₃

| γ ← this one does not share the prefix

After left factoring:

Example

A → α A' | γ

A' → β₁ | β₂ | β₃

Now when the parser sees the start of α, it uses A → α A'. After consuming α, the lookahead determines which A' production to use.

Example 1 — Simple Case

Original:

Example

A → a b c

| a b d

Common prefix: a b

After left factoring:

Example

A → a b A'

A' → c | d

Now the parser reads a b, then looks at the next token:

If it sees c → use A' → c
If it sees d → use A' → d

One token of lookahead is enough.

Example 2 — The Dangling Else

Original:

Example

stmt → if ( expr ) stmt

| if ( expr ) stmt else stmt

| other

Common prefix: if ( expr ) stmt

After left factoring:

Example

stmt → if ( expr ) stmt stmt'

| other

stmt' → else stmt

| ε

Now:

After parsing if ( expr ) stmt, look at the next token.
If it is else → use stmt' → else stmt
Otherwise → use stmt' → ε (no else branch)

The Left Factoring Algorithm

The algorithm to left-factor a grammar systematically:

Example

For each non-terminal A:

1. Find the longest common prefix α shared by two or more productions of A.

2. If such a prefix exists:

a. Create a new non-terminal A'.

b. Replace all productions that start with α:

A → α A' (plus any productions that did not share the prefix)

A' → β₁ | β₂ | ... (the parts after the shared prefix α)

3. Repeat until no two productions share a prefix.

Example — Multi-step Left Factoring

Original grammar:

Example

A → a | a b | a b c | d

Step 1 — Common prefix of first three: a

Example

A → a A' | d

A' → ε | b | b c

Step 2 — A' still has common prefix b:

Example

A' → ε | b A''

A'' → ε | c

Final grammar:

Example

A → a A' | d

A' → ε | b A''

A'' → ε | c

The derivation of "abc":

Example

A → a A' → a b A'' → a b c

The derivation of "a":

Example

A → a A' → a ε = a

Left Factoring vs. Left Recursion Elimination

Students often confuse these two transformations. They are different problems with different solutions.

Concept	Problem	Solution
Left recursion	A non-terminal starts with itself: `A → A α`	Introduce right-recursive helper `A'`
Left factoring	Two productions share a common prefix: `A → α β₁	α β₂`

Left recursion example (needs elimination, not factoring):

Example

E → E + T | T

↑ E starts with E — this is left recursion

Left factoring example (needs factoring, not recursion elimination):

Example

A → a b | a c

↑ both start with 'a' — this is a common prefix

Can a Grammar Need Both?

Yes. A grammar can simultaneously have left recursion AND require left factoring. In that case:

First eliminate left recursion.
Then apply left factoring.

Both must be done before a grammar is suitable for LL(1) parsing.

Worked Example — Complete Transformation

Let's transform a grammar that needs both left recursion elimination and left factoring.

Original grammar:

Example

stmt → stmt ; stmt

| id := expr

| print ( expr )

expr → expr + id

| expr - id

| id

Step 1 — Eliminate left recursion in stmt:

Left-recursive rule: stmt → stmt ; stmt (α = ; stmt) Non-left-recursive: id := expr, print ( expr )

Example

stmt → id := expr stmt'

| print ( expr ) stmt'

stmt' → ; stmt stmt' | ε

Step 2 — Eliminate left recursion in expr:

Left-recursive: expr → expr + id, expr → expr - id (α = + id or - id) Non-left-recursive: expr → id

Example

expr → id expr'

expr' → + id expr'

| - id expr'

| ε

Step 3 — Check for common prefixes in stmt:

stmt → id := expr stmt' and … only the id production starts with id. No factoring needed here.

Final grammar (ready for LL parsing):

Example

stmt → id := expr stmt' | print ( expr ) stmt'

stmt' → ; stmt stmt' | ε

expr → id expr'

expr' → + id expr' | - id expr' | ε

Every production now starts with a different token, so a one-token lookahead is enough.