Java Reference
In-Depth Information
0 void func(float, float, float)
f
0 void func(int)
g
1 int
w
2 float
1 int
x
z
2 float
Figure 8.4: An ordered list of symbol stacks
name. This allows
to detect if the same name is entered twice
in the same scope, a situation disallowed by most programming languages.
retrieve
enter
S
ymbol
searches for a name from the head of the list toward its tail so
that the closest, active declaration of the name is encountered first. All names
for a given scope appear adjacently in the unordered list. Thus,
S
ymbol
cope
can annotate the list with a marker to show where the new scope begins.
close
open
S
can then delete the currently active symbols at the head of the
list. Although insertion is fast, retrieval of a name from the outermost scope
can require scanning the entire unordered list. This approach is therefore
impractically slow except for the smallest of symbol tables.
S
cope
Ordered List
If a list of
n
distinct names is maintained alphabetically, binary search can
find any name in
O
(
log n
) time. In the unordered list, declarations from the
same scope appear in sequence, an unlikely situation for the ordered list.
How should we organize the ordered list to accommodate declarations of a
name in multiple scopes? Exercise 5 investigates the potential performance of
storing all names in a single, ordered list. Because
accesses
the currently active declaration for a name, a better data structure is an ordered
list of stacks. Each stack represents one currently active name; the stacks are
ordered by their representative names.
retrieve
S
ymbol
locates the appropriate
stack using binary search. The currently active declaration appears on top of
the located stack.
retrieve
S
ymbol
must pop those stacks containing declarations
for the abandoned scope. To facilitate this, each symbol can be recorded along
with its scope name or depth, as established by
close
S
cope
can
then examine each stack in the list and pop those stacks whose top symbol
is declared in the abandoned scope. When a stack becomes empty, it can be
removed from the ordered list. Figure 8.4 shows such a symbol table for the
open
S
cope
.
close
S
cope
