[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 A
from the grammar.
If the empty string *does* belong to a language, then we can eliminate
from
all productions save for the single production S.
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 AB
from a context-free grammar.
## Left Recursion Removal

A variable A is *left-recursive* if it occurs in a production
of the form
AAx
for any x (V
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