Re: LR(1) Parser Generator

Mike,


Yes I am getting R/R conflicts, or as the bison manual calls them
'mysterious reduce reduce conflicts'. I then have to try and work
out what is causing them and add some extra bits to the grammar.
Normally this involves flattening out the grammar and duplicating
large slabs of it. Alternatively I have to accept some generic
common grammar and hard code checking to make sure they did not
use the wrong constructs in the wrong places.


I am pretty confident the conflicts are spurious, and that LR(1)
will fix the problem.


If all else fails I will write an LR(1) patch for bison and
report the results here. Unfortunately bison is very tersely
documented.


According to my benchmarks the parse is only 5% of gcc
compilation time, so even a 40% increase would not be a big deal
especially given that I would be spending less time scratching my
head about mysterious conflicts and more time developing my
compiler. The dragon book also mentions the 5% figure.


The stats about LALR being smaller than LR are based on the
assumption that the grammar is LALR to start with. If you have to
add hacks to shoehorn it into LALR then the difference would be
smaller though still significant.


Also if you just use a hash table for the parse table the logic
will actually be a lot simpler - no need for 'check tables' etc
etc. That is the LALR parser has various space/time tradeoffs
that slow it down and this can also be balanced against the time
taken for hashing. The hashing can actually be pretty simple. The
key is just state+symbol which is easily hashed by divide by
constant prime. And good compilers convert constant divides into
less expensive operations.


Tim Josling


Mike Dimmick wrote:
>
> "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.
> ...
> 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?

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