Re: detecting ambiguous grammars

Robert A Duff <world!bobduff@uunet.uu.net>
10 Apr 2001 01:23:31 -0400

          From comp.compilers
Related articles
[14 earlier articles]
Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27)
Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-31)
Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-03-31)
Re: detecting ambiguous grammars kenarose@earthlink.net (Ken Rose) (2001-03-31)
Re: detecting ambiguous grammars vbdis@aol.com (2001-03-31)
Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-04-04)
Re: detecting ambiguous grammars world!bobduff@uunet.uu.net (Robert A Duff) (2001-04-10)
Re: detecting ambiguous grammars ki3084lx@ecs.cmc.osaka-u.ac.jp (Le Harusada) (2005-12-15)
| List of all articles for this month |
From: Robert A Duff <world!bobduff@uunet.uu.net>
Newsgroups: comp.compilers
Date: 10 Apr 2001 01:23:31 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 01-03-126 01-03-185 01-04-013
Keywords: parse, comment
Posted-Date: 10 Apr 2001 01:23:31 EDT

"Joachim Durchholz" <joachim_d@gmx.de> writes:


> Most Eiffel compilers use an Earley parser, which will detect
> ambiguities automatically. The Earleys in these compilers are set up
> to report an error instead of returning all parse trees, that's the
> only difference to the standard algorithm.


I was under the impression that the Earley algorithm is extraordinarily
slow (quadratic or cubic, depending...). Is this not true? Doesn't
matter? Why?


- Bob
[It's reasonably fast when the parse is unambiguous, gets a lot slower
when it has to handle multiple parses due to ambiguity. -John]

Post a followup to this message

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