This is a closed-notes, closed-book exam administered under the Rice Honor Code. You have two hours to complete the exam.

We have tried to give you all the information required to complete each question. If you reach a point where you are missing a critical piece of information, make a reasonable assumption, record it in your answer book, and continue.

1. Syntax analysis - A classic example of an ambiguous grammar is the if-then-else problem.

   [stmt] ::= if [expr] then [stmt] else [stmt]
           |  if [expr] then [stmt]
           |  other statements
   

   1. Show a code fragment that has two possible parse trees with this grammar. Draw the parse trees.
   2. Modify the grammar to resolve this ambiguity in the obvious way-that is, to match the dangling else with the closest unmatched then.

2. Linkage Conventions - Your employer has asked you to design the linkage convention for their next generation system. Your convention will be used to support a number of languages, including Pascal, Fortran, and C.

   There are several key issues that you must decide today.

   1. How are parameters passed from caller to callee? How are arrays passed?
   2. Who saves registers at the point of call? Explain the rationale behind your choice.
   3. How is addressability established for non-local variables? Assume that they come in three flavors: C's static variables, C's global variables, and Pascal's lexically scoped local variables.
   4. How are return values handled? In particular, C has the ability to return a structure.
   5. Sketch the layout of an activation record. Include all the major fields required to support your implementation of the procedure abstraction.

3. Code generation - Aho, Sethi, and Ullman describe two methods for ``optimal'' code generation: the tree-labelling algorithm due to Sethi and Ullman and the dynamic programming algorithm due to Aho and Johnson.
   1. For each algorithm, describe the machine model on which it operates and the criteria by which it is ``optimal''.
   2. For each algorithm, what is its asymptotic complexity?
   3. On a modern machine, which algorithm would you expect to generate better code? Justify your opinion.

4. Analysis and Optimization - Aho, Sethi, and Ullman describe several different ``data-flow analysis problems.'' Choose one.
   1. Write down the equations that describe the data-flow problem and define each set mentioned in the equations.
   2. Show an algorithm for solving these data-flow equations.
   3. What is the complexity of your algorithm? How many set operations will it perform before halting?
   4. Describe an optimization that might use the results of this data-flow analysis.