Project 5: Translation to Intermediate Code Trees

Due 11:59am Wednesday November 17th, 2004

Description

In this project you will be traversing an Abstract Syntax Tree as in Project 4 and converting it into intermediate code trees. You will implement a translator that is both modular and portable to build an intermediate representation for the MiniJava grammar.

Directions

• Read chapters 6 and 7 of Appel.
• Observe the reference implementation of the translator. It can be run with the command:

  /homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | /homes/cs352/bin/p5

  This means that your translator should accept the abstract syntax tree from standard input (System.in).
• You will need to modify your existing parser to:
  • Read in the output of P4.
  • Rebuild the Abstract Syntax Tree with type descriptors and the class environment.
  • Output the Intermediate Representation tree.
• To create the intermediate representation tree, you will need to create the following packages (refer to Appel chapter 6 for more information):
  • Frame - stack frame interface
  • Temp - abstract names for local variables
  • PowerPC - PowerPC (target architecture) instruction information
• Your Frame package should (at least) contain the following classes:
  • Frame - abstract class to be extended by the target architecture frame
  • Access - describes formals and locals that may exist in stack frames or registers
  • InFrame - indicates memory location in stack frame
  • InReg - indicates register location
• Your Temp package should (at least) contain the following classes:
  • Temp/TempList - abstract names for local variables
  • Label/LabelList - abstract names for abstract memory locations
• Your Translation program will be graded using automated scripts. Make certain that your project submission can be executed using the following commands:

  cd Project5; make; /homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | java Translate.Main

  where "inputfile.java" is the MiniJava file to be analyzed. Failure to follow this simple directory and package naming scheme will result in a zero on the project.
• Some hints are available at: Hints.
• NOTE: In previous programs, you were expected to match the output of the reference implementation exactly. In this project, while you should strive to match the output of the reference implementation, it will be possible to receive full credit on the assignment if your output is not *exactly* the same as the reference implementation, This is due to the fact that there are many possible trees that represent a correct compilation of the program.
• So, if your translator's compiled output behaves exactly the same as the reference implementation's compiled programs when executed, you will receive full credit.
• Please do not procrastinate. Start early and you should be able to finish the project well within the deadline.

Resources

If you have questions please ask either Dr. Brylow or a TA, or post a message to the class news group at purdue.class.cs352.

Hints

For each method in each class, you will create a Frame.Frame object. Since you are compiling for a PowerPC processor your frame objects will be of type PowerPC.PowerPCFrame. The variables in each method will be referenced as temporaries (Temp.Temp objects) in the intermediate code tree. In the intermediate code language a temporary is similar to a register on an actual processor. You will need to implement methods in the Frame class to allocate temporaries for variables. There are two such methods: allocFormal() (to allocate temporaries for formal variables) and allocLocal() (to allocate temporaries for local variables). Each of these methods will return a Frame.Access object which stores the name of the temporary allocated. The Frame.Access object returned will always be a PowerPC.InReg object. You will need to maintain a symbol table to bind the variable names with the corresponding Frame.Access objects.

The Intermediate Code Tree is made of objects of two main types: Tree.Exp and Tree.Stm. These classes are both abstract, and the objects in the tress will be made of objects of types which inherit from Tree.Exp or Tree.Stm.
Classes that extend Tree.Exp are : BINOP, CALL, CONST, ESEQ, MEM, NAME, TEMP.
Classes that extend Tree.Stm are : CJUMP, EXP, JUMP, LABEL, MOVE, SEQ.

Note: Tree.SEQ will be used to link together a sequence of statements. For example, if you have statements stm1,stm2,stm3. You will link them together by calling:

           SEQ(stm1,SEQ(stm2,stm3)).

For each method in each class you will create a Frame.Frame and a method body (a tree rooted at a Tree.Stm). The Frame.Frame and the body together form a fragment (in this case a Translate.ProcFrag). Each Translate.ProcFrag will be added to a linked list (called frags).

The return type of each visitor is Translate.Exp. Do not confuse this with the Tree.Exp. Translate.Exp is another abstract class, and the four classes that extend Translate.Exp are:

         Translate.Ex (when visiting an expression, i.e. AddExp)
         Translate.Nx (when visiting a statement, i.e. AssignStm)
         Translate.Cx (when visiting a conditional, i.e. GreaterExp)
         Translate.IfThenElseExp (when visiting IfStm and similar nodes).

Each of these subclasses of abstract class Translate.Exp have three methods to convert Translate.Exp objects to Tree.Exp and Tree.Stm objects :
         unEx() : converts to Tree.Exp.
         unNx() : converts to Tree.Stm.
         unCx() : converts to Tree.Stm in the form of a conditional statement.

You will use these methods to convert from Translate.Exp objects to Tree.Exp objects. For example: If you have an Translate.Ex object called "x" and need to convert it to a Tree.Stm, you will need to call x.unNx().

Testing/Debugging

The only way to find the exact structure of the tree any visitor method needs to return is to create a small test case and run p5 on it. Observe the output from p5 and recreate it with your code.

%  /homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | java Translate.Main >& out1

%  /homes/cs352/bin/p3 inputfile.java | /homes/cs352/bin/p4 | /homes/cs352/bin/p5 >& out2

% diff -w out1 out2

Reminder: see note regarding matching the reference implementation output.

Turnin

• Submit a directory named Project5 with the required programs and a Makefile. Do not submit any binaries or compiled class files.
• Submit using

  turnin -c cs352=0X01 -p project5 Project5

  on a machine in the CS undergrad "Lore" domain, where "Project5" is the name of your project 5 directory, and "0X01" is your division number.

Useful Links

• Java Language Specification
• Textbook Website
• MiniJava BNF
• Course Newsgroup

Credits

This has been adapted from Dr. Hosking's and Dr. Brylow's previous description.