|Purple Dragon Book: Newbie questions on Chapter 4 text. firstname.lastname@example.org (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. email@example.com (Felipe Angriman) (2010-06-09)|
|Re: Purple Dragon Book: Newbie questions on Chapter 4 text. firstname.lastname@example.org (Harry) (2010-06-10)|
|Re: Purple Dragon Book: Newbie questions on Chapter 4 text. email@example.com (Chris Dodd) (2010-06-12)|
|Re: Purple Dragon Book: Newbie questions on Chapter 4 text. firstname.lastname@example.org (Felipe Angriman) (2010-06-13)|
|Date:||Tue, 8 Jun 2010 23:16:29 -0700 (PDT)|
|Posted-Date:||09 Jun 2010 19:05:07 EDT|
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.
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)."
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
Question 2. Page 237, second last para
"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"
a) How did the authors assert that there are only two cases, and not
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.
Return to the
Search the comp.compilers archives again.