Re: LR(1) Parser Generator
30 Jul 2001 01:20:40 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: LR(1) Parser Generator (Vladimir Makarov) (2001-07-18)
Re: LR(1) Parser Generator (Mike Dimmick) (2001-07-18)
Re: LR(1) Parser Generator (Tim Josling) (2001-07-23)
Re: LR(1) Parser Generator (2001-07-23)
Re: LR(1) Parser Generator (David R Tribble) (2001-07-23)
Re: LR(1) Parser Generator (Mark) (2001-07-23)
Re: LR(1) Parser Generator (2001-07-30)
Re: LR(1) Parser Generator (Sönke Kannapinn) (2001-08-02)
Re: LR(1) Parser Generator (Tim Josling) (2001-08-06)
LR(1) Parser Generator (2003-04-05)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 30 Jul 2001 01:20:40 -0400
Organization: University of California, Riverside
References: 01-07-060 01-07-102 01-07-115
Keywords: parse, LR(1)
Posted-Date: 30 Jul 2001 01:20:40 EDT

Tim Josling <> 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

Post a followup to this message

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