Re: SLR vs. 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.
--

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