Midterm I Solutions

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

Grade Distributions

For the Exam plus Assignments

Includes homeworks 1-3, machine problem 1 and the first exam; excludes those who did not take the exam. Note that all grade scales shown here should be considered to be very rough!


Mean    = 18.44
Median  = 19.8
                                                X X   X
   _____________________X_X_X_X_X___X_X_X___X_X_X_X_X_X_X___
     0 . 2 . 4 . 6 . 8 .10 . 2 . 4 . 6 . 8 .20 . 2 . 4 . 6
                       D         C         B         A

For the Exam

Mean    = 7.69                              X
Median  = 7.7                             X X
                            X X     X     X X
   _____________________X_X_X_X_X_X_X___X_X_X___
     0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
                     D      C      B      A

Exam Scores versus Homework and Machine Problem Scores

These distributions show clearly that high performance on exams is far more likely among those who've done the homework and machine problems.

    9 |                    1  2  2  2   9 |        1  5  1
 e  8 |  1                              8 |  1
 x  7 |                 1        1  1   7 |        2     1
 a  6 |     1        1  1               6 |  2        1
 m  5 |        1              2         5 |  1     1  1
    4 |___________1___________________  4 |__1______________
         2  3  4  5  6  7  8  9 10 11        0  1  2  3  4
                   homework                 machine problem

Exam Scores versus Homework Scores

Exam Solutions

Hand assemble the this EAL code, and show the final contents of the symbol table. There are extra blanks! Do not fill in unused symbol table entries or next to lines that assemble nothing into memory. It is OK to cross out and replace values where they are changed. (2 points)
```
EAL V2.0 by Douglas W. Jones; Mon Jun 30 14:56:55 2003

     1 0000: 0A    |     B    B     -- 4 had forward reference trouble
     2 0001: 0011  |     W    #11   -- 5 had size of word trouble
     3             |; Commentary     \ 2 had hex conversion problems
     4             |B    =    5
     5 0003: 05    |A:   B    B	    -- 4 had forward reference trouble
     6 0004: 03    |     B    A
     7             |B    =    10
     8 0005: 000B  |     W    11    -- 4 had size of word trouble
                                     \ 1 had hex conversion problems
       ; symbol table:
       A       =       #0003        -- 1 had a bad value here
       B       =       #000A        -- 1 omitted this symbol
```
7 had good answers here; hex conversion problems involving the number 11₁₀ and 11₁₆ caused trouble for a few students.
Noting the size of one-word operands using the correct number of hex digits in the assembly listing caused problems for roughly 1/4 of the class. A similar number had problems with the multiple definitions of the symbol B; which definition governs what use of the symbol? The latter problem is closely related to homework 2 problem 5, so anyone who did the assignments was well prepared for this question.
Complete the header comments in this fragment of a parser. (2 points)
```
void parse_notion()
/* parse one notion following this EBNF grammar:
   <notion> := $ <notion> $
            |  <theme>
*/
{
	if (lex_ispunc( &lex_this, '$' )) {
		lex_scan();
		parse_notion();
		parse_punc( '$', "dollarsign expected" );
	} else {
		parse_theme();
	}
}
```
3 had good answers. 11 omitted the second $ from the rule, 3 had strange uses of curly braces { } in an attempt to indicate iteration without use of recurision, despite the fact that the function itself is clearly recursive. 3 used curly braces for grouping or had extra sets of them with unclear intent. 5 made no use of either recursion or curly braces, suggesting no understanding of the infinite set of possible notions allowed by this grammar. Finally 4 introduced new and sometimes strange nonterminals.

Hand assemble the following EAL code, and show what goes in the symbol table. For those lines of code that cause data to be stored in memory, show the memory address that is changed and the value stored in memory. All numbers should be shown in hexadecimal, with a trailing plus sign to indicate those that are relocatable. There are many extra blanks! Do not fill blanks for unused symbol table entries or lines that assemble nothing to memory. (2 points)

EAL V3.0 by Douglas W. Jones; Mon Jun 30 15:18:40 2003

     1             |A    =    .      -- 2 assembled something here
     2             |.    =    #100   
     3 0100: 0000+ |B:   W    D      -- 4 used the wrong address
     4             |C:               \  7 misrelocated line 3 data
     5             |.    =    A
     6 0000+ 0100  |D:   W    B      -- 5 misrelocated this address
     7             |.    =    C      \  3 misrelocated line 6 data
     8 0102: 0002+ |     W    D+2    -- 6 misrelocated this address
     9             |                 \  7 misrelocated this data

; symbol table:
A       =       #0000+  -- 1 had the wrong value, 3 misrelocated
B       =       #0100   -- 2 had the wrong value, 3 misrelocated
C       =       #0102   -- 2 had the wrong value, 5 misrelocated
D       =       #0000+  -- 1 had the wrong value, 7 misrelocated

5 got this entirely write, 1 got it so entirely wrong that errors could not be incorporated in the above. Homework 4 problem 3 was good preparation for this problem.

Write EAL code equivalent to that on the left, but without using any macro or conditional directives. (2.0 points)
```
MACRO T,I	      B  3
  B I                 B  2
  IF I > 1            B  1
    T (I-1)           B  1
    T (I-1)           B  2
  ENDIF               B  1
ENDMAC                B  1
```
7 got full credit. 2 gave 32121, getting the first recursion correct but getting careless on the second. 1 gave 321321, expressing an intuitive understanding that it did something twice. 1 gave 321, expressing only the understanding that it counts down somehow; 2 gave 3210, getting this but with the wrong terminating condition. Only one left it blank. Problem 2 on assignment 4 provided preparation for recursive macros such as this.
Consider the following fragment from the EBNF grammar for C:

<number> ::= <decimal digit> { <decimal digit> }
| 0 { <octal digit> }
| 0x { <hexidecmal digit> }

This describes lexical details of C, so assume we start with a lexical analyzer such as the one used with the EAL assembler. In the fragment of lexical analysis code below, all details that don't relate to the above grammar fragment been left out, including everything about other lexeme types and everything having to do with actually evaluating the number. The blanks relate to key issues that connect with the grammar! Fill in the blanks! (2 points)
```
...
} else if (*pos == '0' ) { /* -- 1 forgot the quotes here */
	pos++; /* skip past 0 prefix */
	if (*pos == 'x') { /* it must be a hexadecimal number */
		pos++ ; /* -- one did this wrong */
		while (isxdigit( *pos )) { /* -- 1 missed the * */
		                           /* -- 1 had something really odd*/
			pos++;
		}

	} else { /* it must be an octal number -- one had trouble */
		while (isdigit( *pos )) {
			if (*pos > '7' ) { /* -- 4 off by 1 */
			                      /* -- 8 forgot the quotes */
			                      /* -- 3 completely missed it */
				lex_error( &lex_next, "bad digit" );
			}
			pos++;
		}
	}
} else if ( isdigit( *pos )) { /* -- 2 had really odd things here */
	do {
		pos++; /* -- 1 had a really odd answer here */
	} while (isdigit( *pos ));

} else ...
```
5 had perfect answers here. This problem should have been fairly easy for anyone who did machine problem 1 with all the work it required on the lexical analyzer of the example assembler, since the code given here was very much in the style of the code from the machine problem.