Re: Where reductions in LALR?

tubylerczyk wrote:
> I have sample from "Compilers constructions" by Waite and Goos
> In chapter 7 is grammar LALR(1) but not SLR(1):
> (1) Z -> A
> (2) A -> aBb
> (3) A -> adc
> (4) A -> bBc
> (5) A -> bdd
> (6) B -> d
>
> In book table is:
> a b c d # A B
> -------------------------------
> 0 2 3 . . . 1
> 1 . . . . *
> 2 . . . 5 . 4
> 3 . . . 7 . 6
> 4 8 .
> 5 . +6 9 . .
> 6 . 10
> 7 . . +6 11 .
> 8 +2 +2 +2 +2 +2
> 9 +3 +3 +3 +3 +3
> 10 +4 +4 +4 +4 +4
> 11 +5 +5 +5 +5 +5
>
> number means Shift and Goto, +number means reduction
>
> I generate state set ( * - kernel item)
> 0:
> * Z -> .A
> A -> .aBb
> A -> .adc
> A -> .bBc
> A -> .bdd
>
> 1: (0,A)
> * Z -> A.
>
> 2: (0,a)
> * A -> a.Bb
> * A -> a.dc
> B -> .d
>
> 3: (0,b)
> * A -> b.Bc
> * A -> b.dd
> B -> .d
>
> 4: (2,B)
> * A -> aB.b
>
> 5: (2,d)
> * A -> ad.c
> * B -> d.
>
> 6: (3,B)
> * A -> bB.c
>
> 7: (3,d)
> * A -> bd.d
> * B -> d.
>
> 8: (4,b)
> * A -> aBb.
>
> 9: (5,c)
> * A -> adc.
>
> 10: (6,c)
> * A -> bBc.
>
> 11: (7,d)
> * A -> bdd.
>
> I find lookaheads for
> B->.d in state 2 = {b} => B ->d. in state 5 = {b}
> => reduction in state 5 for b
> B->.d in state 3 = {c} => B->d. in state 7 = {c}
> => reduction in state 7 for c
> It is OK, but...
>
> Lookaheads for Z->.A in state 0 is # - end of stream,
> how will for A->,aBb ? In my opinion also # because
> First(epsilon+#) = #
> This way I find lookaaheads for items in state 8,9,10 and 11
> I find all are #, but in table in book reduction in this state are for
> any terminal symbol, not only end of stream
> What is mean? If lookaheads is # I must reduce for ALL symbols when
> state <> 1 ? Or maybe in state 8,9,10,11 lookaheads are set of all
> symbols? How is would created?
> Note that LALR tables (differs to SLR) often have state with the same
> reduction for all terminal symbols


You are right. The books description is confusing to people not
experienced to LALR parsing. The states 8, 9, 10, and 11 should list
reductions only for #.


Many parser generators include some form of optimizers to reduce the
size of the parsing tables, and one common optimization is to use a
special representation for states in which the only action is to reduce
one production. One such optimization is to introduce a stack and
reduce operation that combines into one operation a normal stack
operation followed by a normal reduce operation. In you example you
could chance the pushing of state 8, 9, 10, and 11 in state 4, 5, 6, and
7 to stack and reduce production 2, 3, 4, or 5, respectively. It seems
to me that Waite and Goos has assumed that the parser generator would
make such an optimization (or something similar), but either failed to
tell the students, or somehow you missed that line.


Karsten Nyblad

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