Hardware Reference
In-Depth Information
symbol table routine just searches the table linearly until it finds a match. This
method is easy to program but is slow, because, on the average, half the table will
have to be searched on each lookup.
Another way to organize the symbol table is to sort it on the symbols and use
the
binary search
algorithm to look up a symbol. This algorithm works by com-
paring the middle entry in the table to the symbol. If the symbol comes before the
middle entry alphabetically, the symbol must be located in the first half of the ta-
ble. If the symbol comes after the middle entry, it must be in the second half of the
table. If the symbol is equal to the middle entry, the search terminates.
Assuming that the middle entry is not equal to the symbol sought, we at least
know which half of the table to look for it in. Binary search can now be applied to
the correct half, which yields either a match, or the correct quarter of the table.
Applying the algorithm recursively, a table of size
n
entries can be searched in
about log
2
n
attempts. Obviously, this way is much faster than searching linearly,
but it requires maintaining the table in sorted order.
A completely different way of simulating an associative memory is a technique
known as
hash coding
or
hashing
. This approach requires having a ''hash'' func-
tion that maps symbols onto integers in the range 0 to
k
1. One possible function
is to multiply the ASCII codes of the characters in the symbols together, ignoring
overflow, and taking the result modulo
k
or dividing it by a prime number. In fact,
almost any function of the input that gives a uniform distribution of the hash values
will do. Symbols can be stored by having a table consisting of
k
buckets
num-
bered 0 to
k
−
1. All the (symbol, value) pairs whose symbol hashes to
i
are stored
on a linked list pointed to by slot
i
in the hash table. With
n
symbols and
k
slots in
the hash table, the average list will have length
n
/
k
. By choosing
k
approximately
equal to
n
, symbols can be located with only about one lookup on the average. By
adjusting
k
we can reduce table size at the expense of slower lookups. Hash cod-
ing is illustrated in Fig. 7-11.
−
Most programs consist of more than one procedure. Compilers and assemblers
generally translate one procedure at a time and put the translated output on disk.
Before the program can be run, all the translated procedures must be found and
linked together properly. If virtual memory is not available, the linked program
must be explicitly loaded into main memory as well. Programs that perform these
functions are called by various names, including
linker
,
linking loader
, and
link-
age editor
. The complete translation of a source program requires two steps, as
shown in Fig. 7-12:
1. Compilation or assembly of the source files.
2. Linking of the object modules.
