Earley Parser

Tom Gelhausen <gelhausen@ipd.uka.de>
2 Oct 2005 02:48:41 -0400

          From comp.compilers
Related articles
Earley parser aamshukov@cogeco.ca (arthur) (2005-05-01)
Re: Earley parser wyrmwif@tsoft.org (SM Ryan) (2005-05-01)
Re: Earley parser awwaiid@thelackthereof.org (Brock) (2005-05-02)
Re: Earley parser schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-05-02)
Earley parser mefrill@yandex.ru (2005-05-03)
Re: Earley parser angray@beeb.net (Aaron Gray) (2005-05-05)
Earley Parser gelhausen@ipd.uka.de (Tom Gelhausen) (2005-10-02)
Re: Earley Parser vmakarov@redhat.com (Vladimir N. Makarov) (2005-10-03)
Re: Earley Parser scavadini@ucse.edu.ar (2005-10-06)
| List of all articles for this month |
From: Tom Gelhausen <gelhausen@ipd.uka.de>
Newsgroups: comp.compilers
Date: 2 Oct 2005 02:48:41 -0400
Organization: Compilers Central
Keywords: parse, question
Posted-Date: 02 Oct 2005 02:48:41 EDT

Hi all,


I search for a parser with the following features


- a true parser (not just a recognizer)
- processes ALL context free grammars (including epsilon productions,
chain productions, and cyclic productions including those)
- processes ambiguous grammars
- returns ALL parse trees (or a DAG)
- return the parse trees in terms of the original grammar (not a derived
one to cope with the epsilon stuff)
- a really usable implementation (rather an API than an applet
demonstrating the basic technique)


I have been looking around for Earley parsers but did not find an
appropriate one. I read across


Jay Earley, An Efficient Context-Free Parsing Algorithm, 1970
Laszlo Szathmary, Jerly: a Java implementation of Earley's algorithm
Peter Schroeder-Heister, Formale Sprachen und Berechenbarkeit
Grune/Jacobs, Parsing Techniques - A Practical Guide
Aycock/Horspool, Practical Earley Parsing, 2002
James Power, Notes on Formal Language Theory and Parsing


But I (as a parsing noob) could not understand enough to reimplement
the parsing step (unger's method, after recognition). Earley's
proposal is sait to be incorrect in certain situations (Tomita,
1986). Others do not seem to regard (be able to cope with) epsilon
productions or ambique grammars. For Aycock/Horspool's approach i lack
to much background knowledge, I fear. Can anybody help?


Thanks, Tom.


--
Dipl.-Inform. Tom Gelhausen
Institut für Programmstrukturen und Datenorganisation (IPD)
Universität Karlsruhe - Deutschland (Germany)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.