Assignment 4 solutions

Part of the homework for 22C:50, Summer 2004
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Do problems 7, 9 and 11 at the end of Chapter 3 of the notes.
7. Decode the message 28844 15360 55628 in Radix 40.

28844/40 = 721 remainder 4 = C
721/40 = 18 remainder 1 = A
18 = R
15360/40 = 384 remainder 0 = blank
384/40 = 9 remainder 24 = X
9 = I
55628/40 = 1390 remainder 28 = .
1390/40 = 34 remainder 30 = 0
34 = 4
So, 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 */
```
What features of the EAL assembler would prevent your converting EAL from a 2-pass assembler to a 1-pass assembler with chaining used to resolve forward references?
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:
```

Look in the code for EAL, in file parser.c and find the code for processing the B and W pseudo-ops. Write the code you would to handle the MOVE opcode.

		} 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 { ...