Re: A Non-LALR(1) Parser Generator

ejy@hrmsc.att.com (Eugene Yurek) writes:


>Charlie Wetherell originally wrote LR along with Shannon for some
>government entity they were either employed for or were working on a
>contract for, so, consequently, the entire source is in the public domain.


Does anybody know if LR is sitting on a server somewhere?


>This generator is not easy to use compared to YACC. You cannot provide
>semantic actions within the grammar. They must be handled in a separate
>source file, and manually tied back to the productions in the BNF (yuk!!).
>Basically, I'm saying that LR works well, however, its not that easy to
>use (though this is a subjective observation on my part). And as I said
>above, you're going to need a Fortran compiler, and some patience to use
>it. It is, however, the only LR(1) parser generator that I've ever come
>across (please, no flames!!!).


Even if it is useless from practical point of view, it would be very
interesting to have a look at the source code. Apparently, also, LR had
excellent output options, since the emphasis, I think, was to accept a
very large class of grammars. Because of this, you could get from LR just
about any diagnostic about your grammar that you could ever hope for.


Since my original article, I have been told this description of the first
of Pager's algorithms:


"Two items with the same lookahead symbol and different
cores should not be put together in a merged state unless
there are already two items in one of the states with those
cores and a common lookahead."


If anybody can make head or tail of this description, they're welcome to
it.


His second algorithm ("strong compatibility") will merge _all_ item sets
which can be merged without introducing a shift-reduce conflict into the
parser, but is apparently computationally expensive. So here's a challenge
for programmers out there: write a parser generator, which has the same
conflict resolving capabilities as YACC, but will parse LR(1) grammars. By
the way, parsers created must be of a reasonable size - i.e. some item set
merging must take place.


While I'm on the subject of parser generators, I heard about an LALR
parser generator written in Sasl the other day. Does anybody know about
this?


Also, have any other parser generators ever been written for LR(1)
grammars (or any other superset of LALR(1) grammars for that matter)? I
know about some algorithms for parsing all context-free grammars, but they
are all either parallel or run in cubic time...


bromage@mullauna.cs.mu.oz.au
--

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