Re: Earley...

vannoord@let.rug.nl (Gertjan van Noord)
25 May 1997 13:45:32 -0400

          From comp.compilers
Related articles
Earley... darius@phidani.be (Darius Blasband) (1997-05-22)
Re: Earley... vannoord@let.rug.nl (1997-05-25)
Re: Earley... lijnzaad@ebi.ac.uk (Philip Lijnzaad) (1997-05-27)
Re: Earley... alan@ezlink.com (Alan L. Wendt) (1997-05-30)
Re: Earley... clark@quarry.zk3.dec.com (1997-06-04)
| List of all articles for this month |
From: vannoord@let.rug.nl (Gertjan van Noord)
Newsgroups: comp.compilers
Date: 25 May 1997 13:45:32 -0400
Organization: University of Groningen, Faculty of Arts
References: 97-05-252
Keywords: parse

Darius Blasband (darius@phidani.be) wrote:
> Hello !


> I'd be interested in any experience or technical information about
> Earley's parsing algorithm. More specifically:


> - How does one explain the huge difference between the theoretical
> complexity (often linear or quadratic, cubic worst case) and
> the real performance (quite bad, if I recall)


Earley is efficient for _general_ context free grammars, but it is
less efficient then e.g. LR(1) which only deals with a subset of
the context-free grammars.


> - Is it true that (some or all) Eiffel parsers use Earley's
> algorithm ?
> - Is there a yacc-like tool that supports Earley's algorithm, even
> if it does not support semantic actions a la yacc ?
> - Does anyone use it in practice ?


Earley's algorithm and many variations of it are used in natural language
processing, because there one is often interested in languages which are
not LR(k).
--
dr Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
vannoord@let.rug.nl tel. +31-50-3635935 fax +31-50-3636855
http://www.let.rug.nl/~vannoord/
--

Post a followup to this message

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