Java Reference
In-Depth Information
21. Although table-compression is an NP-complete problem, explain why
the following heuristic works well in practice:
Rows are considered in order of decreasing density of non-
default entries. (That is, rows with the greatest number of
nondefault entries are considered first.)
Apply this heuristic to the table shown in Figure 5.20 and describe the
results.
22. A sparse array can be represented as a vector of rows, with each row
represented as a
list
of nondefault column entries. Thus, the nondefault
entry at
T
[
i
,
j
] would appear as an element of list
R
[
i
]. The element
would contain both its column identification (
j
) and the nondefault entry
(
T
[
i
,
j
]).
(a) Express the table shown in Figure 5.20 using this format.
(b) Compare the e
ectiveness of this representation with those given
inSection5.8.Considerboththesavingsinspaceandanyincrease
or decrease in access time.
ff
23. Section 5.9.3 contains an example where the production A
is applied
using an invalid lookahead token. With Follow sets computed globally
for a given grammar, the style of LL(1) parsing described in this chapter
is known as
strong LL
(1). A
full LL
(1) parser applies a production only
if the next input token is valid. Design an algorithm for constructing full
LL(1) parse tables.
Hint:
If a grammar contains
n
occurrences of the nonterminal A,then
consider
splitting
this nonterminal so that each occurrence is a unique
symbol. Thus, A is split into A
1
→λ
A
n
. Each new nonterminal has
productions similar to A, but the context of each nonterminal can di
,
A
2
,...,
ff
er.
24. Consider the following grammar:
1 S
→
V
2
|
W
3 V
→
vAb
4 W
→
wAc
5 A
→ λ
Is this grammar LL(1)? Is the grammar
full
LL(1), as defined in Exer-
cise 23?
