Tue, 8 Jun 2010 23:16:29 -0700 (PDT)

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: | Harry <simonsharry@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Tue, 8 Jun 2010 23:16:29 -0700 (PDT) |

Organization: | Compilers Central |

Keywords: | books, question |

Posted-Date: | 09 Jun 2010 19:05:07 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.