C431 Final Exam -- Fall 1994

Haynes/Kumar

1. (6 points) Consider the following context-free grammar with start symbol S. We represent the empty production by #.

   S --> AB
   A --> #
   A --> aA
   B --> Bb
   B --> b
   B --> c
   

   If the language expressed by this grammar is regular, define it using a regular expression. If not, why not?

2. (12 points)
   1. Give context-free production rules that define the same language as that defined by the regular expression { a | b c } d* a.
   2. Why do compilers typically employ a lexical analyser in addition to a parser, instead of parsing characters directly?

3. (12 points) It has been claimed that "the heap is cheaper than the stack." Thus, if this claim is to be believed, an implementation that allocates procedure call frames on the heap may be as fast or faster than a traditional implementation that allocates procedure call frames on the stack.
   1. Under what circumstancess might this be true? Why? Do you think these circumstances are likely?
   2. Give at least two distinct reasons why heap allocation of call frames simplifies the implementation of Scheme.

4. (20 points) In your projects this semester:
   1. set! statements were eliminated. Suppose that instead assignment to a variable, say x, were compiled to assign a new value to the same location from which a value is fetched on a reference to x. Give an expression, which is as simple as possible, for which this approach yields an improper value (one other than the value dictated by the semantics of Scheme). Indicate the improper value of the expression.

   2. closures captured the necessary elements of the environment in which they are created by forming a flat list of values. Briefly describe the more commonn static-chain technique for representing closure environments and indicate why this technique is inappropriate for your Scheme implementation.

   3. complex (non-immediate) literals were translated into references to global bindings.
      1. Why not simply compile them in-line (at the place of the literal in the text) and avoid global literal bindings?
      2. What is the advantage of using a separate register as a base for indexing the global bindings, rather than just let-binding the complex literal values?

5. (50 points) In class we discussed a method for supporting incremental compilation with top-level definitions in Scheme. We also discussed linking techniques as they are commonly used in traditional languages that support separate compilation. In this problem you are asked to indicate the design of a separate compilation mechanism that would be appropriate as an extension of the your project this semseter.

   Assume the language of your project is extended so that a program is a sequence of expressions that are evaluated in order. Variables that appear free in these expressions refer to top-level bindings. (set! may be used to make top-level "definitions" as in Chez Scheme.) All top-level bindings, as well as the values of all complex literals, should be referenced as offsets from the global pointer. (It is not necessary for the intermediate compilation forms of this extended language to be executable as Scheme expressions.)

   The expressions may be distributed over a sequence of independently compiled files. Before a program may be run, a linking loader must be invoked as a Unix command and given the names of the object files that resulted from compilation of the program's files.

   Describe in as much detail as possible a reasonable design for this language extension. Be sure to include the object file format and a careful description of the operations performed by the linking loader. Do not bother with details of the intermediate representations used by the compiler except as necessary to understand the support of independent compilation.