Efficient Parsing

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.