Midterm I Solutions and Comments
Part of
materials for 22C:50, Summer 2004
|
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
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
Median = 3.5
Mean = 3.25 X X
X X X
___X_____X___X_X_X_X_
0 . 1 . 2 . 3 . 4
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
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 = #00131 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.
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.
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.
#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: ________________________________________________
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.