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

On 06/09/2010 02:16 AM, Harry wrote:
> 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?


Consider the grammar:
S -> A a
A -> a | epsilon


This language is not LL(1), but it satisfies conditions one and two.


The reason that it's ambiguous is that if First(alpha) intersection
Follow(A) is not empty, we can't tell if that terminal is part of alpha,
and by consequent A, or if A is supposed to evaluate to epsilon and the
terminal be part of Follow(A).


The textbook I had for parsing (Louden's Compiler Construction:
Principles and Practice) gave the following as the rules for LL(1) grammar:
1. For every production A -> alpha_1 | alpha_2 | ... | alpha_n,
First(alpha_i) intersection First(alpha_j) is empty for all i and j,
where 1 <= i, j <= n and i != j.
2. For every nonterminal A such that First(A) contains epsilon, First(A)
intersection Follow(A) is empty.


(These rules immediately follow the rules for constructing a parse table
for LL(1) grammars, so the rationale behind them is more evident.)


(Point of order: what are the rules about using non-ASCII characters in
this newsgroup?)
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

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