Assignment 3 solutions

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

From Chapter 3

  1. Rewrite compare from 3.13 so it is efficient. 
    	BOOLEAN compare( char * s, int i )
	/* compare string with symbol in string pool
	   given s, pointer to first char of string
	   given i, index of first char of string in pool
	   returns true if the two strings are equal
	*/
	{
		char ch;
		for (;;) {
			ch = *s;
			if (ch != pool[i]) break;
			if (ch == marker) return TRUE;
			i++;
			s++;
		}
		return FALSE;
	}

  2. Rewrite the code from 3.20 for speed 
    	int hash( char *s )
	{
		int j = 0;
		char ch;
		while ( (ch = *s++) != 0 ) {
			j = ( 5*(j + ch) ) % (tablim + 1);
		}
		return j;	
	}

From Chapter 4

  1. Example code, assembled under different schemes:

    a) Assembled by hand or by machine gives this: 

         2 0000: 0002  |ROOT:    W      FATHER
     3 0002: 0006  |FATHER:  W      SON1
     4 0004: 000A  |         W      SON2
     5 0006: 0000  |SON1:    W      NIL
     6 0008: 0000  |         W      NIL
     7             |; ----------------------
     8 000A: 000E  |SON2:    W      GRANDSON
     9 000C: 0000  |         W      NIL
    10 000E: 0000  |GRANDSON:W      NIL
    11 0010: 0000  |         W      NIL
    12             |NIL      =      0

    b) The symbol table at the line of dashes in each of 2 passes: 

    	-- at line 7 during pass 1 (in order of occurance):
        ROOT    =       #0000
        FATHER  =       #0002
        SON1    =       #0006
        SON2    =       undefined
        NIL     =       undefined
        GRANDSON=       not yet encountered, so not in the table

	-- at line 7 during pass 2 (in order of occurance):
        ROOT    =       #0000
        FATHER  =       #0002
        SON1    =       #0006
        SON2    =       #000A
        NIL     =       #0000
        GRANDSON=       #000E
    c) The symbol table and memory using chaining: 
    	-- at line 7 (in order of occurance):
        ROOT    =       #0000, defined
        FATHER  =       #0002, defined
        SON1    =       #0006, defined
        SON2    =       #0004, undefined (head of chain)
        NIL     =       #0008, undefined (head of chain)

     2 0000: 0002  |ROOT:    W      FATHER
     3 0002: 0006  |FATHER:  W      SON1
     4 0004: 0004  |         W      SON2  -- end of chain
     5 0006: 0006  |SON1:    W      NIL   -- end of chain
     6 0008: 0006  |         W      NIL   -- mid-chain
     7             |; ----------------------

From Chapter 5

  1. Why can a 2-pass assembler handle one but not the other?
    Here's what happens when EAL assembles example I, where there are plenty of forward references, but everything is defined by the start of pass 2: 
         1             |.  = #200
     2 0200: 0204  |   W A
     3             |C:
     4             |.  = A
     5 0204: 0202  |   W B
     6             |.  = C
     7 0202: 0204  |B: W A
     8             |A:
    Here's what happens when EAL assembles example II, where there are plenty of forward references, but not everything is defined by the start of pass 2; comments elaborate on this: 
         1             |.  = #200
     2 0200: ????  |   W B     ; B was undefined during pass 2!
     3             |C:
     4             |.  = A     ; because on pass 1, A was undefined here
     5 0204: 0204  |B: W B     ; so on pass 1, B could not be defined here
     6             |.  = C
     7 0202: 0204  |   W A
     8             |A: