Problem Solving in Automata, Languages, and Complexity

120 CONTEXT-FREE LANGUAGES

and

where (A + X) and (A --+ y) are two distinct A-rules. This implies that w’

belongs to both LA(A -+ Z) and LA(A -+ y), contradicting the assumption.

cl

The above lemma gives us a sufficient condition for unambiguity. For most
grammars, however, this condition is not easy to check. A simple remedy is
to truncate the lookahead sets to a fixed size.
For any language L and any constant k > - 1, define the operation trunck

bY

~YUP~C~(L) = {x 1 [x E L, 1x1 < - k] or [xy E L for SOme y, 1x1 = k]}*

Denote

LAI,(A) = trunck(LA(A))

LAI,(A + z) = ~~~nc~(LA(A -+ 2)).

We say a context-free grammar G is a strong LL(k) grammar if it satisfies

the following strong LL( k) ~0~~~~~0~: For every nonterminal A in G, the sets

LAk (A -+ c) over all A-rules (A + X) form a partition of LAk (A). It is

clear that the strong LL(k) condition implies the condition given in Lemma

3.26 and, therefore, a strong LL(k) g rammar is unambiguous. Intuitively, a

grammar G is a strong LL(k) g rammar if, in the parsing of a string x to get its

leftmost derivation, we can look at the next k symbols of x to determine which

grammar rule to apply to the leftmost nonterminal in the current sentential

form. This is a simple and yet very useful notion in compiler design.

Example 3.27 Shop that the context-free ~r~rnrn~~ G lath ~uZes

S + aA, A + BA I a, B __) bS 1 cs

is unambiguous.

Proof. Since there is only one S-rule, we have LA1 (S) = LA1 (S + aA). Next,
it is easy to see that the two lookahead sets for B are LA1 (B --+ bS) = {b}
and LA@ + cS) = {c}, and are disjoint. Finally, the two lookahead sets of
A are LAl(A --+ BA) = {b,c} and LAl(A + a) = {a}, and they are disjoint
Therefore, G is a strong LL(1) g rammar and, hence, is unambiguous. cl

Exercise 3.3

1. Let G be the context-free grammar with rules

s ___) usaa 1 B, B -+ bbBcc 1 C, C ---+ bc.

(a) Draw a parse tree for ~3b3c3~6.