Re: Earley Parser
6 Oct 2005 15:05:13 -0400

          From comp.compilers

Related articles
[2 earlier articles]
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 |

Newsgroups: comp.compilers
Date: 6 Oct 2005 15:05:13 -0400
Organization: Compilers Central
References: 05-10-005
Keywords: parse
Posted-Date: 06 Oct 2005 15:05:12 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)

You can check Kakuy! at

Kakuy! it's an algorithm animation tool designed to teach Earley's and YCK
parsing techniques. Kakuy! can process all kind of CFG (ambiguous
grammars, epsilon productions, cyclic productions, chain productions) and
generate ALL parse trees (well this is not 100% true in the case of
infinite ambiguous grammars! In this case you can select the max amount of
  trees). You can find a full description of Kakuy! in the post

Probably Kakuy! do not fit your needs (too visual/interactive!). We also
developed a non-intereactive/visual applicantion (ie a command line app)
named Urutaú!. This app implement Earley's algorithm and has the same
capabilities of Kakuy!
The use of Urutaú! is very simple, you must give it the GFG (in Yacc,
BNF,EBNF or plain format) and the input string and it will return (all)
the parse trees coded in a plain file.
To obtain Urutaú! just mail us to Also, if you need some
functionality not yet supported by Urutaú! we will be glad to develop it.

Ah! Kakuy! and Urutaú! are free software.

Best regards

Salvador Valerio Cavadini
Project SEPa!
Facultad de Matemática Aplicada
Universidad Católica de Santiago del Estero (Argentina)

Post a followup to this message

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