Midterm I Solutions and Comments

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

Grade Distributions

Exam Scores

Mean   = 6.8              X   X X        
Median = 6.9              X   X X   X    
                          X   X X X X X X
                      X X X X X X 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

Midterm Scores: Exam plus Homeworks 1-6 plus Machine Problems 1-2

Mean   = 28.0                   X X
Median = 29.9                   X X     X
                                X X     X
                              X X X X   X
          X         X X   X X X X X X X X
  ________X_____X___X_X___X_X_X_X_X_X_X_X_X_X_
   0 . 4 . 8 . 12. 16. 20. 24. 28. 32. 36. 40
                    F    D    C    B    A

Note: The low overall score for someone who turned in at least one machine problem was 16, and the mean overall score for these students was 30.1.

The Exam

Hand assemble this EAL code using two passes to resolve forward references, and show the final contents of the symbol table. There are extra blanks! Do not fill in anything 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)
```
 line     hexadecimal     source
number  location  value    text

  1    __0000__  __0010_       W    B            symbol table
                                                symbol    value
  2    __0002__  __12___       B    #12
                                              ____B___  __0010__
  3    ________  _______  B    =    12
                                              ____A___  __0003__
  4    ________  _______  ; etaion shrdlu
                                              ________  ________
  5    __0003__  __000C_  A:   W    B
                                              ________  ________
  6    __0005__  __03___       B    A

  7    __0006__  __000F_       W    A+B
 
  8    ________  _______  B    =    #10
```
10 did well here, and 9 earned at least 3/4 credit. 6 earned less than half credit. All appear to have tried hard to do this problem. The most common error was failing to report 16-bit values for words (10 reported them as 8-bit values instead). 10 had real difficulty adding the values of the identifiers A and B, and 9 mistook hex for decimal or decimal for hex, 6 made the complementary error, reporting bytes as 16-bit values. 6 failed to advance the location countery by 2 for words, and 5 advanced it by 2 for bytes. There were a number of less common errors.
Complete the header comments in this fragment of a parser. (2 points)
```
void parse_transfix()
/* parse one transfix following this EBNF grammar:

   ___::=_(_{__}_)__________

   _______________|_____________________
*/
{
	if (lex_ispunc( &lex_this, '(' )) {
		lex_scan();
		while (!lex_ispunc( &lex_this, ')' ) parse_transfix();
		parse_punc( ')', "end paren expected" );
	} else {
		parse_womble();
	}
}
```
13 did well here, and 17 earned more than 3/4 credit. Only 4 had less than half credit. The most common error was to omit the curly braces indicating the indefinite iteration corresponding to the while loop; 15 did this. Other errors were difficult to classify. some stra
Given a string s, the substr(s,i,j) operator returns a new string that is the substring of s running from character i to character j (counting from character 1). Given two strings s1 and s2, the operation index(s1,s2) returns the index of the first character in s2 that is found in s1. The operation length(s) returns the length of s in characters.
The constant string values nonblank, alphabetic, nonalphanumeric, numeric, and nonnumeric contain one each of every character of the corresponding type.
Here is a proposal for the design of a lexical analyzer:
```
lex_scan()
{
	int i;
	lex_this = lex_next;
	i = index( line, nonblank );
	if (i > 1) line = substr( line, i, length( line ) );
	i = index( line, alphabetic );
	if (i == 1) { /* found an identifier */
		i = index( line, nonalphanumeric );
		lex_next = substr( line, 1, i-1 );
		line = substr( line, i, length( line ) );
		return;
	}
	i = index( line, numeric );
	if (i == 1) { /* found a number */
		i = index( line, nonnumeric );
		lex_next = substr( line, 1, i-1 );
		line = substr( line, i, length( line ) );
		return;
	}
	/* found punctuation */
	lex_next = substr( line, 1, 1 );
	line = substr( line, 2, length( line ) );
	return;
}
```
What is seriously wrong with this incomplete but workable proposal? (2 points)
```
__The big problem:  it is grossly inefficient____________________

_________________________________________________________________

_________________________________________________________________
```
6 did well. 3 more earned more than half credit. 9 earned no credit and 16 more earned less than half credit. This was the hardest question on the exam. Many gave false assertions about the code. Good partial credit was given for those who focused on ways in which the code is incomplete, even though the statement of the question asserted this incompleteness; typical observations in this category include that the code does not handle end of line or end of file. Half credit was given for those who proposed refinements such as the inclusion of a lexical class with each lexeme.

Write EAL code equivalent to that on the left, but without using any macro or conditional directives. (2.0 points)

MACRO T,I	                           _____B 2____________
  IF I > 0
    B I                                    _____B 1____________
    T (I >> 1)
  ENDIF                                    _____B 0____________
  B I
ENDMAC                                     _____B 1____________

X 2                                        _____B 2____________

18 did well here, and 1 more earned more than 3/4 credit. 10 earned less than half credit. Many who had difficulty simply seemed to have difficulty mastering the recursion.

Consider the following fragment from the EBNF grammar for C:

<variable> ::= <identifier> { <qualifier> }
| * <variable>
<qualifier> ::= . <identifier>
| [ <expression> ]

This describes syntactic details, and we will assume a lexical analyzer such as the one used with the EAL assembler in order to write some code for a parser. In the fragment of parsing analysis code below, all details that don't relate to the above grammar fragment been left out. The blanks relate to key issues that connect the code with the grammar! Fill in the blanks! (2 points)
```
void parse_variable()
{
	if (!lex_ispunc( &lex_this, '*' )) {
		if (lex_this.typ != identifier) error( "identifier expected" );
		
		__lex_scan(); /* scan over identifier */_____
		while (lex_ispunc( &lex_this, '.' )
		||     lex_ispunc( &lex_this, '[' )) {

			__parse_qualifier();_____________________
		}
	} else {
		----- grading error here! 32 students get 0.2 points more -----
		__lex_scan();_________________________________
		parse_variable();
	}
}

void parse_qualifier()
{
	if (lex_ispunc( &lex_this, '.' )) {
		lex_scan();

		__if (lex.typ != identifier) error( "identifier expected" );__
		lex_scan();
	} else if (lex_ispunc( &lex_this, '[' )) {
		lex_scan();

		__parse_expression();____________________
		parse_punc( ']', "end bracket expected" );
		
	}
}
```
Most had over half credit here, and 11 had over 3/4 credit. This question was carefully composed so that most lines that were left blank had prototypes somewhere else in the code that could be copied. 22 students invented a function called parse_identifier() and used it on blanks 1 and 4, but unfortunately, these two blanks force different assumptions to be made about whether or not parse_identifier() calls lex_scan(). 11 more called parse_identifier() only for blank 4, but all routines of the form parse_x() are assumed to scan over the thing they parse, and the call to lex_scan right after this blank makes this an inappropriate move.