Left Factoring | Left Factoring Examples

Grammar With Common Prefixes-

 

If RHS of more than one production starts with the same symbol, then such a grammar is called as Grammar With Common Prefixes.

 

Example-

 

A → αβ₁ / αβ₂ / αβ₃

(Grammar with common prefixes)

 

• This kind of grammar creates a problematic situation for Top down parsers.
• Top down parsers can not decide which production must be chosen to parse the string in hand.

To remove this confusion, we use left factoring.

 

Left Factoring-

 

Left factoring is a process by which the grammar with common prefixes is transformed to make it useful for Top down parsers.

 

How?

 

In left factoring,

• We make one production for each common prefixes.
• The common prefix may be a terminal or a non-terminal or a combination of both.
• Rest of the derivation is added by new productions.

 

The grammar obtained after the process of left factoring is called as Left Factored Grammar.

 

Example-

 

 

 

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