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
|
Eingabedatum | 13. Mai 1996 |
---|