Bibliography | Schö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-Schema | D.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 date | May 13, 1996 |
---|