Re: Looking for symbol table hashing algorithm

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
--

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