Java Reference
In-Depth Information
Depth records the nesting depth of a symbol. It is useful in checking if a
symbol at a given nesting level is already entered.
There are two index structures for the symbol table: a hash table and a
scope display . The hash table allows e
cient lookup and entry of names, as
described in Section 8.3.1. The scope display maintains a list of symbols that
are declared at the same level. In particular, the i th entry of the scope display
references a list of symbols currently active at scope depth i . Such symbols are
linked by their level field. Moreover, each active symbol's var field is essentially
a stack of declarations for the associated variable.
Figure 8.7 shows the pseudocode for this symbol table implementation.
Figure 8.8 shows the table that results from applying this implementation to
the example in Figure 8.1, at the point where method f is invoked. Figure 8.8
assumes the following unlikely situation with respect to the hash function:
f and g hash to the same location.
w and z hash to the same location.
All symbols are clustered in the same part of the table.
The code in Figure 8.7 relies on the following methods:
delete
( sym ) removes the symbol table entry sym from the collision chain
found at HashTable .
( sym . name ). The symbol is not destroyed—it is
simply removed from the collision chain. In particular, its var and level
fields remain intact.
get
add
( sym ) adds the symbol sym to the collision chainat HashTable .
get
( sym . name ).
Prior to the call to
add
, there is no entry in the table for sym .
is invoked to abandon the currently active scope, each
symbol in the scope is visited by the loop at Marker 3 .Eachsuchsymbolis
removed from the hash table at Marker 4 . If an outer scope definition exists
for the symbol, then the definition is inserted into the hash table at Marker 5 .
Thus, the var field serves to maintain a stack of active scope declarations for
each symbol. The level field allows
When
close
S
cope
close
S
cope
to operate in time proportional
to the number of symbols a
ected by abandoning the current scope. Amortized
over all symbols, this adds a constant overhead to the management of each
declared symbol.
retrieve
ff
examines a collision chain to find the desired symbol. The
loop at Marker 6 accesses all symbols that hash to the same table location,
that is the chain that should contain the desired name. The code at Marker 7
follows the entries' hash fields until the chain is exhausted or the symbol is
located. A properly managed hash table should have very short collision
S
ymbol
 
Search WWH ::




Custom Search