Re: Earley... (Gertjan van Noord)
25 May 1997 13:45:32 -0400

          From comp.compilers

Related articles
Earley... (Darius Blasband) (1997-05-22)
Re: Earley... (1997-05-25)
Re: Earley... (Philip Lijnzaad) (1997-05-27)
Re: Earley... (Alan L. Wendt) (1997-05-30)
Re: Earley... (1997-06-04)
| List of all articles for this month |

From: (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 ( 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 tel. +31-50-3635935 fax +31-50-3636855

Post a followup to this message

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