|Keyword implemetation. firstname.lastname@example.org (Thomas Fjellstrom) (2001-06-28)|
|Re: Keyword implementation. email@example.com (Matthew J. Lockner) (2001-07-01)|
|Re: Keyword implementation. firstname.lastname@example.org (Alex Colvin) (2001-07-02)|
|From:||"Matthew J. Lockner" <email@example.com>|
|Date:||1 Jul 2001 23:44:12 -0400|
|Organization:||University of Northern Iowa|
|Posted-Date:||01 Jul 2001 23:44:12 EDT|
If you're building keyword recognition into the lexer, then the
approach I prefer is to use GNU gperf
(http://www.gnu.org/software/gperf/gperf.html). Its advantages are
manyfold, but I enjoy the laziness of giving the tool a list of
keywords and having it spit out a testing function (identifier
is/isn't in the set).
gperf builds a "minimal perfect" hash function for you. The
documentation has considerable digression on exactly what this means,
but suffice it to say it is a very fast hash function. Of course, the
usual phrase "mileage may vary" most likely applies, and I think code
profiling would be the only good way to reveal whether bsearch can do
better for a given keyword set, etc. I would guess that gperf will
still be less work, though.
My two cents, anyway.
Thomas Fjellstrom wrote:
> In a compiler/translator I've been writing I implemented
> the Reserved/Key words with a sorted table and searched
> using bsearch. I was wondering what every ones preference
> was for implementing keywords? using the symbol table,
> a method just like mine or something else all togeter?
[We discussed minimal perfect hashing at great length some years ago, and
I don't recall that perfect hash functions were all that fast. It seems
to me that on average a separate hash table for keywords will lose compared
to a single combined hash-indexed symbol table, since every non-keyword is
looked up twice with two hashes. -John]
Return to the
Search the comp.compilers archives again.