Re: Algorithms

Ralph Boland <>
17 Apr 2002 23:17:32 -0400

          From comp.compilers

Related articles
Algorithms (Steve Vernon) (2002-04-10)
Re: Algorithms (2002-04-13)
Re: Algorithms (Joachim Durchholz) (2002-04-16)
Re: Algorithms (Ralph Boland) (2002-04-17)
Re: Algorithms (Vladimir Makarov) (2002-04-17)
Re: Algorithms (Joachim Durchholz) (2002-04-19)
Re: Parse Algorithms address@in.sig (John Mapley) (2002-04-24)
| List of all articles for this month |

From: Ralph Boland <>
Newsgroups: comp.compilers
Date: 17 Apr 2002 23:17:32 -0400
Organization: University of New Brunswick
References: 02-04-069 02-04-077 02-04-096
Keywords: parse
Posted-Date: 17 Apr 2002 23:17:32 EDT

Joachim Durchholz wrote:

> Hans Aberg wrote:
> > So it seems that once one steps off the road of deterministic parsers,
> > one should not count on high speed. (This is a theme in Tomita
> > parsers, etc: Trying to make non-deterministic parsers that still are
> > fairly efficient.)
> Two Eiffel compilers use Earley parsers, and they are reasonably fast
> (at least in the parsing stage). I have never looked into these
> parsers, so I can't draw any conclusions from this observation.
> Regards,
> Joachim
> [Earley parsers get slow when they're parsing something ambiguous so they
> have to carry multiple parses. If your language is mostly unambiguous they
> should be OK. It's also my impression that they earned their reputation of
> slowness when computers were a lot slower and had far less memory than they
> have now. -John]

This suggests that the Eiffel language or at least the grammars
defining Eiffel are not LR(1). Is this correct? I would not have
expected that; Eiffelbeing a well thought out and clean language.

If this is so where can I find an Eiffel grammar. I am looking for
grammars that are not LR(1) and preferably strongly not so. I am
developing a parser generator tool for parsing a large class of
difficult grammars and am looking for real life grammars that are
difficult to parse.


Ralph Boland

Post a followup to this message

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