12 Jun 2010 20:43:58 +0200

Related articles |
---|

Purple Dragon Book: Newbie questions on Chapter 4 text. simonsharry@gmail.com (Harry) (2010-06-08) |

Re: Purple Dragon Book: Newbie questions on Chapter 4 text. Pidgeot18@verizon.invalid (Joshua Cranmer) (2010-06-09) |

Re: Purple Dragon Book: Newbie questions on Chapter 4 text. felipeangriman@gmail.com (Felipe Angriman) (2010-06-09) |

Re: Purple Dragon Book: Newbie questions on Chapter 4 text. simonsharry@gmail.com (Harry) (2010-06-10) |

Re: Purple Dragon Book: Newbie questions on Chapter 4 text. cdodd@acm.org (Chris Dodd) (2010-06-12) |

Re: Purple Dragon Book: Newbie questions on Chapter 4 text. felipeangriman@gmail.com (Felipe Angriman) (2010-06-13) |

From: | Chris Dodd <cdodd@acm.org> |

Newsgroups: | comp.compilers |

Date: | 12 Jun 2010 20:43:58 +0200 |

Organization: | X-Privat.Org NNTP Server - http://www.x-privat.org |

References: | 10-06-023 |

Keywords: | books, parse |

Posted-Date: | 13 Jun 2010 06:03:41 EDT |

Harry <simonsharry@gmail.com> wrote in news:10-06-023@comp.compilers:

*> Question 2. Page 237, second last para*

*>*

*> [emphasis mine]*

*>*

*> "The use of a stack in shift-reduce parsing is justified by an*

*> important fact: the handle will always eventually appear on top of*

*> the stack, never inside. This fact can be shown by considering the*

*> possible forms of two successive steps in *any* rightmost*

*> derivation. Figure 4.29 illustrates *the two possible* cases."*

*>*

*> [Continued on next page]*

*>*

*> In both cases, after making a reduction the parser had to shift*

*> zero or more symbols to get the next handle onto the stack. It*

*> *never had to* go into the stack to find the handle"*

*>*

*> Now...*

*> a) How did the authors assert that there are only two cases, and not*

*> more?*

The two cases are:

1) the RHS of the rule being expanded contains a non-terminal

2) the RHS of the rule being expanded does not contain a non-terminal

clearly one or the other must apply.

The most confusing thing here is that the Dragon Book always refers to

derivations 'top-down', with the sentence symbol on the left expanding

ultimately to the string of terminals on the right, even when talking about

'bottom up' parsing. So with bottom up parsing, the logical flow of the

algorithm is 'backwards' -- the opposite direction from the derivation arrows

(ie right to left).

*> b) How do we know for sure that "it never had to go into the stack",*

*> since neither are they showing an actual sentence in this example (so*

*> we could verify if did or did not go into the stack), nor are they*

*> using any induction-life proof to establish the stated fact!*

This follows from the fact we're using/getting a rightmost derivation. At

each step in a rightmost derivation (now going in the direction of the

arrows), we expand the rightmost non-terminal in the sentential form. If we

expanded any other, it wouldn't be a rightmost derivation. So at each

reduction in a shift-reduce parse (now going against the arrows) there will

never be any non-terminal symbols after the group of symbols on the top of

the stack we're replacing with a non-terminal (reducing), there will just be

the 'unread' input. I say 'unread' here because we actually may have read k

lookahead symbols for LR(k) -- the point is those lookahead symbols are NOT

on the stack (yet).

*> c) Finally, it is not clear from Figure 4.29 what the dotted and solid*

*> lines mean? Basically, what exactly is being described in this figure?*

Unfortunately I don't have a copy of the purple dragon book handy (only red),

so I'm not sure which figure is 4.29, and the red book doesn't have any

figures with dotted lines around here.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.