Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive parsing. Algorithm to left factor a grammar Input: Grammar G Output: An equivalent left factored grammar.
- For each non terminal A find the longest prefix α common to two or more of its alternatives.
- If α!= E,i. e., there is a non trivial common prefix, replace all the A productions
A-> αβ1| αβ2|…………..| αβn| ɣ
where ɣ represents all alternatives that do not begin with α by
A==> α A’| ɣ
A’==>β1|β2|………….|βn
Here A’ is new non terminal. Repeatedly apply this transformation until no two alternatives for a non-terminal have a common prefix.
EX: Perform left factoring on following grammar,
A->xByA | xByAzA | a B->b
Left factored, the grammar becomes
A-> xByAA’ | a A’->zA | Є B-> b