Lab 11

Hand Translations A

Before Starting

Please navigate to cs.montana.edu/survey and fill out the class survey before starting this lab.

Objectives

The primary objective of this lab is to continue your familiarization with the process of translation. To this end you will be required to do some hand translations of mPascal programs into machine language at level A functionality. Remaining time can be spent on your project.

Remember!

Remember that the primary reason for the laboratories is to learn. Therefore, be sure to ask the TA whenever you have problems. The labs are not quizzes.

Preparation

You will need the mMachine machine language definition at your disposal. You will also need a Word document with your team names at the top.

Notes

Note 1

Your main task here is to translate procedures and functions. We have gone over the translation of procedures pretty thoroughly in the lecture. The main points you need to remember are:

Point 1 -- Branch Around Procedures and Functions : Since code is generated in sequential order, there must be a branch inserted to get around the code for procedures and functions when the main program first starts executing. It is assumed that program execution will start from the top when the translated program is actually run, so a jump instruction must be executed to force program execution to continue with the code that is the translation of the begin block for the main program.

Point 2 -- Procedure and Function Declaration: The point at which a procedure definition is first encountered requires symbol table calls to put the name of the procedure and its attributes into the symbol table and then to create a new symbol table on the top of the stack for the new procedure. All of the new procedure's parameters and variables (along with their attributes) must be placed into this new table.

Point 3 -- Activation Record Initialization Time. Consider the begin block of a procedure (or function). This is the entry point to the procedure, the code that is to start executing when this procedure is called. At this point the compiler must generate special IR related to starting a procedure running, such as dropping the label for the procedure and completing the setup of the activation record on the stack for this procedure (the initial part of the activation record setup for this procedure is done at the point of call).

Point 4 -- Procedure End: When the end of a procedure is reached, actions must be taken to return to begin the process of removing the activation record from the stack for this procedure (the rest is done after returning to the point of call) and returning to the point of call.

Point 5 -- Main Program Code Start: The label generated in point 1 must be dropped here. This is to ensure that a jump can be made from the start of the translated code around any intervening procedure and function code to this part of the program, which is to be where execution starts The activation record for the main program must also be constructed at this point..

Point 6 -- Procedure or Function Call: A procedure (or function) call requires semantic actions that generate code to set up the calling sequence properly, to start the construction of the activation record for the called procedure, to put the actual parameters into the activation record for the called procedure, and then to make the actual jump to the procedure.

Point 7 -- Return from Procedure Call: Upon returning from the call, code must be present that removes the rest of the activation record from the stack that was started for the called procedure. The parameters in particular may need to be copied from the stack into the actual parameter locations for some programming languages. This will not be true of your project if you implement reference variables as they should be (with an address).

Point 8 -- Return from Function Call: This is similar to point 7. However, functions are slightly different than procedures throughout in that somehow the function return value must be left on top of the stack after return from a function call. That is, even after the activation record for a function is completely removed, the function return value must be the top stack element.

Note 2

When generating the code that sets up the activation record for a procedure, you must have a model of the activation record in mind. There are many different possibilities. The main things to remember are:

decide on a model, and then stick with it so that the activation records have a common format and the compiler generates code to construct and delete activation records in the same manner at every relevant point in your compiler.
remember that the first part of an activation record needs to be constructed by code generated by the compiler at the point of call; this translated code is responsible, for example, for placing the actual parameters into the activation record. The second part of the activation record needs to be constructed by code included by the compiler when it is translating the begin block of the procedure.
remember, too, that the activation record must be deconstructed in similar fashion -- partly by code in the called procedure and partly code in the calling procedure after the return from the call.

The model we gave in class looked like:

 ____________________________  < sp points here 
| local variable n           | 
|____________________________| 
|     . . .                  | 
|____________________________| 
| local variable 1           | 
|____________________________|  
| caller's return address    | 
|____________________________| 
| actual-formal parameter m  | 
|____________________________| 
|     . . .                  | 
|____________________________| 
| actual-formal parameter 1  | 
|____________________________| < display register points here 
| old display register value | 
|____________________________|

where the blue part is constructed code generated by the compiler at the point of call, and the green part is generated by code inserted by the compiler at the point at which the begin block of the called procedure is compiled.

