Re: Purple Dragon Book: Newbie questions on Chapter 4 text.

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.

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