Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!wuarchive!emory!att!att!ima!iecc!compilers-sender From: bart@cs.uoregon.edu (Barton Christopher Massey) Newsgroups: comp.compilers Subject: Re: Hash specifics Keywords: design Message-ID: <1990Dec13.201211.6483@cs.uoregon.edu> Date: 13 Dec 90 20:12:11 GMT References: <1990Dec12.221425.569@zoo.toronto.edu> <9012122107.aa06454@ICS.UCI.EDU> Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: bart@cs.uoregon.edu (Barton Christopher Massey) Organization: Department of Computer Science, University of Oregon Lines: 28 Approved: compilers@iecc.cambridge.ma.us In article <9012122107.aa06454@ICS.UCI.EDU> Ira Baxter 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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.