[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
all productions save for the single production S.
In this case we can also eliminate any occurrences of S from the right-hand-side
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
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