Skip to main content

Elimination of Left Factoring

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

 

Comments

Popular posts from this blog

Code Optimization | Code Optimization Techniques

Code Optimization- Code Optimization is an approach to enhance the performance of the code. The process of code optimization involves- Eliminating the unwanted code lines Rearranging the statements of the code Advantages- The optimized code has the following advantages- Optimized code has faster execution speed. Optimized code utilizes the memory efficiently. Optimized code gives better performance. Code Optimization Techniques- Important code optimization techniques are- Compile Time Evaluation Common sub-expression elimination Dead Code Elimination Code Movement Strength Reduction 1. Compile Time Evaluation- Two techniques that falls under compile time evaluation are- A) Constant Folding- In this technique, As the name suggests, it involves folding the constants. The expressions that contain the operands having constant values at compile time are evaluated. Those express