Compiler Construction
Fall 1998
Final Examination

This is a take-home examination. Exams should be placed in my mailbox by
Tuesday Dec. 22, 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.

1. Consider the grammar:

                               A ->  aAa | epsilon

with one non-terminal and one terminal symbol.

a) characterize the sentences in this language.

b) Show that this language is not LL (1), by trying to build the
corresponding parse table.

c) A naive recursive descent parser for this grammar might be as follows:

                    procedure A is
                      if Next_Token = Token_a then
                          Scan;         --  skip over first a
                          if Next_Token = Token_a then
                             Scan;      --  skip over second a
                          end if;
                       end if;

Show that this does not work. (Trace the parser over some sentence in the
language) This contrived example is often used in textbooks to argue that
recursive descent is not a good parsing technique.

d) How would you write a recognizer for the sentences in this language?

2. Consider the well-known syntactic ambiguity in C:


If A denotes a type, either built-in or declared by means of a typedef, then
this expression is a cast. If A denotes a numeric variable, the expression
is a substraction. How would you handle the disambiguation of this
expression in a compiler? Describe what tree you would build, and how you
might fix it up if need be. 

a) Consider the following function in an ML-like language. Its purpose is
to apply a given operation to all the elements in a list:

      func apply (op, l, val) =
              if null (l) then nil
              else cons ( op (hd (l), val), apply (op, tl (l), val))

Give the most general type expression for this function.

b) The following function produces the partial application of a given
operation to all the prefixes of a given list (eg. the partial sums of the
first one, two, three ... elements of the list). In APL the corresponding
operator is called expansion.

        func expand (op, l) =
             if null (l) then nil
             elsif null (tl (l)) then cons (hd (l), nil)
               cons (hd (l), apply (op, expand (op, tl (l)), hd (l)))

Give the most general type expression for expand.

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

         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. Describe what needs to be done for
the function call to Sqrt and the procedure calls to Put and Put_Line.

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.