Left Factoring | Left Factoring Examples

Definition:

Left factoring is a grammar transformation technique used to eliminate ambiguity in context-free grammars (CFGs). It is primarily applied when a grammar has multiple productions for a non-terminal that share a common prefix. Left factoring refactors the grammar to remove this common prefix, making it more suitable for top-down parsing (such as LL(1) parsers).

Why is Left Factoring Needed?

Top-down parsers (e.g., recursive descent and LL parsers) struggle with ambiguous or left-recursive grammars. Left factoring helps by making the decision-making process for selecting a production deterministic. It allows the parser to determine the correct production by reading a fixed number of symbols ahead.

Left Factoring Process

If a non-terminal has multiple productions with a common prefix, such as:

$$$$A→αβ1∣αβ2∣αβ3∣γ

$$$$

Where:

• $\mathrm{\alpha }$is the common prefix.
• ${\beta }_1,{\beta }_2,{\beta }_3$ are different suffixes.
• $\gamma$ is an alternative production.

We refactor the grammar as:

$$A$$

$$A'$$

​Here, 

$A^{\mathrm{\prime }}$is a new non-terminal that represents the choices after the common prefix $\alpha$.

Example 1: Left Factoring a Grammar

Consider the following grammar:

$$S\to ifEthenSelseS\mathrm{\mid }ifEthenS$$

Here, both productions of $S$ start with if E then S, making it difficult for a top-down parser to decide which production to choose.

Using left factoring, we rewrite it as:

$$S\to ifEthenS{S}^{\mathrm{\prime }}$$

$$S'$$

Now, the parser can decide by first parsing if E then S and then checking whether else S follows.

Example 2: Left Factoring a Simple Grammar

Consider the grammar:

$$A\to ab\mathrm{\mid }ac$$

Here, both productions begin with a. We left-factor it as:

$$A\to a{A}^{\mathrm{\prime }}$$
$$A^{\mathrm{\prime }}\to b\mathrm{\mid }c$$

This refactored grammar ensures that the parser first matches a, then decides between b and c.

Advantages of Left Factoring

1. Removes Ambiguity: Helps in resolving ambiguous choices in top-down parsing.
2. Improves Parsing Efficiency: Enables LL(1) parsing by ensuring that the decision for which production to choose is clear from the first token.
3. Enhances Readability: The grammar becomes more structured and easier to understand.

PRACTICE PROBLEMS BASED ON LEFT FACTORING-

Problem-01: Do left factoring in the following grammar-

S → iEtS / iEtSeS / a

E → b

Solution- 

The left factored grammar is-

S → iEtSS’ / a

S’ → eS / ∈

E → b

 

Problem-02: Do left factoring in the following grammar-

A → aAB / aBc / aAc

 

Solution- 

Step-01: 

A → aA’

A’ → AB / Bc / Ac

Again, this is a grammar with common prefixes.

Step-02: 

A → aA’

A’ → AD / Bc

D → B / c

This is a left factored grammar. 

Problem-03: Do left factoring in the following grammar-

S → bSSaaS / bSSaSb / bSb / a

 Solution-

Step-01: 

S → bSS’ / a

S’ → SaaS / SaSb / b

Again, this is a grammar with common prefixes. 

Step-02: 

S → bSS’ / a

S’ → SaA / b

A → aS / Sb

This is a left factored grammar.

 

Problem-04: Do left factoring in the following grammar-

S → aSSbS / aSaSb / abb / b

Solution- 

Step-01: 

S → aS’ / b

S’ → SSbS / SaSb / bb

Again, this is a grammar with common prefixes. 

Step-02: 

S → aS’ / b

S’ → SA / bb

A → SbS / aSb

This is a left factored grammar.

 

Problem-05: Do left factoring in the following grammar-

S → a / ab / abc / abcd

Solution-

Step-01: 

S → aS’

S’ → b / bc / bcd / ∈

Again, this is a grammar with common prefixes. 

Step-02: 

S → aS’

S’ → bA / ∈

A → c / cd / ∈

Again, this is a grammar with common prefixes. 

Step-03: 

S → aS’

S’ → bA / ∈

A → cB / ∈

B → d / ∈

This is a left factored grammar.

 

Problem-06: Do left factoring in the following grammar-

S → aAd / aB

A → a / ab

B → ccd / ddc

 

Solution- The left factored grammar is-

S → aS’

S’ → Ad / B

A → aA’

A’ → b / ∈

B → ccd / ddc