Computer Science 5220
Spring 2003
Practice questions for exam 2

1. What is the difference between a synthesized attribute and an inherited attribute? Define each of those terms.

2. You are given the following (ambiguous) grammar for expressions.

         expr -> expr + expr
         expr -> expr * expr
         expr -> NUM
         expr -> VAR
     

   where NUM and VAR are tokens. The lexer provides an attribute NUM.val that is the (integer) value of a NUM token. It also provides an attribute VAR.name that is the name of a variable. You would like to translate these expressions into instructions for a stack machine. The stack machine has the following instructions. Push the value of the variable at offset k onto the stack

   PUSH_INT k	Push integer k onto the stack
   PUSH_VAR k
   ADD	Pop the top two numbers from the stack and push their sum
   MULT	Pop the top two numbers from the stack and push their product

   The PUSH_INT instruction can handle any integer that the lexer will produces as an attribute of a NUM token. You have access to three support functions: get_var_offset(v) returns the offset where the variable named v is stored; gen1(I) generates single-part instruction I, and gen2(I,k) generates two-part instruction I, with parameter k.

   Write semantic actions to be performed at each production that will generate code to compute a given expression and leave its value on the top of the stack. Do not worry that the grammar is ambiguous. That is a parsing problem, not a semantic one.

3. This is the same as the preceding exercise, but instead of performing actions to generate the code, you would like to create the code sequence as an attribute of an expression nonterminal. Suppose that, in addition to get_var_offset(v), the following functions are available. single(I) produces, as its value, a sequence that represents the single-part instruction I. doub(I,k) produces a code sequence for a two-part instruction. Operator + can be used to compute the concatenation of two code sequences.

4. Exercise 8.14 of the text. Assume that a Boolean expression can be passed inherited attributes E.true and E.false telling it where to jump to if the expression is true. Generate label instructions as in the text.

5. If your parser works by building syntax trees instead of directly writing translations, how can it handle the C for loop in a simpler way than is done in solving exercise 8.14 of the text?

6. How can attributes be used to perform type inference in a language such as Pascal?

7. Dataflow analysis is used to determine

   1. the relationship between places where variable values are used and where they are defined.
   2. where a program is in a loop.
   3. which parts of a program are good candidates for trying to keep variables in registers.

8. Why is register allocation one of the more important aspects of optimization?

9. What is the definition of a basic block?

10. How would a live variable analysis be useful in generating good quality executable code?
    1. It can help to avoid generating instructions to store some values from registers into memory.
    2. It allows you to use more registers to hold temporary values.
    3. A live variable analysis makes it unnecessary to perform a control flow analysis.
    4. A live variable analysis is useful in finding places where variables might be used before they are defined.

11. How does a type checker determine type information about a program when types are polymorphic, and can include type variables?