Re: LR(1) Parser Generator

thp@cs.ucr.edu
30 Jul 2001 01:20:40 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: LR(1) Parser Generator vmakarov@redhat.com (Vladimir Makarov) (2001-07-18)
Re: LR(1) Parser Generator mike@dimmick.demon.co.uk (Mike Dimmick) (2001-07-18)
Re: LR(1) Parser Generator tej@melbpc.org.au (Tim Josling) (2001-07-23)
Re: LR(1) Parser Generator haberg@matematik.su.se (2001-07-23)
Re: LR(1) Parser Generator david@tribble.com (David R Tribble) (2001-07-23)
Re: LR(1) Parser Generator cotemark@globetrotter.net (Mark) (2001-07-23)
Re: LR(1) Parser Generator thp@cs.ucr.edu (2001-07-30)
Re: LR(1) Parser Generator soenke.kannapinn@wincor-nixdorf.com (Sönke Kannapinn) (2001-08-02)
Re: LR(1) Parser Generator tej@melbpc.org.au (Tim Josling) (2001-08-06)
LR(1) Parser Generator pjain@iitk.ac.in (2003-04-05)
| List of all articles for this month |

From: thp@cs.ucr.edu
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 <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


Post a followup to this message

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