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)
- A → αA’
- 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:
- Eliminate left recursion for the given production
- Write Left factored grammar
Reference Link