Re: Earley Parser

"Vladimir N. Makarov" <>
3 Oct 2005 00:21:50 -0400

          From comp.compilers

Related articles
Earley parser (arthur) (2005-05-01)
Re: Earley parser (SM Ryan) (2005-05-01)
Re: Earley parser (Brock) (2005-05-02)
Re: Earley parser (Sylvain Schmitz) (2005-05-02)
Earley parser (2005-05-03)
Re: Earley parser (Aaron Gray) (2005-05-05)
Earley Parser (Tom Gelhausen) (2005-10-02)
Re: Earley Parser (Vladimir N. Makarov) (2005-10-03)
Re: Earley Parser (2005-10-06)
| List of all articles for this month |

From: "Vladimir N. Makarov" <>
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 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 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.