Left factoring

Left factoring is another useful grammar transformation used in parsing. The general ideal is to replace the productions

$$\longmapsto \alpha \beta_{{1}}^{{}} \alpha \beta_{{n}}^{{}} \gamma \left\{\vphantom{ \begin{array}{lll} A & \longmapsto & {\alpha} A... ...gmapsto & {\beta}_1 \ \mid \ \cdots \ \mid \ {\beta}_n \\ \end{array} }\right. \begin{array}{lll} A & \longmapsto & {\alpha} A' \ \mid \ {\gamma... ...A' & \longmapsto & {\beta}_1 \ \mid \ \cdots \ \mid \ {\beta}_n \\ \end{array}$$ (37)

where

• A, A' are nonterminals,
• $\alpha$,$\beta_{{1}}^{{}}$,...,$\beta_{{n}}^{{}}$ are strings of symbols with $\alpha$ $\neq$ $\varepsilon$,
• $\gamma$ represents all alternatives for A-productions that do not start with $\alpha$.

Example 13   Let us consider the following grammar:

S	$$\longmapsto$$	$$\bf if$$ E $$\bf then$$ S  |  $$\bf if$$ E $$\bf then$$  S $$\bf else$$ S  |  a
E	$$\longmapsto$$	b

(38)

By left factoring we obtain

S	$$\longmapsto$$	$$\bf if$$ E $$\bf then$$ SS'  |  a
S'	$$\longmapsto$$	$$\bf else$$ S  |  $$\varepsilon$$
E	$$\longmapsto$$	b

(39)