Programming language principles, part 2, CS 288, April 26, 2006

Each of the three questions is worth 20 points

 

  1. Using the simplified attribute grammar below, show the values of the each of the attributes reg, next_free_reg, and code for each of the nodes in the syntax tree given below. Note that the second of these attributes is inherited, while the other two are synthesized. Assume that the number k of available registers is 8. You needn't use any particular algorithm to find the attribute values. 
    reg_names : array [0..k-1] of register_name := ["r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8"]
   -- ordered set of temporaries
program → expr
    ⊲ expr.next_free_reg := 0
    ⊲ program.code := expr.code
'+' : expr1 → expr2 expr3
    ⊲ handle_op(expr1, expr2, expr3, "+")
'-' : expr1 → expr2 expr3
    ⊲ handle_op(expr1, expr2, expr3, "-")
'*' : expr1 → expr2 expr3
    ⊲ handle_op(expr1, expr2, expr3, "*")
'/' : expr1 → expr2 expr3
    ⊲ handle_op(expr1, expr2, expr3, "/")
id : expr → ε
    ⊲ expr.reg := reg_names[expr.next_free_reg mod k]
    ⊲ expr.code := [expr.reg ":=" expr.stp->name]
macro handle_op(ref result, L_operand, R_operand, op: syntax_tree_node)
    result.reg := L_operand.reg
    L_operand.next_free_reg := result.next_free_reg
    R_operand.next_free_reg := result.next_free_reg + 1
    if R_operand.next_free_reg < k
      spill_code := restore_code := nil
    else
      spill_code := ["*sp :=" reg_names[R_operand.next_free_reg mod k]] +
                      ["sp := sp - 4"]
      restore_code := ["sp := sp + 4"] +
                        [reg_names[R_operand.next_free_reg mod k] ":= *sp"]
    result.code := L_operand.code + spill_code + R_operand.code +
              [result.reg ":=" L_operand.reg op R_operand.reg + restore_code
    The grammar uses the notational conventions of Section 9.3 of Scott. In particular, square brackets delimit individual target instructions, juxtaposition indicates concatenation withing instructions, and the + operator indicates concatenation of instruction lists. You may assume that expr.stp->name yields the name of an identifier. Note that handle_op is a macro and not a grammar rule.

    The syntax tree to be used is 

            Program
           |
           *
         /   \
        +     -
       / \   / \
      a   b c   /
               / \
              d   e

     

  2. This question deals with registers, and especially with their use within procedure calls. Recall that it is common to use a frame pointer register to point to a known location within a frame of a subroutine call stack.
    1. What is the purpose of the spill code in the previous problem?
    2. What is the advantage of partitioning a processor's register set into a subset to be saved by the caller, and a subset to be saved by the callee?
    3. If static chains are used, why must at least part of the work for maintaining them be performed by the caller rather than the callee?
    4. How is the frame pointer used to access objects whose size is known at compile time?
    5. How is the frame pointer used to access objects whose size is not known at compile time (e.g., array parameters in some languages)?

     

  3. Suppose that a pointer variable p points to a structure with a field first
    1. State how would this field be accessed in C, C++, Ada, and Java (note that in Java, the variable would not be of an explicit pointer type)
    2. In which of these languages would the dereferencing of the pointer be performed automatically?
    3. When parameters are passed by reference in C++, must they be explicitly dereferenced?
    4. Unlike C++, C does not allow parameters to be passed by reference. How can this method of parameter passing be simulated in C? Consider what has to happen in the function header (or declaration or prototype), in the function body, and in the caller.