Re: Hash specifics

In article <9012122107.aa06454@ICS.UCI.EDU> Ira Baxter <baxter@zola.ICS.UCI.EDU> writes:
> If you have a lexer independent of the parsing mechanism, so that it
> hasn't got any idea whether the next string is a keyword or not
> (assemblers scanning the opcode field violate this requirement), then
> you'll have to do a symbol/string table probe anyway


You can very efficiently decide whether the next input belongs to a given
set of keywords or is an identifier as you read it in using a DFA or some
similar recognizer. Given the wide availability of FLEX, this is the
approach I almost always use -- dodges both the problems of efficient
keyword hashing and separating identifiers from keywords.


I tend to agree with Henry Spencer that on modern machines, "imperfect
hashing" is likely to be good enough -- after all, how many keywords are we
talking about, anyway? A couple hundred, max? Let's just increase the
table size until some really cheap hash function doesn't generate any
collisions. How big a table will we end up with? A couple thousand
entries? That's "only" 8K of pointers on a 32-bit box... An interesting
exercise would be a program which, for a given set of keywords, and a given
table size limit, tried more and more expensive hash functions until the
keywords hashed without collisions into the table and then emitted the
function. Kind of like gperf with less lofty ambitions :-).


Bart Massey
bart@cs.uoregon.edu
--

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