Re: Algorithms

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.


Regards,
Joachim--

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