next up previous
Next: Parsing Up: Context-free grammars Previous: Elimination of left recursion

Left factoring

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

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

where

Example 13   Let us consider the following grammar:

S $\displaystyle \longmapsto$ $\displaystyle \bf if$ E $\displaystyle \bf then$ S  |  $\displaystyle \bf if$ E $\displaystyle \bf then$  S $\displaystyle \bf else$ S  |  a
E $\displaystyle \longmapsto$ b
(38)

By left factoring we obtain

S $\displaystyle \longmapsto$ $\displaystyle \bf if$ E $\displaystyle \bf then$ SS'  |  a
S' $\displaystyle \longmapsto$ $\displaystyle \bf else$ S  |  $\displaystyle \varepsilon$
E $\displaystyle \longmapsto$ b
(39)


next up previous
Next: Parsing Up: Context-free grammars Previous: Elimination of left recursion
Marc Moreno Maza
2004-12-02