Re: LR(1) Parser Generator

"Tim Josling" <tej@melbpc.org.au> wrote in message
> I am looking for the source for an LR(1) compiler, preferably
> written in C, and with open source licencing. Google cannot help.
> Is anyone aware of anything. I do have a pascal implementation
> but I do not like pascal (for no good reason I'm sure) and P2C
> core dumps on the program.
>
> LALR implementations are available but it has to be LR(1).


Why do you say you need full LR(1)? From memory, the difference is
that states with the same core are merged in the LALR(1)
implementation; that is, if two states are identical but for the
lookahead required to resolve the next-state transition, they are
merged.


If I remember correctly, this means that shift/reduce conflicts cannot
be introduced by merging states - there's a theorem which states that
if a shift/reduce conflict occurs in the LALR(1) machine, it would
also have done so in the LR(1) machine. I believe however that
artificial reduce/reduce conflicts are possible in LALR(1); is this
happening to you?


Bison's user manual (at
http://www.gnu.org/manual/bison/html_chapter/bison_8.html#SEC79) lists
a possible method of resolving these reduce/reduce conflicts.


I would expect that, with sufficient understanding of the Pascal
implementation, and of the Bison source, you might be able to adapt
Bison (or some other open source LALR(1) parser generator) to produce
full LR(1).


> Everyone says LR(1) implementations are too slow or too big but
> those books were written when mainframes has 1mb of 'core'.


True, but full LR(1)s do still frequently have many thousands of states.


I'd like to see more development of adaptive parser generators, which build
only as complex a system as is necessary to parse the language, e.g.


LL(1) [or Parr-style LL^1(k)] for keyword-led productions;
SLR(1), LALR(1), LR(1) for subsets which can be attacked in that manner;
Tomita for really sticky ambiguous problems.


This may be naivety on my part! It's possible that the code required for
the various different state machines would outweigh the possible saving in
state space. Some experimentation would probably be necessary. I don't
really have the skills to write this!


--
Mike Dimmick

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