Compilation: Putting it Together

users.monash.edu/~lloyd/Seminars/2006-PLI/index.shtml Recall [block structure], stack management and code generation.
begin              --lex level 1
  real v1;             --level 1 obj 1
  real v2;             --level 1 obj 2
  proc A =             --level 1 obj 3
    
begin          --lex level 2
  real v3;         --level 2 obj 1
  proc B =         --level 2 obj 2
    
begin      --lex level 3
  real v4;     --level 3 obj 1
  ...
end{B};
B --call B end{A};
proc C = --level 1 obj 4
    
begin          --lex level 2
  real v5;         --level 2 obj 1
  proc D =         --level 2 obj 2
    
begin      --lex level 3
  real v6;     --level 3 obj 1
  A        --call A
end{D};
D --call D end{C};
C --call C end
-- LA, CS UWA
... and the SML equivalent:
let val v1 = ...;
    val v2 = ...;
    fun A() =
       let val v3 = ...
           fun B() =
              let val v4 = ...
              in ...
              end
       in B()
       end;
    fun C() =
       let val v5 = ...
           fun D() =
              let val v6 = ...
              in A()
              end
       in D()
       end
in C()
end
A simple example program
  begin
     int i;

     proc A(byValue int x) =
     begin(*A*)
        int j := 7;

        proc B(y) =
        begin(*B*)
           int k := 9;
           if ... then
               (*comment*) A(j+1)
        end(*B*);

        B(3)
     end(*A*);
     ...
     A(2)
  end.
We will now compile the command on the red line...
stages in the processing of (*comment*) A(j+1)

characters:

(, *, c, o, m, m, e, n, t, *, ),  , A, (, j, +, 1, )

lexical symbols (have regular grammars, used to create a lexer)

  id = letter (letter | digit)*
  etc.

symbols:

id(A), open, id(j), operator(+), numeral(1), close

grammar, concrete syntax (CFG, used to create a parser)

  <Cmd> -> <id> ( <Exp> ) | ...
  <Exp> -> <Exp> + <Term> | ... etc.

abstract syntax (corresponds to data-structure for parse trees)

  <Cmd> -> <id> <Exp> | ...
  <Exp> -> <Exp> <BinOpr> <Exp> | ... etc.
continued ... ... stages of processing continued

parse tree:

                 call
           ---------------
           A             +
                      -------
                      j     1

retrieve dictionary information:

  A: int->unit, addr_of_code=..., lex_level=1
  x: ref int,   offset=3 (words), lex_level=2,
     A's param, byValue
  j: ref int,   offset=4 (words), lex_level=2

annotated tree:

         call
    -----------------
    |               |
    A:int->unit     +: int*int->int
      address       |
              ----------------------
              |                    |
            deref:(ref int->int)   |
              |                    |
              j:ref int            1:int
                offset=4
                lex_level=2

code, see later ...

stack as B is running:
          ^     ^
          |     |<------------SF
          -------
          | k=9 |
          | y=3 |
B      |----.   |
       |  | .---|-----|
       v  | ra  |<----|---------ARB
       |  -------     |
       |  | j=7 |     |
       |  | x=2 |     v
A   |--|----.   |     |
    |  |  | .---|---| |
    |  -->| ra  |<-----
    v     -------   |
    |     | i   |   |
main|     | .   |   v
    |     | .   |   |
    ----->| ra  |<------------SB
          -------

... code, in B, for procedure call  A(j+1):


...                 -- x is int, by-value (input)
load R4, 2(ARB)     -- param, NB j is non-local to B
load R5, 4(R4)      -- j
add  R5, literal 1  -- +1
sto  R5, 3(SF)      -- where x will be for A

LR Env, ARB      -- load A's...
load Env, 2(Env) -- ...address environment...
load Env, 2(Env) -- ...then...
BAL RA, A        -- ...branch and link (JSR) to A
...


When this code executes, it, together with A's entry sequence, has the effect of changing the stack to ...

... stack as A is running:
          ^     ^
          |     |<------------SF
          -------
          | j=7 |
          | x=8 |
A   |-----|-.   |
    |     | .---|------>---|
    |     | ra  |<------------ARB
    |     -------          |
    v     | k=9 |          |
    |     | y=3 |          v
B   |  |----.   |          |
    |  |  | .---|-----|    |
    v  v  | ra  |<----|-----
    |  |  -------     |
    |  |  | j=7 |     |
    |  |  | x=2 |     v
A   |<-|--|-.   |     |
    |  |  | .---|---| |
    |  -->| ra  |<-----
    v     -------   |
    |     | i   |   |
main|     | .   |   v
    |     | .   |   |
    ----->| ra  |<-----<------SB
          -------

Conclusion



16 October L. Allison, School of Computer Science and Software Engineering, Monash University, Australia 3800.
Created with "vi (Linux & Solaris)",   charset=iso-8859-1