3.3 nursing and Ambiguity 121
(b) Show that this grammar is unambiguous.
- Let G be the context-free grammar with rules
S ---+ AaSbB 1 E, A -+ aA f a, B + bB 1 E.(a) Show that G is ambiguous.
(b) Find an unambiguous context-free grammar equivalent to G.- Consider grammar G with rules
S --+ aAcaa 1 bAbcc, A -+ a 1 ab 1 E.Find the minimum k such that G is a strong LL(k) grammar.
- (a) Show that grammar G3 of Example 3.25(b) is a strong LL(l) gram-
mar.
(b) Does the grammar of Example 3.24(b) satisfy the condition of
Lemma 3.26? Does it satisfy a strong LL(k) condition for any
k > - O? - Modify grammar Gz of Example 3.25 into an equivalent, unambiguous
grammar.
acxl 1 l l l 1 ask by A -+ aA’ and A’ + al 1... 1 cuk, where a E z1 and
WY’*, a/$ E (VUC)‘. P rove the following statements:
(a) Grammar G is ambiguous if and only if the grammar G’ resulted
from a left-factoring operation on G is ambiguous.
(b) If, after a left-factoring operation, a grammar G becomes a strong
LL(k) grammar, then G must be a strong LL(k + 1) grammar. Is
the converse true?- For each of the following context-free grammars, determine whether it
is a strong LL(l) g rammar. If not, find a strong LL( 1) grammar which
is equivalent to it.
(a) S _I) Sl$, S1 --+ uaSlb 1 bb 1 ab.
(b) S+S1$, Sl~aAISlblSlc, A~bAcIE.- Show that the following grammars are
any k > 0, but they are unambiguous.
not strong LL(k) grammars for
(a) S __I) aSb 1 A, A --+ aAc 1 E.
(b) S _I) A 1 B, A -+ uAb I ab, B __I) aBc I UC.