Tag: Left Factoring in Compiler Design

Left Factoring | Left Factoring Examples

Compiler Design

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 → αβ1 / αβ2 / αβ3

(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-

 

 

Also Read- Left Recursion

 

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

 

To gain better understanding about Left Factoring,

Watch this Video Lecture

 

Next Article- Relationship With Left Recursion

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Relation between Left Recursion & Left Factoring

Compiler Design

Relationship Between Left Recursion, Left Factoring & Ambiguity-

 

There is no relationship between Left Recursion, Left Factoring and Ambiguity of Grammar.

 

  • All the three concepts are independent and has nothing to do with each other.
  • The presence or absence of left recursion does not impact left factoring and ambiguity anyhow.
  • The presence or absence of left factoring does not impact left recursion and ambiguity anyhow.
  • The presence or absence of ambiguity does not impact left recursion and left factoring anyhow.

 

The following examples support this fact-

 

Example-01: Ambiguous Grammar With Left Factoring-

 

Consider the following grammar-

S → aS / a / ∈

 

Clearly, this grammar has left factoring.

Now, let us draw parse trees for the string w = a-

 

 

Clearly,

  • Two different parse trees exist for the string w = a.
  • Therefore, the grammar is ambiguous.

 

Example-02: Unambiguous Grammar With Left Factoring-

 

Consider the following grammar-

S → aA / aB

A → a

B → b

 

Clearly, this grammar has left factoring.

The language generated by this grammar consists of only two strings L(G) = { aa , ab}.

Now, let us draw parse trees for these strings-

 

 

Clearly,

  • A unique parse tree exists for both the strings.
  • Therefore, the grammar is unambiguous.

 

Example-03: Ambiguous Grammar With Left Recursion-

 

Consider the following grammar-

S → SS / ∈

 

Clearly, this grammar has left recursion.

Now, let us draw parse trees for the string w = ∈-

 

 

Clearly,

  • Infinite parse trees exist for the string w = ∈.
  • Therefore, the grammar is ambiguous.

 

Example-04: Unambiguous Grammar With Left Recursion-

 

Consider the following grammar-

S → Sa / ∈

 

Clearly, this grammar has left recursion.

A unique parse tree exists for all the strings that can be generated from the grammar.

Therefore, the grammar is unambiguous.

 

Example-05: Ambiguous Grammar Without Left Recursion & Without Left Factoring-

 

Consider the following grammar-

S → aA / Ba

A → a

B → a

 

Clearly, this grammar has neither left recursion nor left factoring.

Now, let us draw parse trees for the string w = aa-

 

 

Clearly,

  • Two different parse trees exist for the string w = aa.
  • Therefore, the grammar is ambiguous.

 

Example-06: Unambiguous Grammar With Both Left Recursion & Left Factoring-

 

Consider the following grammar-

S → Sa / ɛ / bB / bD

B → b

D → d

 

Clearly, this grammar has both left recursion and left factoring.

A unique parse tree exists for all the strings that can be generated from the grammar.

Therefore, the grammar is unambiguous.

 

To gain better understanding about relationship between left recursion, left factoring and ambiguity-

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Calculating First and Follow

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.