Project, Part 4

Compiling Classes

CS 212 - Spring 2004

Due: Monday, May 10, 11:00PM

Update (May 1): An error in the example program has been corrected (the types were missing on the parameter list for the Node constructor).

Updates (Apr 28):

The due date has been shifted from Friday, May 7, to Monday, May 10.
It is legal in Part 4 Bali to have an array of objects.
A class’s super class must be defined before the class.
Do not call the System.exit method. There is no reason for you to call this method since any errors are supposed to be handled by throwing an Exception (either BaliSyntexException or BaliSemanticException).
You may need to download the latest version of the SaM Simulator; earlier versions did not include the PUSHIMMPA (push immediate program address) instruction that is needed for this assignment.
Some corrections have been made to the example program that appears below.
You may want to take a look at the lecture notes (Week11 Implementing Objects.pdf and Week13 Code for Classes.pdf) and the example code that was used in lecture.

Objectives

Extend your compiler to include classes and single inheritance.

Bali Part 4

Part 4 Bali is object oriented! In other words it includes classes and (single) inheritance. See the Bali Specs for Part 4. Objects are stored in SaM's Heap. A single program can include multiple classes and multiple functions (this is different from Java where there are only classes and no functions). There is still a main function that is called automatically when a Bali program is run. Here's a sample program; this program has not yet been tested so there may be some errors.

// Sample Part 4 program that uses a Queue and a Stack
int main ( )
  {int n; Stack s; Queue q;} {
  n = 0; s = Stack(); q = Queue();
  while n < 5 do {
    s.put(n); q.put(n);
    n = n + 1;
    }
  n = 0;
  while n < 5 do {
    print s.get(); print q.get();
    n = n + 1;
    }
  return 0;
  }

class Node
  { public int data; public Node link; }
  { public Node (int data, Node link) {}
    { this.data = data;
      this.link = link;
    }
  }{}

class Queue
   { private Node head, last; }
   {}
   { public void put (int i)
       { Node n; }
       { n = null;
         n = Node(i, n);
         if head == null then head = n;
         else last.link = n;
         last = n;
         return;
       }
     public int get ()
       { Node n; }
       { n = head;
         head = head.link;
         return n.data;
       }
   }

class Stack
   { private Node top; }
   {}
   { public void put (int i)
       {}
       { top = Node(i, top);
         return;
       }
     public int get ()
       { Node n; }
       { n = top;
         top = top.link;
         return n.data;
       }
   }

Implementing Classes

A description of how classes are implemented appeared in lecture (Week11 Implementing Objects.pdf and Week13 Code for Classes.pdf). Please feel free to ask questions on the newsgroup (cornell.class.cs212), via email, during lecture, or during Office Hours.

You will need to manipulate program addresses (i.e., labels within the sam-code). To do this, use the instruction
PUSHIMMPA label
which pushes a Program Address (indicated by label) onto the stack.

Error Handling

As in the previous assignment, you are two report the two kinds of errors:

syntax errors, code that violates the rules of the Bali grammar, and
semantic errors, code that violates the rules of Bali semantics.

For example, a missing semicolon or an unmatched parenthesis is a syntax error; a type mismatch or an undeclared variable is a semantic error.

Tasks

Write a Bali compiler that translates Bali code (satisfying the Bali Specs for Part 4) into valid sam-code. You may use any of the sam-code instructions; these are summarized in SaM Summary.

