Left Factoring

It is a process of factoring out the common prefixes of alternatives.

It is used when it is not clear that which of the two alternatives is used to expand the non-terminal.

• Rewrite the production rules without changing the meaning to avoid left factoring

A  → αβ1 / αβ2  ——— (1)

1. 1. A  → αA’
   2. A  → β1 / β2

Rewrite the given expression (1) using the 1 and 2 expressions.

Example:

Consider the grammar and eliminate the left recursion 

E ⟶ E + T / T ——- (1)

T ⟶ T * F / F  ——- (2)

First, let’s take equation (1) and rewrite it using the given formula

E ⟶ E + T / T

E ⟶ T E’          —— (3)

E’ ⟶ +TE’ / Є  —— (4)

Productions 3 and 4 are the Left factoring equations of the given production

T ⟶ T * F / F

T ⟶ FT’        —–(5)

T’ ⟶ FT’ / Є —— (6)

Productions 5 and 6 are the Left factoring equations of the given production

The final productions after left factoring are:

• • E ⟶ T E
  • E’ ⟶ +TE’ / Є
  • T ⟶ FT’
  • T’ ⟶ FT’ / Є

These questions are given as:

1. Eliminate left recursion for the given production
2. Write Left factored grammar

Reference Link

Left Factoring