For any context-free grammar G, there are algorithms for parsing strings w 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