Re: perfect hashing

> > Indeed, I wouldn't use it for keywords.
> > Consider the typical scanner.
> >
> > a) Recognize that we have some sort of keyword or identifier
> > b) See if it's a keyword
> > c) If not, look it up in the symbol table
>
> Step a) is done by the lexical analyser, and if the token class
> 'identifier' excludes reserved keywords, or 'identifier's which are
> also keywords are lexed as keywords, then the job of recognizing
> keywords distinct from identifiers is complete in step a. This
> eliminates step b, and avoids a perfect hasher too.


Assuming (c) requires a hash value, if you calculate the hash for all
identifiers in (a) you eliminate the loop overhead of calculating the
hash for (c). That's something like three instructions per character.
My current favorite ASCII-character-at-a-time hash is


    hash = (hash ^ current_character) + ((hash<<26)+(hash>>6));


- Bob Jenkins

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