Execution Log
keys_file = 'reserved_words.txt'
Reading table from file `reserved_words.txt' to extract keys.
Reader options:
comment: '#'
splitby: ','
keycol: 1
Number os keys: 33
tmpl_file = None
outname = 'std'
NG = 34
Generating graphs NG = 34 .....
Generating graphs NG = 35 .....
Generating graphs NG = 36 .....
Generating graphs NG = 37 .....
Generating graphs NG = 38 .....
Generating graphs NG = 39 .....
Generating graphs NG = 40 .....
Generating graphs NG = 42 .....
Generating graphs NG = 44 .....
Generating graphs NG = 46 .....
Generating graphs NG = 48 .....
Generating graphs NG = 50 .
Acyclic graph found after 56 trials.
NG = 50
OK
Format options:
width: 76
indent: 4
delimiter: ', '
# =======================================================================
# ================= Python code for perfect hash function ===============
# =======================================================================
G = [0, 0, 0, 0, 35, 39, 34, 0, 40, 0, 0, 39, 41, 0, 17, 22,
0, 0, 28, 0, 48, 39, 0, 2, 26, 21, 39, 0, 1, 0, 22, 44, 5, 13, 10, 0,
18, 30, 27, 19, 19, 16, 41, 0, 37, 12, 15, 42, 7, 0]
def hash_f(key, T):
return sum(ord(T[i % 8]) * ord(c) for i, c in enumerate(key)) % 50
def perfect_hash(key):
return (G[hash_f(key, "D1xUlEvm")] +
G[hash_f(key, "4tyvof9I")]) % 50
# ============================ Sanity check =============================
K = ["False", "None", "True", "and", "as", "assert",
"break", "class", "continue", "def", "del", "elif", "else", "except",
"finally", "for", "form", "global", "if", "import", "in", "is",
"lambda", "nonlocal", "not", "or", "pass", "raise", "return", "try",
"while", "with", "yield"]
assert len(K) == 33
for h, k in enumerate(K):
assert perfect_hash(k) == h
Solution
#!/usr/bin/python3
# ===================================================================
# reserverd word hash table
# ===================================================================
import user_interface as ui
# ---- reserved word functions
def False_function():
print('False function called')
def None_function():
print('None function called')
def True_function():
print('True function called')
def and_function():
print('and function called')
def as_function():
print('as function called')
def assert_function():
print('assert function called')
def break_function():
print('break function called')
def class_function():
print('class function called')
def continue_function():
print('continue function called')
def def_function():
print('def function called')
def del_function():
print('del function called')
def elif_function():
print('elif function called')
def else_function():
print('else function called')
def except_function():
print('except function called')
def finally_function():
print('finally function called')
def for_function():
print('for function called')
def form_function():
print('form function called')
def global_function():
print('global function called')
def if_function():
print('if function called')
def import_function():
print('import function called')
def in_function():
print('in function called')
def is_function():
print('is function called')
def lambda_function():
print('lambda function called')
def nonlocal_function():
print('nonlocal function called')
def not_function():
print('not function called')
def or_function():
print('or function called')
def pass_function():
print('pass function called')
def raise_function():
print('raise function called')
def return_function():
print('return function called')
def try_function():
print('try function called')
def while_function():
print('while function called')
def with_function():
print('with function called')
def yield_function():
print('yield function called')
# ---- reserved words
W = [ 'False', 'None', 'True', 'and', 'as', 'assert', 'break',
'class', 'continue', 'def', 'del', 'elif', 'else',
'except', 'finally', 'for', 'form', 'global', 'if',
'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or',
'pass', 'raise', 'return', 'try', 'while', 'with', 'yield' ]
# ---- associate reserved words with functions
X = [ False_function, None_function, True_function,
and_function, as_function, assert_function,
break_function, class_function, continue_function,
def_function, del_function, elif_function,
else_function, except_function, finally_function,
for_function, form_function, global_function,
if_function, import_function, in_function,
is_function, lambda_function, nonlocal_function,
not_function, or_function, pass_function,
raise_function, return_function, try_function,
while_function, with_function, yield_function,
]
# -------------------------------------------------------------------
# Python code for perfect hash function
# -------------------------------------------------------------------
G = [0, 0, 25, 46, 23, 28, 0, 0, 0, 27, 0, 0, 5, 3, 29, 24,
43, 26, 0, 0, 20, 17, 0, 3, 47, 14, 0, 23, 0, 0, 0, 22, 38, 1, 9, 43,
0, 0, 27, 49, 0, 4, 49, 1, 33, 0, 3, 0, 10, 5]
def hash_f(key, T):
return sum(ord(T[i % 8]) * ord(c) for i, c in enumerate(key)) % 50
def perfect_hash(key):
return (G[hash_f(key, "XQTXDFqM")] +
G[hash_f(key, "vqrQoQv4")]) % 50
# -------------------------------------------------------------------
# ---- main
# -------------------------------------------------------------------
if __name__ == '__main__':
w_max = len(W) - 1 # length of W array
while(True):
print()
s = ui.get_user_input('Enter reserved word: ')
if not s:
break
h = perfect_hash(s)
print()
print(f'Hash is {h}')
if h > w_max or s != W[h]:
print(f'{s} does not match')
##ui.pause()
else:
X[h]()
reserved_words.py
#!/usr/bin/python3
# ==================================================================
# sorted Python reserved words prep for insertion into
# test file
# ==================================================================
x = [ 'False', 'def', 'if', 'raise',
'None', 'del', 'import', 'return',
'True', 'elif', 'in', 'try',
'and', 'else', 'is', 'while',
'as', 'except', 'lambda', 'with',
'assert', 'finally', 'nonlocal', 'yield',
'break', 'for', 'not',
'class', 'form', 'or',
'continue', 'global', 'pass' ]
xx = sorted(x)
print(xx)
filename = 'reserved_words.txt'
with open(filename,'w') as fout:
for w in xx:
fout.write(w + '\n')
# ---- output reserved word function templates
for w in xx:
print(f'def {w}_function():')
print(f" print('{w} function called')")
# ---- output reserved word to function association
size = 18
i = 0
print('X = [ ',end='')
for w in xx:
f = f'{w}_function'
ff = f + ',' + ' '*(size - len(f))
print(ff,end='')
i += 1
if i > 2:
print('\n ',end='')
i = 0
print(' ]')