Assignment 4 solutions
Part of
the homework for 22C:50, Summer 2004
|
7. Decode the message 28844 15360 55628 in Radix 40.28844/40 = 721 remainder 4 = C
721/40 = 18 remainder 1 = A
18 = R15360/40 = 384 remainder 0 = blank
384/40 = 9 remainder 24 = X
9 = I55628/40 = 1390 remainder 28 = .
1390/40 = 34 remainder 30 = 0
34 = 4So, the result is "RACIX 40."
9. Explain the weakness of hash(s) = s[1] mod (tablim + 1)
This means the hash function depends on only one character of the string s; this means that all identifiers that have the same character in that position will hash to the same slot in the symbol table, and worse, consecutive characters hash to consecutive slots in the symbol table, so if more than about 26 distinct identifiers are involved, search times will hardly differ from a simple linear search. It hardly matters which character, but s[1] (does this really mean the second character?) is a really odd choice.
11. Rewrite Figure 3.20 for efficiency.
int hash( char * s ) { int j; char ch; j = 0; while ((ch = *s++) != '\0') { j := ( 5*(j + ch) ) % (tablim + 1); } return j; } /* hash */
First, chaining only works for forward references that are words (that is, large enough to hold a pointer). EAL allows bytes to contain forward references.
Second, chaining only works for simple forward references. EAL allows forward references within expressions. Here is an example illustrating both:
W X+3 B X X:
} else if ((SYM_HANDLE)lex_this.val == move_handle) { OBJECT_VALUE value; /* new value */ struct lexeme op; /* for errors only */ /* scan over the MOVE */ lex_scan(); /* process first operand */ op = lex_this; /* prepare for errors */ value = parse_operand(); if ((value.value > 0xFFFF) && (value.value < (UINT_MAX-0xFFFF))) { lex_error( &op, "bad one-word value" ); value.value = 0; } object_word( location, value ); location.value = location.value + 2; /* scan over comma */ parse_punc( '\'', "comma expected" ); /* process second operand */ op = lex_this; /* prepare for errors */ value = parse_operand(); if ((value.value > 0xFFFF) && (value.value < (UINT_MAX-0xFFFF))) { lex_error( &op, "bad one-word value" ); value.value = 0; } object_word( location, value ); location.value = location.value + 2; } else { ...