Hash function for Pascal keywords?

Thread View: net.lang.pascal

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by Karl Berry. Thu, 18 Oct 1984 16:54

#104

Author: Karl Berry.
Date: Thu, 18 Oct 1984 16:54

9 lines
876 bytes

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

Re: Hash function for Pascal keywords?

#106

Author: Ian Kaplan
Date: Sat, 20 Oct 1984 01:40

47 lines
2453 bytes

   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!ian

Re: Re: Hash function for Pascal keywords?

#113

Author: Bob Dietrich
Date: Fri, 02 Nov 1984 21:30

37 lines
2317 bytes

>    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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads