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

I will answer partially to the first question with a trivial grammar.


> 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?


Say you have a grammar like this


1. S -> A a
2. A -> a
3. A -> [epsilon]


where [epsilon] is the null string.


Now for Production rule 1 all tree condition are met.
However for Production rule 2 and 3 just condition 1 and 2 are met.


Basically the third condition is stating that the Select-Set(k) with k
= 1 for production rules with the same non terminal must be disjoint.


In the case above the Select-Set(k) with k = 1 for rules 2 and 3 is { a }.


This means that when the parser need to make a choice between
production rule 2 or 3 it will no be able to make such a choice
because the select set are not disjoint.


In this particular case this can be addressed by rewriting the grammar
or by adding lookahead, but that is a thing for a different thread.


HTH,
Felipe

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