Re: perfect hashing

"Jan Gray" <jsgray@acm.org>
9 Aug 2000 23:57:14 -0400

          From comp.compilers

Related articles
Hashtable alternatives gwynfa@paradise.net.nz (Gwynfa) (2000-07-27)
Re: Hashtable alternatives rkrayhawk@aol.com (2000-08-04)
perfect hashing preston@tera.com (Preston Briggs) (2000-08-04)
Re: perfect hashing ceco@jupiter.com (Tzvetan Mikov) (2000-08-05)
Re: perfect hashing jsgray@acm.org (Jan Gray) (2000-08-09)
Re: perfect hashing jmochel@foliage.com (2000-08-10)
Re: perfect hashing fjh@cs.mu.OZ.AU (2000-08-10)
Re: perfect hashing parz@home.com (Parzival) (2000-08-10)
Re: perfect hashing rick@home.com (2000-08-13)
Re: perfect hashing lars@bearnip.com (Lars Duening) (2000-08-13)
Re: perfect hashing pmk@cray.com (2000-08-13)
[3 later articles]
| List of all articles for this month |
From: "Jan Gray" <jsgray@acm.org>
Newsgroups: comp.compilers
Date: 9 Aug 2000 23:57:14 -0400
Organization: Gray Research LLC
References: 00-07-064 00-08-022 00-08-026 00-08-031
Keywords: lex

"Tzvetan Mikov" <ceco@jupiter.com> wrote in message
> I guess that would be faster, but it seems "cleaner" not to mix the
> reserved words and the symbol table together. Going down this road in
> a C compiler we could even use the same symbol table for preprocessor
> defines as well ( has that been done?). Is that a good idea?


Yes. As I wrote in http://compilers.iecc.com/comparch/article/96-10-103:


> Is scanning/parsing _speed_ ever reason to go toward using a hash
> table for identifying keywords?


Sure. In C like languages, really fast compilation may require an
integrated preprocessor, and since even keywords can be #define'd to
something else, it would be wrong to specifically scan for them as such.
Therefore, the best approach is often to recognise an identifier
([A-Za-z_][A-Za-z_0-9]*), then lookup (perhaps via hash table) several
properties of the identifier:
* is it a macro name? (and perhaps its macro definition)
* is it a keyword? (and its keyword token)
* other useful attributes of the id (id known to be, or definitely not be,
a type name, class name, member name, etc.)


Jan Gray
Redmond, WA


Post a followup to this message

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