necessary to use S → SS. The grammar is therefore not an LL (2) grammar. In a
similar fashion, we can see that no matter how many look-ahead symbols we
have, there are always some situations that cannot be resolved.
This observation about the grammar does not imply that the language is not
deterministic or that no LL grammar for it exists. We can find an LL grammar for
the language if we analyze the reason for the failure of the original grammar.
The difficulty lies in the fact that we cannot predict how many repetitions of the
basic pattern a n b n there are until we get to the end of the string, yet the grammar
requires an immediate decision. Rewriting the grammar avoids this difficulty.
The grammar
is an LL-grammar nearly equivalent to the original grammar.
To see this, consider the leftmost derivation of w = abab. Then
We see that we never have any choice. When the input symbol examined is a, we
must use S → aSbS, when the symbol is b or we are at the end of the string, we
must use S → λ.
But the problem is not yet completely solved because the new grammar can
generate the empty string. We fix this by introducing a new start variable S o and
a production to ensure that some nonempty string is generated. The final result
is then an LL-grammar equivalent to the original grammar.
While this informal description of LL grammars is adequate for
understanding simple examples, we need a more precise definition if any
rigorous results are to be developed. We conclude our discussion with such a
definition.
Definition 7.5
Let G = (V, T, S, P) be a context-free grammar. If for every pair of leftmost
similar fashion, we can see that no matter how many look-ahead symbols we
have, there are always some situations that cannot be resolved.
This observation about the grammar does not imply that the language is not
deterministic or that no LL grammar for it exists. We can find an LL grammar for
the language if we analyze the reason for the failure of the original grammar.
The difficulty lies in the fact that we cannot predict how many repetitions of the
basic pattern a n b n there are until we get to the end of the string, yet the grammar
requires an immediate decision. Rewriting the grammar avoids this difficulty.
The grammar
is an LL-grammar nearly equivalent to the original grammar.
To see this, consider the leftmost derivation of w = abab. Then
We see that we never have any choice. When the input symbol examined is a, we
must use S → aSbS, when the symbol is b or we are at the end of the string, we
must use S → λ.
But the problem is not yet completely solved because the new grammar can
generate the empty string. We fix this by introducing a new start variable S o and
a production to ensure that some nonempty string is generated. The final result
is then an LL-grammar equivalent to the original grammar.
While this informal description of LL grammars is adequate for
understanding simple examples, we need a more precise definition if any
rigorous results are to be developed. We conclude our discussion with such a
definition.
Definition 7.5
Let G = (V, T, S, P) be a context-free grammar. If for every pair of leftmost