Technischer Bericht TR-1991-07

Bibliograph.
Daten
Schöbel, Thomas: A new parsing strategy for context-free grammars.
Universität Stuttgart, Fakultät Informatik, Fakultätsbericht Nr. 1991/07.
10 Seiten, englisch.
CR-Klassif.D.3.4 (Programming Languages Processors)
F.4.2 (Grammars and Other Rewriting Systems)
Kurzfassung

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.

Volltext und
andere Links
HTML (aus PostScript generiert)
Abteilung(en)Universität Stuttgart, Betriebssoftware
Eingabedatum13. Mai 1996
   Publ. Informatik