Re: Looking for symbol table hashing algorithm

eodell@pobox.com (Eric O'Dell)
8 Jul 1998 01:34:25 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: Looking for symbol table hashing algorithm drunelson@my-dejanews.com (1998-07-03)
Re: Looking for symbol table hashing algorithm jmccarty@sun1307.spd.dsccc.com (1998-07-03)
Re: Looking for symbol table hashing algorithm zs@cs.mu.OZ.AU (1998-07-05)
Re: Looking for symbol table hashing algorithm chase@naturalbridge.com (David Chase) (1998-07-05)
Re: Looking for symbol table hashing algorithm dietz@interaccess.com (Paul Dietz) (1998-07-05)
Re: Looking for symbol table hashing algorithm khays@sequent.com (1998-07-05)
Re: Looking for symbol table hashing algorithm eodell@pobox.com (1998-07-08)
Re: Looking for symbol table hashing algorithm preston@tera.com (1998-07-08)
Re: Looking for symbol table hashing algorithm drh@microsoft.com (Dave Hanson) (1998-07-08)
Re: Looking for symbol table hashing algorithm smith@aragorn.uni-trier.de (1998-07-10)
Re: Looking for symbol table hashing algorithm scott@basis.com (1998-07-10)
Re: Looking for symbol table hashing algorithm henry@spsystems.net (1998-07-10)
Re: Looking for symbol table hashing algorithm chase@naturalbridge.com (David Chase) (1998-07-10)
[4 later articles]
| List of all articles for this month |

From: eodell@pobox.com (Eric O'Dell)
Newsgroups: comp.compilers
Date: 8 Jul 1998 01:34:25 -0400
Organization: @Home Network
References: 98-07-030
Keywords: symbols

On 3 Jul 1998 00:45:29 -0400, Warwick Irwin
<wal@cosc.canterbury.ac.nz> wrote:


>Can anyone point me to a reference for an industrial-strength hashing
>algorithm suitable for implementing a symbol table in a C++ parser?
>I would like something that has been tuned for large C++ programs.
>
>The parser is itself written in C++, so a C++ implementation would be ideal,
>if such a thing is available.


The algorithm Holub proposes in _Compiler Design in C_ is pretty
workable, and I can't offhand see any reason why you couldn't make a
C++ class out of it. It uses a hash table with individual table
entries linked via linked lists to keep track of scope.


I'm going to echo Kirk Hays, though, and suggest using a balanced tree
instead of a hash if the input is going to be exceptionally large or
generated by another program. Personally, I prefer red-black trees,
since they're fractionally faster than AVL trees, but this may not
matter much in practice. Imatix (www.imatix.com) has a good free C
implementation of an AVL tree in their SFL library.




--Eric
--


Post a followup to this message

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