Re: LR(1) Parser Generator

Tim Josling <tej@melbpc.org.au> wrote:
: 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.


Have you tried to resolve these conflicts by hand by giving priorities
to the rules?


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


Are you sure that your grammar isn't ambiguous?


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


On the order of 20 years ago, I saw a paper that gave an algorithm
that producted LR(1) tables that were not significantly larger than
LALR tables. As I recall, the algorithm split LALR states only when
necessary to avoid R/R conflicts.


: 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 issue isn't parse time, but rather table size and table-generation
time. But you're right: the definition of "big" doubles at Moore's
rate and there have been many doubling periods since the Dragon book
was written.


Tom Payne

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