Is Minimal Perfect Hashing the wrong algorithm?

>[I just stick the keywords in the symbol table so with one probe I've got
>whatever it is. I thought that was what everyone did. -John]


Nope. There's this whole group of people out there who use "minimal
perfect hashing" to distinguish keywords from each other and from
other identifiers. They maintain a small hash table with their 50 (or
whatever) keywords stuck in it. When the lexer comes up with an
alphabetic string, they first look in the keyword hash table. If that
lookup fails, then they know they've got an identifier and add it to
the symbol table.


Consider the original message:
>Many compiler writers use Minimal Perfect Hashing to generate some
>hash tables such as a key word table.
>But this algorithm minimizes table size.


I think it's sort of a dumb way to go, as I argued in my previous post.


Other people do like John suggests. Still other people (e.g., Fraser
and Hanson) build a small, hard-coded tree to distinguish keywords as
part of the lexer. That way they avoid any lookups at all for
keywords.


Preston Briggs
--

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