Java Reference
In-Depth Information
1. The two data structures most commonly used to implement symbol
tables in production compilers are binary search trees and hash tables.
What are the advantages and disadvantages of using each of these data
structures for symbol tables?
2. Consider a program in which the variable is declared as a method's
parameter and as one of the method's local variables. A programming
language includes parameter hiding if the local variable's declaration can
mask the parameter's declaration. Otherwise, the situation described in
this exercise results in a multiply defined symbol. With regard to the
symbol table interface presented in Section 8.1.2, explain the implicit
scope-changing actions that must be taken if the language calls for
(a) parameter hiding
(b) no parameter hiding
3. Describe two alternative approaches to handling multiple scopes in a
symbol table, and list the actions required to open and close a scope for
each alternative. Trace the sequence of actions that would be performed
for each alternative during compilation of the program in Figure 8.1.
4. Figure 8.7 provides code to create a single symbol table for all scopes.
Recalling the discussion of Section 8.2.2, an alternative approach seg-
regates symbols by scope, as shown in Figure 8.3. Modify the code of
Figure 8.7 to manage a stack of symbol tables, one for each active scope.
Retain the symbol table interface as defined in Section 8.1.2.
5. Recalling the discussion of Section 8.3.1, suppose that all active names
are contained in a single, ordered list. An identifier would appear
k
times
in the list if there are currently
k
active scopes that declare the identifier.
(a) How would you implement the methods defined in Section 8.1.2
so that
retrieve
S
ymbol
finds the appropriate declaration of a given
identifier?
(b) Explain why the lookup time does or does not remain
O
(
log n
)for
a list of
n
entries.
