|[2 earlier articles]|
|Re: LR(1) Parser Generator email@example.com (Vladimir Makarov) (2001-07-18)|
|Re: LR(1) Parser Generator firstname.lastname@example.org (Mike Dimmick) (2001-07-18)|
|Re: LR(1) Parser Generator email@example.com (Tim Josling) (2001-07-23)|
|Re: LR(1) Parser Generator firstname.lastname@example.org (2001-07-23)|
|Re: LR(1) Parser Generator email@example.com (David R Tribble) (2001-07-23)|
|Re: LR(1) Parser Generator firstname.lastname@example.org (Mark) (2001-07-23)|
|Re: LR(1) Parser Generator email@example.com (2001-07-30)|
|Re: LR(1) Parser Generator firstname.lastname@example.org (Sönke Kannapinn) (2001-08-02)|
|Re: LR(1) Parser Generator email@example.com (Tim Josling) (2001-08-06)|
|LR(1) Parser Generator firstname.lastname@example.org (2003-04-05)|
|Date:||30 Jul 2001 01:20:40 -0400|
|Organization:||University of California, Riverside|
|References:||01-07-060 01-07-102 01-07-115|
|Posted-Date:||30 Jul 2001 01:20:40 EDT|
Tim Josling <email@example.com> wrote:
: 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
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
Return to the
Search the comp.compilers archives again.