[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 A

B from a context-free grammar.

Left Recursion Removal

A variable A is left-recursive if it occurs in a production of the form A

Ax for any x

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.