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" Newsgroups: comp.compilers Date: 3 Sep 2005 15:24:04 -0400 Organization: http://groups.google.com Keywords: LALR, question Posted-Date: 03 Sep 2005 15:24:04 EDT

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
(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 -> .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)
* B -> d.

6: (3,B)
* A -> bB.c

7: (3,d)
* A -> bd.d
* B -> d.

8: (4,b)
* A -> aBb.

9: (5,c)

10: (6,c)
* A -> bBc.

11: (7,d)
* A -> bdd.

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