Re: symbol tables and search tries

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
3 Feb 2006 18:40:27 -0500

          From comp.compilers

Related articles
[17 earlier articles]
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-02-02)
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-02-02)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-02)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-02-03)
Re: symbol tables and search tries d148f3wg02@sneakemail.com (Karsten Nyblad) (2006-02-03)
Re: symbol tables and search tries henry@spsystems.net (2006-02-03)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-03)
Re: symbol tables and search tries haberg@math.su.se (2006-02-03)
Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-02-06)
Re: symbol tables and search tries Suif.liyuan@gmail.com (jjyynmb) (2006-02-24)
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:40:27 -0500
Organization: Compilers Central
References: 06-01-117 06-01-120 06-01-132 06-01-139 06-02-012
Keywords: symbols

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


Post a followup to this message

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