Java Reference
In-Depth Information
6. Design and implement a symbol table using the ordered list data struc-
ture suggested in Section 8.3.1. Discuss the time required to perform
each of the methods defined in Section 8.1.2.
7. Extend the symbol table implementation of Figure 8.7 to include an im-
plementation of
ocally
tests whether
name
is present in the symbol table's current (innermost)
scope. If it is, true is returned. If
name
is in an outer scope, or is not in
the symbol table at all, false is returned.
declared
L
ocally
(
name
). Recall that
declared
L
8. Program a symbol table manager using the interface described in Sec-
tion 8.1.2 and the implementation described in Section Section 8.3.3.
9. Program a symbol table manager using the interface described in Sec-
tion 8.1.2. Maintain the symbol table using red-black trees. Describe the
performance characteristics of this approach.
10. Program a symbol table manager using the interface described in Sec-
tion 8.1.2. Maintain the symbol table using splay trees. Describe the
performance characteristics of this approach.
11. Each string in Figure 8.5 occupies its own space in the string bu
er. Sup-
pose the strings were added in the following order:
i
,
input
,and
putter
.
If the strings could share common characters, then these three strings
could be represented using only 8 character slots. Design a symbol table
string-space manager that allows strings to overlap, retaining the rep-
resentation of each string as an o
ff
ff
set and length pair, as described in
Section 8.3.2.
12. Some languages allow special access to names that are actually su
xes
of complex names. In Java, the classes in the package
java
.
lang
are
available, so that the
java
.
lang
.
Integer
class can be referenced simply as
Integer
. This feature is also available for any explicitly imported classes.
Similarly, Pascal's with statement allows field names to be abbreviated
in the applicable blocks. Design a name space that supports the e
cient
retrieval of such abbreviated names, under the specified conditions. Be
sure to document any changes you wish to make to the symbol table
interface given in Section 8.1.2.
