[Overview] [Previous] [Next]

Simplifying Context-Free Grammars

The productions of context-free grammars can be coerced into a variety of forms without affecting the expressive power of the grammar.

Empty production removal

If the empty string does not belong to a language, then there is a way to eliminate productions of the form Agoes toempty string from the grammar.

If the empty string does belong to a language, then we can eliminate empty string from all productions save for the single production Sgoes toempty string. In this case we can also eliminate any occurrences of S from the right-hand-side of productions.

Unit production removal

We can eliminate productions of the form Agoes toB from a context-free grammar.

Left Recursion Removal

A variable A is left-recursive if it occurs in a production of the form
Agoes toAx
for any x is a member of (V union T)*. A grammar is left-recursive if it contains at least one left-recursive variable.

Every context-free language can be represented by a grammar that is not left-recursive.


Copyright 1996 by David Matuszek
Last modified Mar 18, 1996