SPPF-Style Parsing From Earley Recognisers. / Scott, Elizabeth.

In: Electronic Notes in Theoretical Computer Science, Vol. 203, No. 2, 04.2008, p. 53-67.

Research output: Contribution to journalArticlepeer-review



In its recogniser form, Earley's algorithm for testing whether a string can be derived from a grammar is worst case cubic on general context free grammars (CFG). Earley gave an outline of a method for turning his recognisers into parsers, but it turns out that this method is incorrect. Tomita's GLR parser returns a shared packed parse forest (SPPF) representation of all derivations of a given string from a given CFG but is worst case unbounded polynomial order. We have given a modified worst-case cubic version, the BRNGLR algorithm, that, for any string and any CFG, returns a binarised SPPF representation of all possible derivations of a given string. In this paper we apply similar techniques to develop two versions of an Earley parsing algorithm that, in worst-case cubic time, return an SPPF representation of all derivations of a given string from a given CFG.
Original languageEnglish
Pages (from-to)53-67
JournalElectronic Notes in Theoretical Computer Science
Issue number2
Publication statusPublished - Apr 2008
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 1178008