Technical Report TR-1991-07

BibliographySchöbel, Thomas: A new parsing strategy for context-free grammars.
University of Stuttgart, Faculty of Computer Science, Technical Report No. 1991/07.
10 pages, english.
CR-SchemaD.3.4 (Programming Languages Processors)
F.4.2 (Grammars and Other Rewriting Systems)
Abstract

We present a family of new top-down parsing algorithms for arbitrary context-free grammars based on the notion of a "tree of possible left-derivations". When coded in a special way, this tree can be compressed to a graph. While the time complexity on uniform RAMs is O(n^3) in worst case, we need O(n^2) space. We show that the asymptotic time complexities are equal to Earley's algorithms, and give some arguments to show our algorithm will be better in almost all cases.

Full text and
other links
HTML (generated from PostScript)
Department(s)University of Stuttgart, Betriebssoftware
Entry dateMay 13, 1996
   Publ. Computer Science