Re: Algorithms

Joachim Durchholz <joachim_d@gmx.de>
19 Apr 2002 11:26:46 -0400

          From comp.compilers

Related articles
Algorithms ACA99SRV@sheffield.ac.uk (Steve Vernon) (2002-04-10)
Re: Algorithms haberg@matematik.su.se (2002-04-13)
Re: Algorithms joachim_d@gmx.de (Joachim Durchholz) (2002-04-16)
Re: Algorithms rboland@unb.ca (Ralph Boland) (2002-04-17)
Re: Algorithms vmakarov@redhat.com (Vladimir Makarov) (2002-04-17)
Re: Algorithms joachim_d@gmx.de (Joachim Durchholz) (2002-04-19)
| List of all articles for this month |

From: Joachim Durchholz <joachim_d@gmx.de>
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.


Regards,
Joachim--


Post a followup to this message

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