Assignment 3 solutions
Part of
the homework for 22C:50, Spring 2003
|
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; }
int hash( char *s ) { int j = 0; char ch; while ( (ch = *s++) != 0 ) { j = ( 5*(j + ch) ) % (tablim + 1); } return j; }
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= #000Ec) 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 |; ----------------------
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: