Left Factoring & Examples | Compiler Design - Computer Science Engineering (CSE) PDF Download

• Example 1: Remove the left recursion from the production: A ⇒ A α|β
                                                                                           
   
  Applying the transformation yields:

A→ β A ^I
A ^I→ α A ^I | ∈ 
          ­­­
RemAIning part after A
 

Example 2: 
Remove the left recursion from the productions:
E → E + T | T
T→ T * F | F
Applying the transformation yields:
E→ T E^I                                                  T → F T^I
E ^I→ T E^I | ∈                                        T I→ * F T^I ∈

Example 3:
Remove the left recursion from the productions:
E→ E + T | E – T|T
T→ T * F| T/F | F
Applying the transformation yields:
E→ T E^I                           T→ F TI
E→ + T E^I | - T E^I | ∈       T I→ * F T^I | /F T^I | ∈

Example 4: 
Remove the left recursion from the productions:
S→ A a | b
A→ A c | S d | ∈
1. The non terminal S is left recursive because S→ A a→ S d a But it is not immediate left recursive.
2. Substitute S-productions in A→ S d to obtAIn:
A→ A c | A a d | b d | ∈
3. Eliminating the immediate left recursion:
S→ A a | b
A→ b d A^I | A ^I 
A^I→ c A^I | a d A^I |∈

Example 5: 
Consider the following grammar and eliminate left recursion. S → A a | b
                   A → S c | d

The nonterminal S is left recursive in two steps: S → A a → S c a → A a c a → S c a c a - - -

Left recursion causes the parser to loop like this, so remove: Replace A → S c | d by A → A a c | b c | d

and then by using Transformation rules: A → b c A^I | d A^I 
A^I → a c A^I ∈
 

2.5 Left Factoring: Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive parsing.
When it is not clear which of two alternative productions to use to expand a non-terminal A, we may be able to rewrite the productions to defer the decision until we have some enough of the input to make the right choice.

Algorithm: For all A ∈ non-terminal, find the longest prefix a that occurs in two or more right-hand sides of A.

If a ¹ ∈ then replace all of the A productions, A → a bI | a b2 | - - - | a bn | r
With
A → a A^I | r A^I → bI | b2| - - - | bn | ∈ Where, A^I is a new element of non-terminal. Repeat until no common prefixes remAIn.
It is easy to remove common prefixes by left factoring, creating new non-terminal.

For example consider:
V → a b | a r Change to:
V → a V^I V^I → b | r

Example 1:
Eliminate Left factoring in the grammar: S → V := int
V → alpha ‘[‘ int ’]’ | alpha
Becomes:
S → V := int
V → alpha V^I
V^I → ’[‘ int ’] | Î