schmidt@glacier.ics.uci.edu (Doug Schmidt) (01/09/89)
Hi,
Does anyone have a complete list of Modula 2 keywords they
would send me please? In return, I'll mail you back a perfect
hash function written in C for recognizing Modula 2 reserved
words in 0(1) time.
thanks,
Doug Schmidt
--
schmidt@ics.uci.edu (ARPA) | Per me si va nella citta' dolente.
office: (714) 856-4043 | Per me si va nell'eterno dolore.
| Per me si va tra la perduta gente.
| Lasciate ogni speranza o voi ch'entrate.schmidt@siam.ics.uci.edu (Doug Schmidt) (01/12/89)
Hi,
Thanks to Frode Odegard, I now have a list of Modula2 reserved words,
and in return, I am distributing the following pair of C routines that
recognize elements of this set of reserved words in O(1) time. The
code was automatically generated, so I'm sure there are a few areas
where a bit of human optimization might be useful. Please let me know
if you've got any suggestions on how to improve the format and/or
optimization.
If you compile reserved.c and test.c together with a C compiler
you'll be able to see how the routine works.
thanks,
Doug Schmidt
------------------------------( reserved.c )------------------------------
#define MIN_WORD_LENGTH 2
#define MAX_WORD_LENGTH 14
#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 95
/*
40 keywords
93 is the maximum key range
*/
static int hash (str, len)
register char *str;
register int len;
{
static int cval[] = {
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 25, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 30, 15, 15, 0, 0,
20, 95, 20, 35, 95, 95, 0, 5, 40, 20,
40, 0, 0, 35, 10, 0, 10, 0, 95, 10,
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 95, 95, 95, 95, 95,
95, 95, 95, 95, 95, 95, 95, 95,
};
register int hval;
switch (hval = len) {
default:
case 4:
hval += cval[str[3]];
case 3:
case 2:
case 1:
hval += cval[str[0]];
hval += cval[str[len - 1]];
case 0:
return (hval);
}
}
int in_word_set (str, len)
register char *str;
register int len;
{
static char * wordlist[] = {
"", "", "",
"END",
"ELSE",
"WHILE",
"", "",
"MOD",
"QUALIFIED",
"",
"MODULE",
"",
"VAR",
"TYPE",
"",
"REPEAT",
"", "",
"CASE",
"", "",
"OR",
"FOR",
"EXIT",
"",
"RECORD",
"BY",
"DO ",
"", "", "",
"TO",
"AND",
"FROM",
"",
"EXPORT",
"", "", "",
"UNTIL",
"",
"OF",
"",
"WITH",
"",
"RETURN",
"",
"SET",
"", "", "", "",
"NOT",
"DIV ",
"", "",
"IF",
"", "",
"ELSIF",
"", "", "",
"PROCEDURE",
"CONST",
"", "", "", "", "",
"IMPORT",
"", "", "",
"ARRAY",
"",
"IN",
"", "", "", "", "", "",
"LOOP",
"DEFINITION",
"",
"POINTER",
"",
"IMPLEMENTATION",
"", "", "", "",
"THEN",
"BEGIN",
};
if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH) {
register int key = hash (str, len);
if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE) {
register char *s = wordlist[key];
return (*s == *str && ! strcmp (str + 1, s + 1));
}
}
return (0);
}
---------------------------------( test.c )----------------------------------------
/*
Tests the generated perfect has function.
The -v option prints diagnostics as to whether a word is in
the set or not. Without -v the program is useful for timing.
*/
#include <stdio.h>
#define MAX_LEN 80
int main ( int argc, char *argv [ ] ) {
int verbose = ( argc > 1 ) ? 1 : 0;
char buf [ MAX_LEN ];
while ( gets ( buf ) ) {
if ( in_word_set ( buf, strlen ( buf ) ) && verbose ) {
printf ( "in word set %s\n", buf );
}
else if ( verbose ) {
printf ( "NOT in word set %s\n", buf );
}
}
return ( 0 );
}
--
schmidt@ics.uci.edu (ARPA) | Per me si va nella citta' dolente.
office: (714) 856-4043 | Per me si va nell'eterno dolore.
| Per me si va tra la perduta gente.
| Lasciate ogni speranza o voi ch'entrate.schmidt@siam.ics.uci.edu (Doug Schmidt) (01/13/89)
Oops, there was a typo in the previous listing, the "DO" was printed
as "DO "! Thanks to Thomas Kaule for pointing this out.
Here's the ``correct'' (hopefully) version:
Doug
----------------------------------------
#define MIN_WORD_LENGTH 2
#define MAX_WORD_LENGTH 14
#define MIN_HASH_VALUE 2
#define MAX_HASH_VALUE 79
/*
40 keywords
78 is the maximum key range
*/
static int hash (str, len)
register char *str;
register int len;
{
static int cval[] = {
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 35, 25, 40, 10, 0,
20, 79, 20, 20, 79, 79, 0, 15, 0, 0,
10, 15, 0, 10, 5, 0, 0, 20, 15, 0,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79,
};
register int hval;
switch (hval = len) {
default:
case 2:
hval += cval[str[1]];
case 1:
hval += cval[str[0]];
hval += cval[str[len - 1]];
case 0:
return (hval);
}
}
int in_word_set (str, len)
register char *str;
register int len;
{
static char * wordlist[] = {
"", "",
"OR",
"",
"ELSE",
"UNTIL",
"RETURN",
"TO",
"NOT",
"TYPE",
"",
"REPEAT",
"DO",
"END",
"LOOP",
"",
"RECORD",
"POINTER",
"SET",
"PROCEDURE",
"DEFINITION",
"MODULE",
"IN",
"FOR",
"EXIT",
"ELSIF",
"EXPORT",
"BY",
"MOD",
"THEN",
"BEGIN",
"", "",
"DIV",
"QUALIFIED",
"", "", "",
"VAR",
"FROM",
"ARRAY",
"",
"OF",
"", "",
"WHILE",
"IMPORT",
"",
"AND",
"IMPLEMENTATION",
"CONST",
"", "", "", "", "", "", "", "", "",
"", "",
"IF",
"",
"WITH",
"", "", "", "", "", "", "", "", "",
"", "", "", "", "",
"CASE",
};
if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH) {
register int key = hash (str, len);
if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE) {
register char *s = wordlist[key];
return (*s == *str && ! strcmp (str + 1, s + 1));
}
}
return (0);
}
--
schmidt@ics.uci.edu (ARPA) | Per me si va nella citta' dolente.
office: (714) 856-4043 | Per me si va nell'eterno dolore.
| Per me si va tra la perduta gente.
| Lasciate ogni speranza o voi ch'entrate.schmidt@siam.ics.uci.edu (Doug Schmidt) (01/13/89)
Hi,
Just for completeness, here is a perfect hash function for Modula 3
keywords! Now there are no more reasons not to build a modula 3 compiler
and donate it to the FSF! ;-).
Doug
p.s. Again, let me know if there are any problems.
----------------------------------------
#define MIN_WORD_LENGTH 2
#define MAX_WORD_LENGTH 9
#define MIN_HASH_VALUE 6
#define MAX_HASH_VALUE 157
/*
53 keywords
152 is the maximum key range
*/
static int hash (str,len)
register char *str;
register int len;
{
static int cval[] = {
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 20, 25, 10, 35, 0,
45, 157, 10, 55, 157, 30, 15, 5, 0, 60,
0, 157, 0, 10, 10, 20, 55, 0, 35, 0,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157, 157, 157,
157, 157, 157, 157, 157, 157, 157, 157,
};
register int hval;
switch (hval = len) {
default:
case 2:
hval += cval[str[1]];
case 1:
hval += cval[str[0]];
hval += cval[str[len - 1]];
case 0:
return (hval);
}
}
int in_word_set (str,len)
register char *str;
register int len;
{
static char * wordlist[] = {
"", "", "", "", "", "",
"RETURN",
"",
"READONLY",
"PROCEDURE",
"", "", "",
"TRY",
"TYPE",
"WHILE",
"REPEAT",
"",
"TYPECASE",
"ELSE",
"", "",
"METHODS",
"SET",
"THEN",
"ARRAY",
"UNSAFE",
"BY",
"", "",
"BEGIN",
"", "", "",
"CASE",
"",
"RAISES",
"",
"END",
"",
"UNTIL",
"RECORD",
"", "",
"EXCEPTION",
"", "", "",
"REF",
"EXIT",
"",
"EXCEPT",
"EXPORTS",
"",
"FROM",
"", "",
"IN",
"AND",
"", "",
"INLINE",
"OR",
"UNTRACED",
"INTERFACE",
"ELSIF",
"", "", "",
"WITH",
"",
"MODULE",
"",
"NOT",
"EVAL",
"",
"IMPORT",
"",
"VAR",
"",
"VALUE",
"", "", "", "",
"CONST",
"", "", "", "", "", "", "", "",
"BITS",
"", "", "", "", "", "",
"OBJECT",
"",
"MOD",
"", "", "",
"FINALLY",
"FOR",
"LOCK",
"", "", "", "", "", "", "", "", "",
"", "", "", "", "", "", "", "", "",
"", "", "", "",
"TO",
"", "", "", "", "", "", "", "", "",
"", "", "", "", "",
"IF",
"DIV",
"", "", "",
"OF",
"", "", "", "",
"DO",
};
if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH) {
register int key = hash (str, len);
if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE) {
register char *s = wordlist[key];
return (*s == *str && ! strcmp (str + 1, s + 1));
}
}
return (0);
}
--
schmidt@ics.uci.edu (ARPA) | Per me si va nella citta' dolente.
office: (714) 856-4043 | Per me si va nell'eterno dolore.
| Per me si va tra la perduta gente.
| Lasciate ogni speranza o voi ch'entrate.