Java Reference
In-Depth Information
void func
(float,float,float)
z
x
int
f
float
w
int
g
void func(int)
x
float
Current Scope
Outer Scope
Outermost Scope
Figure 8.3: A stack of symbol tables, one per scope
Section 8.3.3 describes this kind of symbol table in greater detail. Such a
symbol table is shown in Figure 8.8 on page 293.
8.3 Basic Implementation Techniques
Any implementation of the interface presented in Section 8.1 must correctly
insert and find symbols. Depending on the number of names that must be
accommodated and other performance considerations, a variety of implemen-
tations is possible. Section 8.3.1 examines some common approaches for orga-
nizing symbols in a symbol table. Section 8.3.2 considers how to represent the
symbol names themselves. Based on this discussion, Section 8.3.3 proposes an
e
cient symbol table implementation.
8.3.1 Entering and Finding Names
We begin by considering various approaches for organizing the symbols in
the symbol table. For each approach, we examine the time needed to insert
symbols, retrieve symbols, andmaintain scopes. These actions are not typically
performed with equal frequency. A name can be declared no more than once
in each scope, but names are typically referencedmultiple times. It is therefore
reasonable to expect that
is called more frequently than the
other methods in our symbol table interface. Thus, we pay particular attention
to the cost of retrieving symbols.
retrieve
S
ymbol
Unordered List
This is the simplest possible storage mechanism. The only data structure
required is an array, with insertions occurring at the next available location. For
added flexibility, a linked list or resizable array avoids the limitations imposed
by a fixed-size array. In this representation,
inserts a name at the
head of the unordered list. The scope name (or depth) is recorded with the
enter
S
ymbol
 
 
Search WWH ::




Custom Search