Comprehensive Examination
Compiler Construction
Spring 1996
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.
- 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
- Show a code fragment that has two possible parse trees with this grammar.
Draw the parse trees.
- Modify the grammar to resolve this ambiguity in the obvious way-that
is, to match the dangling else with the closest unmatched then.
- 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.
- How are parameters passed from caller to callee?
How are arrays passed?
- Who saves registers at the point of call? Explain the rationale
behind your choice.
- 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.
- How are return values handled? In particular, C has the ability
to return a structure.
- Sketch the layout of an activation record. Include all the major
fields required to support your implementation of
the procedure abstraction.
- 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.
- For each algorithm, describe the machine model on which
it operates and the criteria by which it is ``optimal''.
- For each algorithm, what is its asymptotic complexity?
- On a modern machine, which algorithm would you expect to
generate better code? Justify your opinion.
- Analysis and Optimization - Aho, Sethi, and Ullman describe
several different ``data-flow analysis problems.''
Choose one.
- Write down the equations that describe the data-flow problem
and define each set mentioned in the equations.
- Show an algorithm for solving these data-flow equations.
- What is the complexity of your algorithm? How many set operations
will it perform before halting?
- Describe an optimization that might use the results of this data-flow
analysis.