Homework 6

22C:50 Section 2, Fall 2000

Not Due Wednesday Oct. 4, 2000

To help you study for the Midterm on Oct 4

1. Consider the following code:

   ; a pointless comment
       W   55
       W   #55
   K   =   5
   L:  W   M
   M:            ; another comment
       W   L     ; and another comment
   ; and another!
       W   K
   

   Part a: Hand assemble this code. You can check your work by using the solution to MP1 distributed to the class:

   Part b: What identifiers should the above code place in the symbol table, and what values should it associate with these identifiers? (Ignore the error in the solution to MP1 that was distributed to the class! In that code, it foolishly puts a, another and and in the symbol table.)

   Part c: Given a symbol table implemented using a string pool, what strings would you expect the assembler to put in the string pool as a result of assembling the above code? (Ignore any identifiers that get put in the pool in order to make them predefined.)

   Part d: Which symbols defined in the above code are absolute and which are relocatable?

   Part e: Which words of output produced by the assembly of the above code contain relocatable values and which contain absolute values?

2. Consider the following code in our example assembly language, as extended by chapters 5 and 6:

       MACRO   N,X,Y
         IF (X) > (Y)
           N (X-1),(Y+1)
           W X
         ELSE
           W Y
         ENDIF
       ENDMAC
   
       N 1 2
   
       N 2 1
   
       N 3 0
   

   Part a: Hand expand all macros in this code, showing an equivalent sequence of W commands with simple integer arguments.

   Part b: What are the actual parameters passed to each call to the macro N that is made as a consequence of the final source line of the above code.

   Part c: How might these actual parameters be packed onto the stack top if the advice from Chapter 6 is taken.

   Part d: Two lines in the above code include lots of parentheses. Explain what these are used for. Note that there are two reasons to use parentheses in our example language.

3. Consider the following grammar:

   <s-expr> ::= <atom>
             |  ( [ <s-expr> { <s-expr> } . [ <s-expr> ] ] )
   <atom> ::= <identifier>
            | <number>
   

   Boldface has been used in the above grammar to distinguish between EBNF symbols (not bold) and terminal symbols that could be confused with special EBNF symbols (bold). (This grammar is the grammar for S-expressions, the fundamental data type of the LISP programming language). Here are some example S-expressions:

   simple
   ( dotted . pair )
   ( list of atoms )
   ( )
   ( list of (mixed . pairs) (lists and atoms) . (final) )
   

   Part a: What are the terminal symbols in the above grammar, and what are the nonterminals?

   Part b: Write a parser, assuming a lexical analyzer such as that distributed with the example solution to MP1.

   Part c: Discuss the role of lookahead in parsing this code.