The computational complexity of GLR parsing

The Tomita parsing algorithm adapts Knuth’s (1967) well-known parsing algorithm for LR(K) grammars to non-LR grammars, including ambiguous grammars. Knuth’s algorithm is provably efficient: it requires at most O(n|G|) units of time, where \G\ is the size of (i.e. the number of symbols in) G and n is the length of the string to be parsed. This is often significantly better than the O(n³|G|²) worst case time required by standard parsing algorithms such as the Earley algorithm. Since the Tomita algorithm is closely related to Knuth’s algorithm, one might expect that it too is provably more efficient than the Earley algorithm, especially as actual computational implementations of Tomita’s algorithm outperform implementations of the Earley algorithm (Tomita 1986, 1987).