Re: symbol tables and search tries

Hans-Peter Diettrich wrote:


> At least it would be possible to calculate an hash code once, for
> subsequent lookup in multiple symbol tables. For tree structures the
> penalty occurs with every table to search, so it might be a good idea
> to use a single global STB, possibly with a scope list added to every
> symbol entry?
>
> DoDi
> [Um, once you calculate the hash codes, what would you call the data
> structure you use to remember the hash codes and the related data for
> subsequent occurrences of the same string in the input text?


E.g. I give the search routine both the string and the hash code, or an
special value (-1) if no hashcode was calculated yet. Once calculated,
the hash code can be propagated to any table search procedure. Finally
the hash code can be stored in the symbol object, for use in the
reorganization of the hash tables.


>
> Re multiple symbol tables, it seems to me there are fairly
> straightforward ways to avoid the cost of multiple lookups, starting
> by using the same string hash in each one. -John]


This was also my idea, but when the bucket lists of the various tables
have different sizes, the modulo of the full hash code can result in
false matches, detectable only by another string comparison. A unique
and sufficiently high list size will be a waste of memory, for many
local scopes, therefore my idea about postponing the separation into
"virtual" tables, attached to every symbol in the common STB; then the
symbol name must be matched only once, followed by an less expensive
match of the (first currently visible...) table in the symbol's table
list.


DoDi

Return to the comp.compilers page.
Search the comp.compilers archives again.