Re: symbol tables and search tries

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
2 Feb 2006 11:46:03 -0500

          From comp.compilers

Related articles
[13 earlier articles]
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-01-31)
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-01-31)
Re: symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-31)
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)
[1 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 2 Feb 2006 11:46:03 -0500
Organization: Compilers Central
References: 06-01-117 06-01-120 06-01-132 06-01-139
Keywords: symbols, lex

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]



Post a followup to this message

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