Purple Dragon Book: Newbie questions on Chapter 4 text.

Hello,


I've been reading the "Purple Dragon" book from the beginning lately.
Even though I'm going very slow, and reading word by word, I'm
sometimes unable to fully follow certain sections of the text... even
after repeated attempts on my part. With due respect to the authors, I
sometimes feel that they have not explained things properly or
completely in certain places in the text.


Assuming that many on this forum would have read this text
cover-to-cover (at least once in their lives) without getting stuck
like me, I'd like to seek clarifications and further insights on
things I cannot follow, either fully or partially, going forward. I
promise, I won't be asking for solutions to the exercises, help with
"projects", etc here.


May I?


Question 1. Page 223, last para


        "A grammar G is LL(1) if and only if whenever A -> alpha | beta are
        two distinct productions of G, the following conditions hold:


        1. For no terminal 'a' do both alpha and beta derive strings
              beginning with 'a'.


        2. At most one of alpha and beta can derive the empty string.


        3. If beta *=> epsilon, then alpha does not derive any string
              beginning with a terminal in FOLLOW(A). Likewise, if
              alpha *=> epsilon, then beta does not derive any string beginning
              with a terminal in FOLLOW(A).


                      [Continued on next page]


              The third condition is equivalent to stating that if epsilon is
              in FIRST(beta), then FIRST(alpha) and FOLLOW(A) are disjoint
              sets, and likewise if epsilon is in FIRST(alpha)."


Now...
Why is condition 3 even required for LL(1), is my question. I mean,
why aren't conditions 1 and 2 enough to remove the ambiguity in the
choice of productions which should then allow the parsing process to
continue?


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?


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!


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?


Many thanks in advance for your interest in these newbie questions.


Regards,
/HS

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