CPSC 411 - Lab Notes - 03-31 - Intermediate Representation

We are now at the third stage of the compilation process. We have successfully changed our character input to tokens (lexing), verified the syntax (grammar rules in YACC) and created an abstract syntax tree (methods for each yacc grammar rule.) Our next stage is to transfrom the AST into an intermediate representation tree. This requires writing a "check" method for each class in the AST.

AST to IR

We can summarize the major differences between AST and IR in the following table:

Level and Offset

Levels equate to scope. Beginning at zero it increments at each new scope and decrements at each remove scope. Offsets equate to a numbering of the variables. For variables they start at 1 and reset at each new scope. Removal takes them back to the previous amount. For arguments we start at -4 and decrement for each argument.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19  
20
21
22

var i:int;
var j:int;
fun f(a:int):int
{ var i:int;
   begin
    read i;
    return a+i;
  end
}
var x:real;
begin
  read i;
  j:= i+5;
  { var j: real;
    begin
      read j;
      x:= j+2.5;
      print x;
    end
  };
  print f(j);
end

i set to (0,1)
j set to (0,2)
a set to (1, -4)
i set to (1,1)

i is (1,1)
a is (1,-4);
i is (1,1)

x set to (0,3)

i is (0,1)
j is (0,2), i is (0,1)
j becomes (1,1)

j is (1,1)
x is (0,3), j is (1,1)
x is (0,3)


j is (0,2)

Overloading of builtins.

Note that in lines 13 and 17 in the above program, we have the operator '+' used with two different types. In line 13, it expects two arguments of type 'int' and returns and 'int'. In line 17, it expects two arguments of type 'real' and returns and 'real'.

You must handle this overloading be either performing a large if/elif statement in your checking of the apply statement, or by allowing overloading of functions in your symbol table. Either is acceptable, the latter is more elegant :)

Last modified: Mon Mar 31 15:26:14 MST 2003