Where reductions in LALR?

"tubylerczyk" <tubylerczyk@wp.pl>
3 Sep 2005 15:24:04 -0400

          From comp.compilers

Related articles
Where reductions in LALR? tubylerczyk@wp.pl (tubylerczyk) (2005-09-03)
Re: Where reductions in LALR? schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-09-04)
Re: Where reductions in LALR? 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-09-04)
Re: Where reductions in LALR? cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-09-07)
| List of all articles for this month |

From: "tubylerczyk" <tubylerczyk@wp.pl>
Newsgroups: comp.compilers
Date: 3 Sep 2005 15:24:04 -0400
Organization: http://groups.google.com
Keywords: LALR, question

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


Post a followup to this message

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