Re: Algorithms

Joachim Durchholz <>
19 Apr 2002 11:26:46 -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)
| List of all articles for this month |

From: Joachim Durchholz <>
Newsgroups: comp.compilers
Date: 19 Apr 2002 11:26:46 -0400
Organization: Compilers Central
References: 02-04-069 02-04-077 02-04-096 02-04-102
Keywords: parse
Posted-Date: 19 Apr 2002 11:26:46 EDT

Ralph Boland wrote:
> Joachim Durchholz wrote:
>>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.
>>[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.

Eiffel is indeed mostly unambiguous.

> This suggests that the Eiffel language or at least the grammars
> defining Eiffel are not LR(1). Is this correct?

I think there should be an LALR(1) grammar for Eiffel, but I haven't
looked into that (you may want to ask the SmallEiffel or Object Tools
guys about the Eiffel grammars that they use). Anyway, Eiffel's
language definition uses a grammar that's not LR, and there's a rule
that says that you can omit semicolons if the parse stays
unambigous. Under such circumstances, Earley parsing is probably the
best way to do.

> 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.

One is in the Eiffel reference ("Eiffel - the Language").
You could also ask in comp.lang.eiffel, there used to be an HTMLized one
somewhere in the WWW.

> 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.

I'm not sure whether Eiffel matches your definition of "difficult
grammar". It's certainly an interesting case on the borderline between
LR grammars and general context-free grammars.


Post a followup to this message

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