Algorithm to left factor a grammar

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.

  1. For each non terminal A find the longest prefix α common to two or more of its alternatives.
  2. 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’| ɣ              

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

Leave a Reply