Re: symbol tables and search tries

Henry Spencer wrote:


> >...The hash function evaluation time should be counted as well. The
> >penalty depends on not only n, the table size, but also on m, the token
> >length.
...
> *Any* symbol table, no matter what data structure it uses, will have an
> O(m) component in a successful lookup, for the same reason.


Since every symbol name is extracted from a text file, could we get
any improvement from doing the inevitable O(m) things already in the
lexer?


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?


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]

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