Java Reference
In-Depth Information
14. Section 5.7 argues that table-driven LL(1) parsers operate in linear time
and space. Explain why this claim does or does not hold for recursive-
descent LL(1) parsers.
15. Explain why the number of nonterminals that can pop from an LL(1)
parse stack is not bounded by a grammar-specific constant.
16. Design an algorithm that computes Predict
k
sets for a CFGs.
17. As discussed in Section 5.5, a grammar is in GNF if all productions are
of the form A
is a string of zero
or more grammar (i.e., terminal or nonterminal) symbols.
Let
G
be a grammar that does not generate
→
a
α
,wherea is a terminal symbol and
α
λ
. Design an algorithm to
transform
G
into GNF.
18. If we construct a GNF version of a grammar using the algorithm de-
veloped in Exercise 17, the resulting grammar is free of left recursion.
However, the resulting grammar can still have common prefixes that
prevent it from being LL(1). If we apply the algorithm presented in
Figure 5.13 of Section 5.5.1, the resulting grammar will be free of left
recursion and common prefixes. Show that the absence of common pre-
fixes and left recursion in an unambiguous grammar does not necessarily
make a grammar LL(1).
19. Section 5.7 andExercises 14 and15 examine the e
ciency of LL(1) parsers.
(a) Analyze the e
ciency of
operating
atable-drivenLL(
k
) parser, as-
suming an LL(
k
) table has already been constructed. Your answer
should be formulated in terms of the length of the parsed input.
(b) Analyze the e
ciency of
constructing
an LL(
k
) parse table. Your
answer should be formulated in terms of the size of the grammar
(the space necessary to represent its vocabularies and productions).
(c) Analyze the e
ciency of operating a recursive-descent LL(
k
)parser.
20. Apply the table compression algorithm in Figure 5.23 to the table shown
in Figure 5.20, presenting rows in the order 1
3. Compare the
success of compression with the result presented in Figure 5.24.
,
5
,
2
,
4
,
