Compiler Construction
Spring 2000
Final Examination

This is a take-home examination. Exams should be placed in my mailbox by
Mednesday May. 10, 5 pm. You are welcome to use any references and texts,
and to discuss the questions with your colleagues, but the work you hand
in should be strictly yours. Needless to say, this also applies to the
final project, which is due at the end of business, May 12.

Problem 1

Consider the language of the alphabet { 0, 1}, which consists of strings
with the same number of 0'a and 1's.

a) Is the grammar for this language regular? Explain.

b) Sketch a parsing algorithm for this language (No need to find a grammar
   for the language).

c) (Optional) write a grammar for this language.

Problem 2

 Your project implemented parameter-passing by value for scalar types.
Suppose we want to implement parameter-passing by reference for arrays, and
be able to write the usual:

                type t is array (integer range <>) of integer;
                function sum (arg : t) return integer is
                  result : integer := 0;
                   for J in arg'first .. arg'last loop
                      result := result + arg (J);     --  line (A)
                   end loop;
                   return result;
                end sum;

Somewhere else we call this function:

                table : t (1..N) := ....
                X : Integer;
                X := sum (table);    --  line (B)

a) Indicate what quadruples and what assembly (for your chosen target machine)
would be generated for line (A). You can assume that the bounds of the array
are stored at locations 0 and 1, so the data itself starts at offset 2 from
the array base.

b) What code (quadruples and assembly) needs to be generated for the
assignment at (B)?

Problem 3

Consider the following procedure, that computes the primes numbers up
to some number N.

         with text_io; use text_io;
         procedure Sieve (N : integer) is
            table : array (1..10000) of boolean;
            for I in table'range loop
               table (I) := True;
            end loop;

            for I in 2 .. Integer (Sqrt (N)) loop
              if table (I) then                     --  I is a prime
                  for J in 2 .. Table'Last loop
                     exit when I * J > Table'Last;
                     Table (I * J) := False;        --  multiple of I
                   end loop;
               end if;
             end loop;
             for I in 2 . Table'Last loop
               if Table (I) then
                  put (I); put_line (" is a prime");
               end if;
              end loop;
           end sieve;

a) Write the quadruples corresponding to this procedure. If your compiler
can process this example you can use it as a guide. Describe what needs to be
done for the function call to Sqrt. 

b) Show the basic blocks of this procedure.

c) Show the flow graph for this procedure.

d) Identify the loop-invariant computations, if any, and move them out of
loops if possible.

e) are there induction variable present? If so, can their use be optimized?

Problem 4

An expression E is said to be very busy at point P if on all paths from P
the expression E is evaluated before any of its operands is redefined. Note
that this definition means that E itself is not necessarily evaluated at P,
only that E is evaluated downstream on all possible paths from P. If an
expression is very busy at P, it may be advantageous to compute it once at
P, rather than at each downstream place where it is currently computed (this
optimization is called hoisting. For example, if the expression is evaluated
on two branches of an if-statement, it saves space to evaluate it once before
the conditional).

Give a data-flow algorithm to determine whether an expression is very busy at
at a point. As usual, assume that you have the program graph and its basic
blocks, functions Busy_in and Busy_out, and local functions Gen and Kill.
Define in a few words what each of these represent, and how they are computed.
Is this a forward or backwards algorithm, and does it use union or intersection?