Re: symbol tables and search tries

Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>> In a compiler, successful lookups would be expected to be rather
>> more frequent than insertions...
>
>Yes, but as it was already mentioned in the thread, there might be
>sufficiently more than one table to look up. This brings the rate of
>failures up.


If you've got a bunch of tables to deal with, but no requirement for
prefix search or sorted table dump, one way of getting rid of the O(m)
issues is to hash each input string as part of scanning, and put it into a
single master hash table, whose purpose is to store each distinct string
only once. That makes string equality comparisons O(1) rather than O(m):
you can just compare pointers and never look at the strings themselves.
All the other tables just hold pointers.
--
spsystems.net is temporarily off the air; | Henry Spencer
mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net

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