derivations
with w 1 , w 2 ,w 3 ∈ T*, the equality of the k leftmost symbols of w 2 and w 3 implies
y 1 = y 2 , then G is said to be an LL (k) grammar. (If |w 2 | or |w 3 | is less than k, then
k is replaced by the smaller of these.)
The definition makes precise what has already been indicated. If at any stage
in the leftmost derivation (w 1 Ax) we know the next k symbols of the input, the
next step in the derivation is uniquely determined (as expressed by y 1 = y 2 ).
The topic of LL grammars is an important one in the study of compilers. A
number of programming languages can be defined by LL grammars, and many
compilers have been written using LL parsers. But LL grammars are not
sufficiently general to deal with all deterministic context-free languages.
Consequently, there is interest in other, more general deterministic grammars.
Particularly important are the so-called LR grammars, which also allow efficient
parsing, but can be viewed as constructing the derivation tree from the bottom
up. There is a great deal of material on this subject that can be found in books on
compilers (e.g., Hunter 1981) or books specifically devoted to parsing methods
for formal languages (such as Aho and Ullman 1972).
EXERCISES
1. Show that the second grammar in Example 7.13 is an LL grammar and that it
is equivalent to the original grammar.
2. Show that the grammar for L = {w : n a (w) = n b (w)} given in Example 1.13 is
not an LL grammar.
3. Find an LL grammar for the language in Exercise 2.
4. Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
5. Show that any LL grammar is unambiguous.
with w 1 , w 2 ,w 3 ∈ T*, the equality of the k leftmost symbols of w 2 and w 3 implies
y 1 = y 2 , then G is said to be an LL (k) grammar. (If |w 2 | or |w 3 | is less than k, then
k is replaced by the smaller of these.)
The definition makes precise what has already been indicated. If at any stage
in the leftmost derivation (w 1 Ax) we know the next k symbols of the input, the
next step in the derivation is uniquely determined (as expressed by y 1 = y 2 ).
The topic of LL grammars is an important one in the study of compilers. A
number of programming languages can be defined by LL grammars, and many
compilers have been written using LL parsers. But LL grammars are not
sufficiently general to deal with all deterministic context-free languages.
Consequently, there is interest in other, more general deterministic grammars.
Particularly important are the so-called LR grammars, which also allow efficient
parsing, but can be viewed as constructing the derivation tree from the bottom
up. There is a great deal of material on this subject that can be found in books on
compilers (e.g., Hunter 1981) or books specifically devoted to parsing methods
for formal languages (such as Aho and Ullman 1972).
EXERCISES
1. Show that the second grammar in Example 7.13 is an LL grammar and that it
is equivalent to the original grammar.
2. Show that the grammar for L = {w : n a (w) = n b (w)} given in Example 1.13 is
not an LL grammar.
3. Find an LL grammar for the language in Exercise 2.
4. Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
5. Show that any LL grammar is unambiguous.