Re: SLR vs. LALR

Eric Jacobs <mkjacobs@erols.com>
24 Aug 1998 13:33:37 -0400

          From comp.compilers

Related articles
SLR vs. LALR jonasn@diku.dk (Jonas Nielsen) (1998-08-19)
Re: SLR vs. LALR mkjacobs@erols.com (Eric Jacobs) (1998-08-24)
| List of all articles for this month |

From: Eric Jacobs <mkjacobs@erols.com>
Newsgroups: comp.compilers
Date: 24 Aug 1998 13:33:37 -0400
Organization: RCN Internet
References: 98-08-138
Keywords: parse, LALR

Jonas Nielsen wrote:
>
> Which parsers can be generated by a grammar that are not SLR but
> LALR. I am searching for a subset of a grammar for an "existing"
> language. I have once read that the grammar for C++ is not SLR but
> only LALR, but could anyone please list me the subset of the grammar
> where the troubles are, and explain why.


One simple problem that occurs in C (and C++) is the handling
of lvalues and rvalues. An lvalue represents a location in memory,
an rvalue represents the actual value. Any lvalue can be an
rvalue, but an rvalue can't be changed into an lvalue without a
special operator (like *). The problem occurs because SLR can't
decide whether to reduce an lvalue to an rvalue without "looking
ahead" (hence the LA in LALR.)


The dragon book gives this sample grammar:


      S -> L = R
      S -> R
      L -> *R
      L -> id
      R -> L


This grammar is unambiguous, but SLR will generate a shift/reduce
conflict looking at a = after seeing L. It wants to reduce R -> L
and also wants to shift S -> L. = R. However, the reduction is
incorrect because there are no productions that start "R =".
SLR is too simple to realize that.


It should be noted that SLR and LALR are not different parsers
but rather different methods of generating parser tables. The
parser is the same, LR.
--


Post a followup to this message

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