Re: Earley Parser

Tom Gelhausen wrote:
> 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)


The following implementation
http://cocom.sourceforge.net/ammunition-13.html satisfies all your
requirements. Plus:


o it consumes few resources (e.g. parsing 30K lines of C program per
second on 500Mhz P3 machine and consuming 5MB memory to make translation
of 10K lines of C).


o it makes minimal cost error recovery.


o it produces any simple syntax directed translation.


o it can produce translation with the minimal cost when there are more
one of them for ambiguous grammar and we ask only one translation.


o compact representation (using DAG) of all translations when there are
many of them.


        The implementation algorithm is based on Earley's idea but it is
very far away from original Earley's algorithm.


The package (with C and C++ interface) is a part of COCOM toolset
http://cocom.sf.net and distributed under GPL (sorry not LGPL, I spent a
few years to implement the parser and don't want to make it free for
proprietary software).

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