Midterm I

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

 

Name: ________________________________________________ ID Number: ___________________

Please answer in the space provided! Your name must be legible and in the form used on your University ID card! Illegible and verbose answers will be penalized! This exam is open-book, open-notes, closed neighbor! This exam 10 points; allocate 4-5 minutes per point.

  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)
     line     hexadecimal     source
    number  location  value    text
    
      1    ________  _______  .    =    #10          symbol table
                                                    symbol    value
      2    ________  _______       W    A 
                                                  ________  ________
      3    ________  _______  B    =    10
                                                  ________  ________
      4    ________  _______  ; commentary
                                                  ________  ________
      5    ________  _______  A:          
                                                  ________  ________
      6    ________  _______       B    B
    
      7    ________  _______  B    =    .
     
      8    ________  _______       W    B 
    

  2. Complete the header comments in this fragment of a parser. (2 points)
    void parse_oddity()
    /* parse one oddity following this EBNF grammar:
    
       _____________________________________________
    
       _____________________________________________
    */
    {
    	if (lex_ispunc( &lex_this, '(' )) {
    		lex_scan();
    		while (!lex_ispunc( &lex_this, ')' )) {
    			parse_oddity;
    		}
    		lex_scan();
    	} else {
    		parse_thingus();
    	}
    }
    

     

    Name: ________________________________________________

     

     

  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)

    ________________________________________________________
    
    ________________________________________________________
    
    ________________________________________________________
    

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

    ________________________________________________________
    

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

    ________________________________________________________
    
     

  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;              ___________________________________
    
    j = two( 2, + );              ___________________________________
      
    k = two( two( 2, + ), * );    ___________________________________
    
                                  ___________________________________
    

     

     

     

    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)

    ________________________________________________________
    
    ________________________________________________________
    

    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)

    ________________________________________________________
    
    ________________________________________________________
    
    ________________________________________________________
    
    ________________________________________________________
    
    ________________________________________________________