3.3 Parsing and Ambiguity 119
analysis of context-free grammars. We delay it until Secion 3.5 (see Example
3.54).
Lookahead Sets. In general, it is difficult to determine whether a given
context-free grammar is ambiguous or not. Indeed, this problem is undecid-
all context-free grammars (see Example 5.47). In the following, we present
a sufficient condition for the unambiguity of a context-free grammar. This
condition is based on the depth-first top-down parsing algorithm of Example
3.22.
Let G = (V,E,R,S) b e a context-free grammar. We write QI! & j3 to
L
denote that the leftmost derivation from a sentential form a to a sentential
form /3. For any nonterminal A, we say a rule A + x is an A-rule. We define
the Zookuhead set of nonterminal A as
```
LA(A) = {u) E X* 1 S & uAv & uw E C*, for some U,V f (VU C)*).
L L
```
That is, if we have reached, in a leftmost derivation, a sentential form a whose
leftmost nontermial is A, then the suffixes of all sentences that can be derived
from CX, starting from symbol A, are in the lookahead set of A. For each A-rule
A + x in R, the lo&ahead set of the rule A -+ x is defined by
##### = {w E IiS* 1 S =G uAv ===+ uxv & uw E C*, for some U,V E (VuC)*}.
```
L L L
```
Suppose A -+ ~1, A + x2,. l
Then, it is easy to see that
```
0, A + xk are all the A-rules in grammar G.
```
```
k
LA(A) = u LA(A -+ xi).
i=l
```
Lemma 3.26 A context-free ~rummur G is ~nurnb~~~~~s ifi fur every non-
~errni~u~ A, the sets LA(A --+ x) over ull Aar~les A + x ~urrn a ~urt~ti~~ of
LA(A), chum is, if LA(A -+ z) n LA(A + y) = 8 for any two ~is~i~c~ A-rules
(A+x) und(A+y).
Proof. For the sake of contradiction, suppose that G is ambiguous. Then,
there exists a string w E X* such that S $ w has two leftmost derivations.
Since the two leftmost derivations start with the same sentential form S,
there exists a sentential form uAv, with u c C*, such that the two leftmost
derivations are identical from S to uAv but different at the next derivation
step. That is, the two leftmost derivations are of the form