Re: LR(1) Parser Generator

"Mike Dimmick" <mike@dimmick.demon.co.uk>
18 Jul 2001 20:04:35 -0400

          From comp.compilers

Related articles
LR(1) Parser Generator tej@melbpc.org.au (Tim Josling) (2001-07-17)
Re: LR(1) Parser Generator marcov@toad.stack.nl (2001-07-18)
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)
[2 later articles]
| List of all articles for this month |

From: "Mike Dimmick" <mike@dimmick.demon.co.uk>
Newsgroups: comp.compilers
Date: 18 Jul 2001 20:04:35 -0400
Organization: Compilers Central
References: 01-07-060
Keywords: LR(1), parse, LALR
Posted-Date: 18 Jul 2001 20:04:35 EDT

"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.
> Is anyone aware of anything. I do have a pascal implementation
> but I do not like pascal (for no good reason I'm sure) and P2C
> core dumps on the program.
>
> LALR implementations are available but it has to be LR(1).


Why do you say you need full LR(1)? From memory, the difference is
that states with the same core are merged in the LALR(1)
implementation; that is, if two states are identical but for the
lookahead required to resolve the next-state transition, they are
merged.


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?


Bison's user manual (at
http://www.gnu.org/manual/bison/html_chapter/bison_8.html#SEC79) lists
a possible method of resolving these reduce/reduce conflicts.


I would expect that, with sufficient understanding of the Pascal
implementation, and of the Bison source, you might be able to adapt
Bison (or some other open source LALR(1) parser generator) to produce
full LR(1).


> Everyone says LR(1) implementations are too slow or too big but
> those books were written when mainframes has 1mb of 'core'.


True, but full LR(1)s do still frequently have many thousands of states.


I'd like to see more development of adaptive parser generators, which build
only as complex a system as is necessary to parse the language, e.g.


LL(1) [or Parr-style LL^1(k)] for keyword-led productions;
SLR(1), LALR(1), LR(1) for subsets which can be attacked in that manner;
Tomita for really sticky ambiguous problems.


This may be naivety on my part! It's possible that the code required for
the various different state machines would outweigh the possible saving in
state space. Some experimentation would probably be necessary. I don't
really have the skills to write this!


--
Mike Dimmick


Post a followup to this message

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