You have the option of building your Part 4 compiler by extending or own Part 3 compiler or by extending the sample solution compiler. The sample solution should appear on the web in the near future.
Your compiler should handle classes as described in the Bali Specs for Part 4.
Your compiler must use an AST (Abstract Syntax Tree) as an intermediate stage between parsing and code generation.
You must provide a class called BaliCompiler (in a file called BaliCompiler.java) that serves as the starting point for your compiler.
- BaliCompiler must implement the Compiler interface (Compiler.java).
- BC.java is a main class that handles the file I/O, initializes the SamTokenizer, and calls BaliCompiler. You can use this class to test your BaliCompiler.
- BaliCompiler.java is stub version of the class you need to create. It also shows how you can set up a PrintWriter to make it easy to produce your code as a String (as required by the Compiler interface).
- BC.java makes use of SamTokenizer, Tokenizer, and TokenizerException. The most up-to-date versions of these are stored on the SaM simulator page where there are also instructions on the use of the .jar file in which these are located.
Your compiler should not produce any output either to a file or to the standard output or err file. It is OK for your program to produce such output while you are debugging, but any such debugging output must be turned off in your submitted version. The only I/O that should take place is the I/O moderated by BC.java.
Your compiler must generate sam-code that represents a valid translation of the supplied Bali program.
- Your generated sam-code should contain no comments.
- Remember to test your sam-code in the SaM Simulator.
Your compiler must also respond correctly to Bali programs that contain errors, throwing either BaliSyntaxException or BaliSemanticException as appropriate. Once an error is detected, no further processing of the Bali program is necessary.
The files you need can be found here: BaliCompiler.java, BC.java, CS212-Part4-1.jar, CS212-Part4-1.src.zip. The .jar file contains the Compiler class and the Exception classes used for error handling; the .zip holds the corresponding source files. You should not need to change these files. You must use the .jar file rather than keeping your own versions of these files. To do this
- You must add
  import edu.cornell.cs.cs212.sp2004.part3.*;
  to the top of any files that use the provided classes.
- You must also inform your Java IDE (e.g., DrJava) that you are using a .jar file. This should be straightforward (in DrJava, look look under Edit:Preferences).
You can assume the Bali programs that we use for grading do not produce runtime errors. In other words, you can assume that, for all our Bali programs that we use for grading, all subscripts are within bounds and arrays are always initialized before use.

Submission Instructions for Part 4:

Submit all of the Java files associated with your compiler. These should be placed in a single .zip file
Do not submit any of the files that we have provided. We will compile your code and run it with the reference copies posted on the website.
Do not submit .class files or any other files that are produced when your classes compile. We only want the .java files.
Make sure that your Java code compiles, even if you have trouble getting it to run properly. We will be recompiling all of your code and running it
Do not include extraneous text in your programs, such as debugging statements or superfluous comments.
Special files:
- You may include (within the .zip file) a brief file called readme.txt if there are special features or issues about your code that you need to communicate to the grading staff.
- You may also include (within the .zip file) a brief file called instructions.txt if there is anything the grading staff should know about how to run your compiler (i.e., if you have used packages, for instance).
- Please do not include these files unless it is truly necessary for you to communicate extra information to the grading staff.
Place a comment block at the top of each file that you have created. The block must give the assignment number, due date, and creator name(s) and Net-ID(s). For example,
```
/**********************************
* Assignment #0: Example format
* Date: 1/1/1111
*
* Tad Morose: tm0
* Sue Themall: st0
**********************************/
```

Bonus Work (up to 25 bonus points)

Warning: Do not spend time on the bonus work unless your compiler already performs as required for Part 4.

There are some situations in which it is important to produce very efficient machine code. For instance, efficient machine code is needed for real-time applications, for code that will be run often, and for large simulations in engineering, physics, or biology.

Consider the following simple Bali code.

x = 2 + 2;

Without any optimization, this is compiled to produce the following SaM instructions.

        PUSHIMM 2
        PUSHIMM 2
        ADD
        STOREOFF 3    // assumes x is at offset 3 from the FBR

Of course, the compiler already "knows" the value of 2+2 at compile time; there is no need to compute this value at runtime. Thus a smart compiler can generate half the instructions while still producing an equivalent result.

PUSHIMM 4
STOREOFF 3

This optimization strategy is known as constant folding.

For bonus credit, research and implement one or more optimization techniques. You can use any techniques that you want subject to the following restrictions.

You must maintain the stack frame conventions of this course.
Optimization must be done on the AST, not on the original code. In other words, your optimizations should modify the AST before code generation is done.
You must provide documentation in readme.txt to let the grading staff know either
- the source you used to find the optimization or
- an informal proof that your optimization improved performance without changing the program's behavior.

Be careful that your optimization does not break other features of Bali. Such breakage will be penalized.

Please do not discuss optimizations that you plan to implement with class member outside your own group. The intent of this bonus work is to encourage some independent research. If you have any questions about optimizations, please email or visit the course staff directly.