[Overview] [Previous] [Next]

Efficient Parsing

Exhaustive search parsing is, of course, extremely inefficient. It requires time exponential in |w|.

For any context-free grammar G, there are algorithms for parsing strings w is a member of L(G) in time proportional to the cube of |w|. This is still unsatisfactory for practical purposes.

There are ways to further restrict context-free grammars so that strings may be parsed in linear or near-linear time. These restricted grammars are covered in courses in compiler construction, but will not be considered here. All such methods do reduce the power of the grammar, thus limiting the languages that can be recognized. There is no known linear or near-linear algorithm for parsing strings of a general context-free grammar.

Copyright 1996 by David Matuszek
Last modified Mar 3, 1996