Re: Earley Parser

scavadini@ucse.edu.ar
6 Oct 2005 15:05:13 -0400

          From comp.compilers

Related articles
[2 earlier articles]
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: scavadini@ucse.edu.ar
Newsgroups: comp.compilers
Date: 6 Oct 2005 15:05:13 -0400
Organization: Compilers Central
References: 05-10-005
Keywords: parse

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


www.ucse.edu.ar/fma/sepa


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


http://compilers.iecc.com/comparch/article/04-12-074


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 sepa@ucse.edu.ar. 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)
web: http://www.ucse.edu.ar/fma/staff/svcavadini


Post a followup to this message

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