perfect hashing

The moderator wrote:
[Perfect hashing is sometimes useful for a fixed table of keywords, but
you can't use it for a normal symbol table. -John]


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


If we use perfect hashing for step b, then we'll _always_ find
some entry and have to finish with a string comparison.


E.g., suppose we have the string "preston". We check to see if it's
a keyword. Using perfect hashing, we zip quickly to some entry in
the hash table -- an entry which will contain some keyword --
and then we compare, fail, and proceed to step c.


Alternatively, if we use some sort of conventional hashing,
with a sparse table, we would quickly zip to some entry in the table,
and it would probably be empty, and we could proceed directly to
step c, avoiding the need for the string comparison.


Preston
[I agree. I've fooled around with perfect hash generators, but in practice
it makes more sense to load the keywords into the same symbol table as the
regular symbols so you can look up every text token in one try. -John]

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