Assignment IV

Due date March 27.


The goal of this assignment is to generate intermediate code from an
analyzed tree for a small subset of Ada. THe subset includes declarations
for integers, one-dimensional arrays of integers with static bounds,
functions with integer arguments, and simple control structures: if-statement,
while-statements, loop statements over ranges, and return statements.
Expressions involve the four basic operations and indexing. For example, you
should compile code for:
      function Fib1 (N : Integer) return Integer is
      begin
         if N = 0 then
            return 0;
         elsif N = 1 then
            return 1;
         else
            return Fib1 (N-1) + Fib1 (N-2);
         end if;
      end Fib1;
      
as well as:

      function Fib2 (N : Integer) return Integer is
         Prev1 : Integer;
         Prev2 : Integer;
         Fib   : Integer;
      begin
         if N = 0 or else N = 1 then
            return N;
         else
            Prev1 := 0;
            Prev2 := 1;

            for I in 2 .. N loop
               Fib := Prev1 + Prev2;
               Prev1 := Prev2;
               Prev2 := Fib;
            end loop;

            return Fib;
         end if;
      end Fib2;

as well as

      function Fib3 (N : Integer) return Integer is
         Prev : array (0..100) of integer;

      begin
         if N = 0 or else N = 1 then
            return N;
         else
           Prev (0) := 0;
           Prev (1) := 1;

           for J in 2 .. N loop
              Prev (J) := Prev (J-1) + Prev (J-2);
           end loop;

           return Prev (N);
         end if;
      end Fib3;
             
The code to be generated consists of simple three-address instructions (also called quadruples): that specify one or two operands, a target result, and an operator. The operands and result are either simple variables appearing in the source program, or temporaries generated to simplify expressions. Control structures are expanded into simple goto's, and labels appear as separate "quadruples" . The intermediate code has the same semantic level as assembly, which is to say that one can map each quadruple into one assembly instruction. For example, the instruction in the loop of Fib3 might be expanded into:
                        T1 := J-1;
                        T2 := Prev (T1);
                        T3 := J-2;
                        T4 := Prev (T3);
                        T5 := T2 + T4;
                        Prev (J) := T5;
We treat indexed retrieval as a quadruple. We treat indexed assignment as a quadruple as well, where the operands are the index and the right-hand side, and the target is the array.

The above is a readable form for the quadruples, for debuggin purposes. Internally, the generated code is just an array of records, where each record has the indicated four components.

Finally, we also want quadruples to encode declarations. For scalar variables we only need a name and a type (which in our case will always be integer). For arrays, assume that the lower bounds is always zero, in which case we need only an upper bound and a component type (which is also integer).

If you choose to do the final part of the project, namely assembly generation, in another language, then you can use the quadruples as input to the last pass of your compiler.