Example 7.12
The grammar
is not an s-grammar, but it is an LL grammar. In order to determine which
production is to be applied, we look at two consecutive symbols of the input
string. If the first is an a and the second a b, we must apply the production S →
ab. Otherwise, the rule S → aSb must be used.
We say that a grammar is an LL (k) grammar if we can uniquely identify the
correct production, given the currently scanned symbol and a “look-ahead” of
the next k − 1 symbols. Example 7.12 is an example of an LL (2) grammar.
Example 7.13
The grammar
generates the positive closure of the language in Example 7.12. As remarked in
Example 5.4, this is the language of properly nested parenthesis structures. The
grammar is not an LL (k) grammar for any k.
To see why this is so, look at the derivation of strings of length greater than
two. To start, we have available two possible productions S → SS and S → aSb.
The scanned symbol does not tell us which is the right one. Suppose we now use
a look-ahead and consider the first two symbols, finding that they are aa. Does
this allow us to make the right decision? The answer is still no, since what we
have seen could be a prefix of a number of strings, including both aabb or
aabbab. In the first case, we must start with S → aSb, while in the second it is
The grammar
is not an s-grammar, but it is an LL grammar. In order to determine which
production is to be applied, we look at two consecutive symbols of the input
string. If the first is an a and the second a b, we must apply the production S →
ab. Otherwise, the rule S → aSb must be used.
We say that a grammar is an LL (k) grammar if we can uniquely identify the
correct production, given the currently scanned symbol and a “look-ahead” of
the next k − 1 symbols. Example 7.12 is an example of an LL (2) grammar.
Example 7.13
The grammar
generates the positive closure of the language in Example 7.12. As remarked in
Example 5.4, this is the language of properly nested parenthesis structures. The
grammar is not an LL (k) grammar for any k.
To see why this is so, look at the derivation of strings of length greater than
two. To start, we have available two possible productions S → SS and S → aSb.
The scanned symbol does not tell us which is the right one. Suppose we now use
a look-ahead and consider the first two symbols, finding that they are aa. Does
this allow us to make the right decision? The answer is still no, since what we
have seen could be a prefix of a number of strings, including both aabb or
aabbab. In the first case, we must start with S → aSb, while in the second it is