karl@dartvax.UUCP (Karl Berry.) (10/18/84)
In a recent issue of Ada Letters [or was it Sigplan notices?] an article was written giving a hash function/table for Ada* keywords. Does anyone have a similar sort of thing for the Pascal keywords? Failing that, does anyone have a speedy way to be able to decide (a) whether something is a Pascal keyword, and if so, then (b) which it is? dartvax!karl -- karl@dartmouth.csnet
ian@loral.UUCP (Ian Kaplan) (10/20/84)
There is a minimal perfect Hash function for Pascal reserved words.
This is described in
"A Letter Oriented Minimal Perfect Hashing Function"
SigPlan Notices, Sept. 1982, V17, #9
by Curtis R. Cook and R.R. Oldehoeft.
This article describes the hash function and the hash table
organization for a Pascal hash table. Cook et al's algorithm for finding
a perfect hashing function is based on Cichelli's hash function described
in
"Minimal Perfect Hash Functions Made Simple"
CACM Jan. 1980, V21, #1.
by Richard J. Cichelli
While the Cichelli algorithm works for the reserved words in Pascal (and
UCSD Pascal) it fails to find a minimal perfect hash function for the
reserved words in Modula-2.
I modified the algorithm developed by Cook and Oldehoeft so that it
terminates when it can not find a perfect minimal hash table.
Unfortunately I do not have it in UNIX readable form. If you want a
copy send me email and I can US mail you a Xerox of the listing.
The generality of the Cichelli hash function is discussed in
"A Monte Carlo Study of Cichelli Hash-function Solvability"
CACM Nov. 1983, V26, #11 pg. 924.
R. Charles Bell and Bryan Floyd
There is also an article titled
"The Study of an Ordered Minimal Perfect Hashing Scheme",
CACM April 1984, pg. 384,
by C.C. Chang.
Mr. Chang claims to have an algorithm which will find minimal
perfect hashing algorithms without hueristic search (used by the
Cichelli algorithm). I do not understand this algorithm. Perhaps a
wiser head would post a tutorial on how Mr. Chang's algorithm works.
Ian Kaplan
Loral Data Flow Group
Loral Instrumentation
ucbvax!sdcsvax!sdcc6!loral!ianrobertd@tektronix.UUCP (Bob Dietrich) (11/03/84)
> While the Cichelli algorithm works for the reserved words in Pascal (and > UCSD Pascal) it fails to find a minimal perfect hash function for the > reserved words in Modula-2. The keywords 'type' and 'exit' conflict in Modula-2. This is because the hash function used is: hash := val[word[1]] + val[word[length]] + length The hash might be made unique by weighting the value for the first (or last) character in the hash function. Another approach would be to pick other than the first and last characters. > > I modified the algorithm developed by Cook and Oldehoeft so that it > terminates when it can not find a perfect minimal hash table. > Unfortunately I do not have it in UNIX readable form. If you want a > copy send me email and I can US mail you a Xerox of the listing. > > Ian Kaplan I have a machine-readable copy of the program that also rejects conflicts. If there's interest, I'll post it again. Bob Dietrich Tektronix, Inc. (503) 629-1727 {ucb or dec}vax!tektronix!robertd uucp address robertd@tektronix csnet address robertd.tektronix@rand-relay arpa address -- Bob Dietrich Tektronix, Inc. (503) 629-1727 {ucb or dec}vax!tektronix!robertd uucp address robertd@tektronix csnet address robertd.tektronix@rand-relay arpa address