Class 35: Steps in Compilation, Revisited

Held Wednesday, April 25, 2001

Summary

Today we revist the steps involved in compilation by looking at a more complex program in some more detail.

Notes

• Don't forget: We meet in 2428 today.
• The example will continue through Friday.
• Groups need to sign up for times.
• Mr. Stone will observe class next week.
• Yes, we have lab tomorrow.

Overview

• A sample program
• Lexing and parsing (elided)
• Translation to intermediate code

A Sample Program

Here is a sample Pascal program to compute the factorial of a number entered by the user.

program factorial(input,output);
  var val: integer;
  function factorial(n: integer): integer;
    function helper(n: integer; acc: integer): integer;
    begin { factorial/helper }
      if (n = 0) then
        helper := acc
      else 
        helper := helper(n-1, acc*n);
    end; { factorial/helper }
  begin { factorial }
    factorial := helper(n, 1);
  end; { factorial}
begin { program }
  write('Please enter a number: ');
  readln(val);
  write('The factorial of ');
  write(val:1);
  write(' is ');
  write(factorial(val):1);
  writeln('.')
end. { program }

Generating Intermediate Code

• Just as we've talked about before, we need to think about the larger program as a collection of smaller pieces that we then join together.
• How do we store our global variable (val)? We use a pseudo-assembler declare-integer

    .deci Val
  

  • In practice, it looks like the commands that our assembler likes are

      .local Val
      .comm  Val,4,4
    

• How do we deal with strings? We use a "declare string" pseudo-instruction

    .deci STRING1 "Please enter a number: "
  

  • Again, the actual code we'll eventually generate is slightly different.

    STRING1:
      .string "Please enter a number: "
    

• We'll continue with the write and writeln calls because they're so similar. For each of those, we need to
  • Push the minimum number of spaces allocated.
  • Push the value.
  • Push the type of value ($16 for "address of string", $259 for "integer")
  • Push the number of parameters (typically 1).
  • Call _p_write.
  • Clean up.
• We also need to generate a label for ``we're done'' because we want to jump to that label some of the time.
• So, writeln("Please enter a number: ") becomes

    push Constant(23)       # Yes, it has 23 characters
    push Address(STRING1)   # "Please enter a number: "
    push Constant(16)       # And it's a string
    push Constant(1)        # That's the only parameter
    push Address(_p_stdout) # Also need the place to print to
    call _p_write           # Write the value
    popmany Constant(5 )    # Pop five values off the stack
    JumpIfEqual Constant(0),Constant(_p_inoutres),NEWLABEL
                            # Is the result okay?
    Cal l_p_inoutres
  NEWLABEL
  

• We also have to deal with procedure calls, in which we push the parameters before calling and pop 'em off afterwards.
• More to come ...

Remaining Steps

• We'll look at the remaining steps (particularly register allocation) on Friday.