3 Sep 2005 15:24:04 -0400

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) |

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.