Left Factoring in Compiler Design: Prefix Rules, Worked Grammars and Exam Traps

A grammar may look simple, yet a predictive parser can get stuck when alternatives such as a b c, a b d and a e all begin with a. The next input symbol does not reveal which production to choose. Left factoring reorganises such alternatives so the parser can consume the shared part first. Left factoring extracts the longest useful common prefix, repeats the transformation to a fixed point, and may still leave the result ambiguous or non-LL(1).

Left factoring and common prefixes: the exact idea

A string x is a prefix of y when y = xz for some string z, which may be empty. The prefixes of a b c are epsilon, a, a b and a b c. The longest common prefix of a b c and a b d is a b. Across a b c, a b d and a e, it is only a.

Suppose a context-free grammar has

A -> alpha beta1 | alpha beta2 | gamma

The alternatives beginning with non-empty alpha form one complete group, while gamma does not begin with it. Rewrite this as:

A -> alpha A' | gamma
A' -> beta1 | beta2

The parser consumes alpha before choosing a suffix, preserving L(A) while changing only grammar shape. This prefix logic also appears in GATE CS exam preparation.

Left factoring worked example: two passes to a fixed point

Start with:

S -> a b c | a b d | a e | f

The first three share a; after it, the first two share b. Extract a:

S -> a X | f
X -> b c | b d | e

Two X alternatives still begin with b, so factor again:

S -> a X | f
X -> b Y | e
Y -> c | d

X and Y are fresh non-terminals. Here e is a terminal, not epsilon.

Derive every terminal string from the result:

S => a X => a b Y => a b c
S => a X => a b Y => a b d
S => a X => a e
S => f

Both grammars generate {a b c, a b d, a e, f}. Factoring postpones choice without changing this set.

Left factoring when one alternative is the whole prefix

If an alternative equals the common prefix, its suffix is empty:

A -> a b | a b c | a b d | x

The a b suffixes are epsilon, c and d. Therefore:

A -> a b R | x
R -> epsilon | c | d

Dropping epsilon would remove a b. Verify all strings:

A => a b R => a b
A => a b R => a b c
A => a b R => a b d
A => x

After a b, $ selects R -> epsilon, c selects R -> c, and d selects R -> d. In a larger grammar, FOLLOW(R) governs epsilon, not automatically $. FIRST and FOLLOW conditions still determine whether the grammar is LL(1).

Left factoring helps predictive choice, but does not guarantee LL(1)

Consider:

Stmt -> id := Expr | id ( Args ) | while ( Cond ) Stmt

Lookahead id matches two alternatives. Factor them:

Stmt -> id Tail | while ( Cond ) Stmt
Tail -> := Expr | ( Args )

After id, the parser uses := or ( to select Tail. This top-down benefit is introduced in Parsing in Compiler Design: Top-Down and Bottom-Up Explained. Bottom-up parsers do not necessarily require the transformation.

This fixes the choice at Stmt, but LL(1) requires disjoint predictive sets everywhere. If two Tail alternatives began with (, further factoring or redesign would be needed. With epsilon, FIRST and FOLLOW conflicts must be absent.

Left factoring traps: longest prefix, left recursion and ambiguity

Test these common claims carefully:

A dangling-else warning:

S -> if E then S else S | if E then S | other

It factors to S -> if E then S S' | other and S' -> else S | epsilon, yet else association can remain ambiguous without another rule or grammar design.

Expand each helper into its caller. Check that every original alternative returns, no suffix vanished, and every non-terminal was rescanned for a common prefix.

Left factoring exam patterns and a reliable solving routine

Typical tasks ask for a longest prefix, an equivalent grammar, helper counts, a missing epsilon, the difference from left-recursion removal, or whether factoring proves LL(1).

Use this four-step routine on the main example:

1. Sort a b c, a b d, a e and f by starting symbol.

2. Group the three a alternatives and extract a into X.

3. Rescan X, then extract b into Y.

4. Stop when no pair under one non-terminal shares a non-empty prefix. Back-expand to recover {a b c, a b d, a e, f}.

For practice, use Context-Free Grammar MCQs: 11 Solved CFG, CFL, PDA. KnowledgeGate has about 3 live practice questions on Left Factoring & Prefixes. This indicates practice depth, not exam frequency.

Left factoring in the short version and the next step

Use this recall ladder:

1. Find alternatives of one non-terminal sharing a non-empty prefix.

2. Extract that prefix into one production.

3. Put suffixes in a fresh non-terminal, including epsilon for an empty suffix.

4. Repeat to a fixed point.

For a self-check, reproduce both passes for S -> a b c | a b d | a e | f, derive all four strings, then factor A -> a b | a b c | a b d | x without losing R -> epsilon.

For Compiler Design sequenced with the CS syllabus, use GATE Guidance by Sanchit Sir. Next, solve both transformations unaided and verify by back-expansion.