4 Sep 2005 10:32:47 -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: | Karsten Nyblad <148f3wg02@sneakemail.com> |

Newsgroups: | comp.compilers |

Date: | 4 Sep 2005 10:32:47 -0400 |

Organization: | Compilers Central |

References: | 05-09-016 |

Keywords: | LALR, parse |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.