Note 3

The translation of functions just has one extra twist. The value returned by the function must be placed on top of the stack of the calling procedure or function. Consider a statement such as

y := 3 + f(x);

in which f is a function. Then to get your stack based arithmetic to work, you would need to push the 3, push the result of f(x), and then do an adds. So, if you can get the function, when it is called, to compute the value of f(x) and then leave that value on top of the stack when it returns, everything will work perfectly. Remember that the top of the stack in this case is going to be below the activation record of the called function. That is, when the function terminates and its activation record is removed, as part of this process the remaining stack must be grown by one and the functional return value placed there. That is, you can conceive of your activation record looking like

 ____________________________  < sp points here 
| local variable n           | 
|____________________________| 
|     . . .                  | 
|____________________________| 
| local variable 1           | 
|____________________________|  
| caller's return address    | 
|____________________________| 
| actual-formal parameter m  | 
|____________________________| 
|     . . .                  | 
|____________________________| 
| actual-formal parameter 1  | 
|____________________________| < display register points here 
| old display register value | 
|____________________________| 
| function return value      | 
|____________________________|

To Do

Choose some of the following to translate into mMachine code. You won't have time to do them all.
Be sure to do your hand translations with the express purpose in mind of determining how you will get your compiler to generate code for procedures and functions according to a model of an activation record you have in mind. In other words, you will miss the point of the lab exercise if you just "get something to work" without considering at the same time how you could get your compiler to do the same thing.
For each program, construct the symbol table with offsets for the variables and use display registers to address the variables in the program. Show how the stacked symbol tables grow and shrink during compiling.
After translating each program, run it on the mPascal emulator.
Note: You will not be given a score on how well you do the translations or even on whether you finish. The point is to actively think and learn how to translate procedures, functions, and parameters on your own based on your years of programming experience. You aren't even required to do the translations in the order of the programs presented below. If you feel reasonably confident with your ability to do a translation, you can try some of the later and more challenging ones first. For example, if you can translate programs 3 and 4, you certainly can translate programs 1 and 2. On the other hand, don't tackle the tougher ones first if you aren't ready.
Once you are confident that you know what is going on, you can use the time to work on your compiler instead of performing more hand translations.

Feel free to modify this code if it is not up to the latest μPascal grammar.

Program 1


program Program1;    
  var N : Integer;
  
  procedure Fred;
    begin
      N := N + 1
    end;
    
  begin     
    Read(N);
    Writeln(N);
    Fred;
    Write(N)
  end.

Program 2


program Program2;
  var I: Integer;
      N: Integer;
      
  procedure Fred(A: Integer; Var B: Integer);
    var I: Integer;
    begin
      I := 5;       
      A := 10;       
      B := 20;       
      Write(I, A, B);     
      end;
      
  begin    
    I := 0;     
    N := 1;     
    Write(I, N);     
    Fred(I, N);     
    Write(I, N)   
    end.

Program 3


program Program3;
  var N: Integer;
  
  function factorial(N: Integer): Integer;
    begin      
      if N = 0 then         
          factorial := 1      
        else         
          factorial := N * factorial(N-1)    
      end;
  begin     
  Read(N);     
  If N >= 0 then       
      write(factorial(N))     
    else       
      write(-1);  
    end.

Program 4


program Program4;
  var I: Integer;       
      N: Integer;
    
  procedure Fred(A: Integer; Var B: Integer);
    var I: Integer;
    
    procedure Doit;
      var X: Integer;
      begin         
        X := 0;        
        I := -5;         
        N := -10;         
        Write(X, I, N);       
      end;
    
    begin       
      I := 5;       
      A := 10;       
      B := 20;       
      Write(I, A, B);       
      Doit;       
      Write(I, A, B);     
    end;
  
  function Why: Integer;
    begin       
      Why := 1     
    end;
    
  begin     
    I := 0;     
    N := 1;     
    Write(I, N);     
    Fred(I, N);     
    Write(I, N);     
    Write(Why);   
  end.

To Turn In

Turn your Word document in to the Lab 12 dropbox with your hand translations, symbol tables, and runs for each program. After you have done this, use the remainder of your time to work on your project.