πŸŽ“ Computer Science & Engineering Portal

Master Engineering Disciplines with Structured Notes

Comprehensive academic lecture notes, exam-oriented unit summaries, laboratory manuals, and previous year question papers designed strictly for university students.

πŸ“‘

University Syllabi

AKTU & AICTE aligned semester guidelines.

πŸ“

Exam Question Papers

Previous 5 years solved university papers.

πŸ’‘

Lab Manuals & Viva

Practical codes with outputs & interview Qs.

Core Subjects & Units Hub

Click on any specific unit to immediately view its lecture notes below

Viewing All Lectures

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:

  • Ξ± is the common prefix.
  • Ξ²1,Ξ²2,Ξ²3 are different suffixes.
  • Ξ³ is an alternative production.

We refactor the grammar as:

Aβ†’Ξ±Aβ€²βˆ£Ξ³A 

Aβ€²β†’Ξ²1∣β2∣β3A'

Here, 

Aβ€² 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β†’if E then S else S∣if E then S

Here, both productions of SS 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β†’if E then S Sβ€²

Sβ€²β†’else S∣Ρ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β†’ab∣ac

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

A→aA′
Aβ€²β†’b∣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

 

Labels: ,

Discussion & Queries (<$I18NNumComments$>):

<$CommentPager$>
<$I18NAtCommentTimeWithPermalink$>, <$I18NCommentAuthorSaid$>

<$BlogCommentBody$>

<$BlogCommentDeleteIcon$>
 <$CommentPager$>