# Midterm I Solutions and Comments

### Exam

```Median = 5.5          X
Mean   = 6.16         X
X         X
_________________X_X_X___X_X_X_______X___
1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
Rough Grade Scale       C       B       A
```

### Homework

```Median = 14.7
Mean   = 15.15
X                 X
_______X_____X_X_X___X_X_________X_X___X_____
10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20
```

### Machine Problem

```Median = 3.5
Mean   = 3.25          X X
X   X X
___X_____X___X_X_X_X_
0 . 1 . 2 . 3 . 4
```

### Overall

```Median = 24.1
Mean   = 24.47

___________X___X___X_____X_____X___X_____X_X___X___________X_X____
16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31
Rough Grade Scale          C               B               A
```

## Exam Solutions

1. 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 V0.0 by Douglas W. Jones; Mon Jun 28 11:19:22 2004

1             |.    =    #10
2 0010: 0012  |     W    A
3             |B    =    10
4             |; commentary
5             |A:
6 0012: 0A    |     B    B
7             |B    =    .
8 0013: 0013  |     W    B

; symbol table:
A       =       #0012
B       =       #0013
```

1 student did well here, 3 each had 1, 2 and 3 significant errors, 1 had 5 significant errors. Popular errors included confusion of hexadecimal and decimal numbers and allocation of memory for lines of assembly code that did not assemble anything into memory.

2. Complete the header comments in this fragment of a parser. (2 points)
```void parse_oddity()
/* parse one oddity following this EBNF grammar:
___ <oddity> ::= ( { <oddity> } )
___           |  <thingus>
*/
```

8 did well here, 2 made one significant errors, and 2 each made 2 and 3 significant errors. Most of the errors involved problems with understanding the while loop parsing zero or more <oddity>s.

This grammar is almost the complete syntax of a historically important programming language, LISP. In that language, an >oddity> is called an S-expression, and a <thingus> is called an atom.

3. Consider this bit of code, from the previous problem:
```void parse_oddity()                                          /*A*/
{                                                            /*B*/
if (lex_ispunc( &lex_this, '(' )) {                  /*C*/
lex_scan();                                  /*D*/
while (!lex_ispunc( &lex_this, ')' )) {      /*E*/
parse_oddity;                        /*F*/
}                                            /*G*/
lex_scan();                                  /*H*/
} else {                                             /*I*/
parse_thingus();                             /*J*/
}                                                    /*K*/
}                                                            /*L*/
```
If the input text has balanced parentheses, it works just fine. If the input text has unbalanced parentheses, it sometimes goes into a loop.

a) Exactly what kind of unbalanced parens cause this? (1 point)

The problem occurs when there is a missing end paren,

8 did well here, 3 earned partial credit for ambiguous or strange errors that were still related to the correct answer.

b) Which line should have been augmented with a check for end-of-file to prevent this? (0.5 points)

Line E should have read something like

```		while ((!lex_ispunc( &lex_this, ')' ))        /*E1*/
&& (lex_this.typ != lex_eof)          ) {     /*E2*/
```

9 did well here, 2 earned no credit with strange answers.

c) Which line should read parse_punc( ')', "end paren expected");? (0.5 points)

Line H should have been as suggested.

3 did well here, 4 suggested adding this line between lines G and H, and 4 had odd suggestions, most frequently, adding it within the loop between lines F and G.

4. Write C code equivalent to that on the left, but without using any macros. (2.0 points)
```#define two(a,b) a b a
two( i, = ) + 1;              ___ i = i + 1;
j = two( 2, + );              ___ j = 2 + 2;
k = two( two( 2, + ), * );    ___ k = 2 + 2 * 2 + 2;
```

2 did well here, 3 more got the first two lines right and then got confused on the final line -- generally adding parentheses to force the expression to have the value 16, when in fact, the value is 8. 3 more had confused answers that earned a small amount of partial credit, and 3 earned no credit.

The most common fatal error was to attempt to construct a function (closed subroutine) equivalent to the define (macro) given here. In fact, this cannot be done for this example macro in C.

Name: ________________________________________________

5. Consider the following fragment of code from a top-down recursive descent compiler.
```parse_if_statement()
/* <if statement> ::=
IF <expression> THEN <block> [ ELSE <block> ] ENDIF
*/
{
int if_number = unique_integer();
int else_number = unique_integer();
lex_scan();
parse_expression();
printf( "  JFALSE .   \n" );
printf( "FIX%d = .-2  \n", if_number );
parse_keyword( then_handle );
parse_block();
if (is_keyword( else_handle )) {
printf( "  JUMP .     \n" );
printf( "FIX%d = .-2  \n", else_number );
printf( "HERE  = .    \n" );
printf( ". = FIX%d    \n", if_number );
printf( "  W HERE     \n" );
printf( ". = HERE     \n" );
if_number = else_number
lex_scan();
parse_block();
}
parse_keyword( endif_handle );
printf( "HERE  = .    \n" );
printf( ". = FIX%d    \n", if_number );
printf( "  W HERE     \n" );
printf( ". = HERE     \n" );
}
```

a) Make an educated guess about the format of the operand field of the JUMP and JFALSE instructions. (1 point)

Jumps and conditional jumps in this machine language must have a two byte destination address field that is the simple direct address of the destination. No indexing or PC relative addressing appears to be involved.

2 did well here. 3 earned about half credit; typically, they did not give the size of the operand, but only that it was an address. 5 earned no credit.

a) The output of this compiler is an EAL-like assembly language. How is the forward reference problem solved by the combination of assembler and compiler. (1 point)

The compiler carefully avoids generating any forward references, so the assembler can finish its job in one pass without using chaining. The solution used by the compiler, setting the assembly origin back to the address that needs to be fixed up once that address is known, resembles chaining in a vague way.

2 did well here, 2 earned half credit by saying chaining, and the remainder earned no credit.