Re: Earley Parser

"Vladimir N. Makarov" <vmakarov@redhat.com>
3 Oct 2005 00:21:50 -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: "Vladimir N. Makarov" <vmakarov@redhat.com>
Newsgroups: comp.compilers
Date: 3 Oct 2005 00:21:50 -0400
Organization: Red Hat, Inc.
References: 05-10-005
Keywords: parse
Posted-Date: 03 Oct 2005 00:21:50 EDT

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).

Post a followup to this message

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