The computational complexity of GLR parsing

Mark Johnson

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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
Pages35-42
Number of pages8
ISBN (Electronic)9781461540342
ISBN (Print)9781461368045
DOIs
Publication statusPublished - 1991
Externally publishedYes

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

Cite this