|Earley... email@example.com (Darius Blasband) (1997-05-22)|
|Re: Earley... firstname.lastname@example.org (1997-05-25)|
|Re: Earley... email@example.com (Philip Lijnzaad) (1997-05-27)|
|Re: Earley... firstname.lastname@example.org (Alan L. Wendt) (1997-05-30)|
|Re: Earley... email@example.com (1997-06-04)|
|From:||firstname.lastname@example.org (Gertjan van Noord)|
|Date:||25 May 1997 13:45:32 -0400|
|Organization:||University of Groningen, Faculty of Arts|
Darius Blasband (email@example.com) 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
dr Gertjan van Noord Alfa-informatica, RUG, Postbus 716, 9700 AS Groningen
firstname.lastname@example.org tel. +31-50-3635935 fax +31-50-3636855
Return to the
Search the comp.compilers archives again.