The computational complexity of GLR parsing

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


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(n3|G|2) 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).
Original languageEnglish
Title of host publicationGeneralized LR parsing
EditorsMasaru Tomita
Place of PublicationBoston
PublisherSpringer, Springer Nature
Number of pages8
ISBN (Electronic)9781461540342
ISBN (Print)9781461368045
Publication statusPublished - 1991
Externally publishedYes


Dive into the research topics of 'The computational complexity of GLR parsing'. Together they form a unique fingerprint.

Cite this