Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 (Tek) 9/12/84; site tektronix.UUCP
Path: utzoo!linus!decvax!tektronix!robertd
From: robertd@tektronix.UUCP (Bob Dietrich)
Newsgroups: net.lang.pascal
Subject: Re: Re: Hash function for Pascal keywords?
Message-ID: <4042@tektronix.UUCP>
Date: Fri, 2-Nov-84 16:30:36 EST
Article-I.D.: tektroni.4042
Posted: Fri Nov  2 16:30:36 1984
Date-Received: Sat, 3-Nov-84 21:48:51 EST
References: <2487@dartvax.UUCP> <572@loral.UUCP>
Organization: Tektronix, Beaverton OR
Lines: 37

>    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