Project, Part 2

Compiling Simple Bali Programs

CS 212 - Fall 2007

Due: Thursday, September 27, 11:59PM for Part 2A
Due: Thursday, October 18, 11:59PM for Part 2B

Objectives

• Practice with software design and software testing.
• Learn about parsing with a Java-like language called Bali.
• Write a compiler in Java that generates SaM-code for a Bali program.

Groups

We encourage you to participate in a group for this and future CS 212 assignments.  This alleviates some of the programming work and provides a chance to improve your group negotiation/participation skills, something that will be useful for future courses.  Groups of size one, two, or three are allowed.  If you wish, you can use the newsgroup (cornell.class.cs212) to look for partners.  Keep in mind the guidelines for Working with Partners specified in the Course Info (e.g., you may not change or drop partners once you have started working on the assignment, but you can change partners between assignments).

Bali

We are going to be using a subset of Bali for this assignment. This subset allows only a single function (the main function) and has just two data types (int and boolean). The subset includes variables, expressions, statements, and some simple I/O. Here's a sample program:

// Sample program that does nothing very interesting
int main ( ):
  int x,
  int y
  :
  x = 2;
  if x > 1 then y = x;
  else y = 1;
  endif
  return y;
end

The specifications for the part of Bali being used for this assignment appear in Bali Specs for Part 2.

Allocating, Assigning, and Retrieving Variables

You must use relative addressing for this assignment. This will prepare you for implementing functions (in Part 3); the implementation of recursive functions requires relative addressing.

• To allocate space for variables (including a return variable), adjust the SP "up" the stack with ADDSP value.
• To store a value into a variable (i.e., to assign), use STOREOFF address.
• To retrieve a variable's value, use PUSHOFF address.
• To return a value (i.e., to clean up at the end of your main function), use ADDSP value to move the SP "down" to 1.

The Symbol Table

You need a strategy for remembering (1) where each variable is located and (2) the type of each variable (for this part of the project, either boolean or int). To do this, you should use a symbol table. You must explicitly create a symbol table within your compiler. Consider using java.util.HashMap to implement your symbol table.

Reading

Read the online chapter on Looping and Branching in SaM.  You'll need to understand the way that Labels and Jumps work to complete this part of the project.

Generating Code for an IF-statement

This section is similar to some of the material in the online chapter, but it uses an example closer to the current version of Bali.  Consider the following code fragment.

if x>2 then 
    y = 8; 
else 
    y = 0;
endif

As we generate the code, we use the symbol table to determine (1) that x and y are both integers and (2) the locations of x and y (say, offset 2 for x and offset 3 for y). 

To execute the if-statement, SaM first needs to evaluate a condition, which is placed on top of the stack, before jumping to the correct portion of the sam-code. To evaluate the condition x > 2, you must retrieve the value of x and then push the value 2. The top of the stack will hold the result of evaluating the condition. By calling GREATER, SaM will push 0 (false) or 1 (true), depending on the results of the comparison  (in this case, the result is 1).

// Check if x > 2
PUSHOFF 2    // push the value of x (Vbot)
PUSHIMM 2    // push the value 2 to compare with x (Vtop)
GREATER      // Push result of (Vbot > Vtop) to top of stack

Now that you have accounted for the condition part of the if-statement, you must jump to an appropriate instruction. Calling JUMPC t will move to the label t if the condition is true. Otherwise, SaM will continue executing sam-code because the condition was false. The sam-code below finishes the example. A block of sam-code for the case when x > 2 is true is labeled as trueLabel, though we could have used another name. In addition, when the if and else clauses finish, SaM needs to move to the statement after the entire if-statement, so we have provided the label continue to finish the remaining program.

// Process if statement
JUMPC trueLabel // check if result is true (1) or false (0)
PUSHIMM 0       // false: push the value 0
STOREOFF 3      //        store the value 0 for y
JUMP continue   //        continue with remaining program
trueLabel:      // true:
PUSHIMM 8       //        push the value 8
STOREOFF 3      //        store the value 8 for y
JUMP continue   //        continue with remaining program
continue:       // continue with program

The code above is a bit redundant. You may remove the second JUMP continue statement since SaM will “fall through” the label after analyzing the block labeled trueLabel.

Generating Code for a WHILE-statement

Again, this section is similar to some of the material in the online chapter, but it uses an example closer to the current version of Bali.  The following steps are necessary for a while-statement.

• Evaluate the while-statement expression (called the condition).
• If the condition is true, execute the statements within the while-statement body. After the body has executed, jump to the code that evaluates the condition
• If the condition is false, jump to the statement that follow the while-statement.

Consider the following code fragment.

x=1; 
loop while x < 5;
   x=x+1;
endloop

You need one label to jump to when the loop is done (say, done) and another label to jump to when re-evaluating the condition (say, loop). The fragment leads to the following sam-code.

PUSHIMM 1      // push 1 on the stack
STOREOFF 2     // store the value 1 for x 
loop:          // label for the start of the loop
PUSHOFF 2      // retrieve the value of x
PUSHIMM 5      // push the value to compare x with
LESS           // is x < 5 ? push 1 if so; otherwise, 0
NOT            // negate the previous test
JUMPC done     // if not (x < 5), do statements after done
PUSHOFF 2      // retrieve the value of x
PUSHIMM 1      // push 1 onto the stack
ADD            // add 1 to the current value of x
STOREOFF 2     // store the new value of x
JUMP loop      // repeat the loop
done:          // continue with remaining program

You may choose arbitrary label names, though you should try to choose names that indicate their purpose. Be aware that a single program can contain multiple if- and while-statements, so make sure that you don't re-use labels.  One way to ensure that all labels are unique is to use a counter written into each label and then incremented.

Error Handling

For this assignment, we will not be testing your compiler's response to errors in supplied Bali programs; all of our test cases for grading will be legal Bali programs. You may, however, want to think about error handling now so that you won't have to rewrite your code when working on Part 3. There are two kinds of errors that can occur in Bali programs:

• 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.

Rather than printing an error message to System.out (or System.err), errors in supplied Bali programs can be handled most clearly and cleanly by using exceptions. We have supplied exception classes corresponding to the two kinds of errors that can occur:

• BaliSyntaxException for syntax errors,
• BaliSemanticException for semantic errors, and
• BaliException, an abstract root class for both the syntactic and semantic exceptions.

BC.java, the main program that runs your compiler, is designed so that it catches BaliExceptions and then prints the exception's message. For more information on BC.java, see the instructions for Part 2B, below.

Part 2A (20 points)

Note that Part 2A is due before Part 2B.

• Post a brief message on the course newsgroup cornell.class.cs212. In the subject line, enter the following: 
                                  Part2A: your netID

This group is monitored by the course staff and is intended for both questions and discussion.  You are welcome to ask questions about the project (and answer questions, if you want), but please do not post homework solutions or partial solutions.  If you post a question, use a meaningful subject line.

• Submit a Design Document describing the design that you plan to use for your compiler.  Your design document should consist of a high-level, brief, and very-clear description of your approach followed by a concise description of each component explaining what it is supposed to do and how it will do it.  Include a diagram of the AST that your compiler will produce when it compiles the Bali program at the beginning of this write-up (the program labeled "Sample program that does nothing very interesting"). 
   
• Submit a Testing Strategy document that outlines how you plan to test your compiler to ensure that it satisfies the Bali requirements and has no bugs.
   
• Submit an ASCII text file called BadCases.txt which contains at least 10 examples of the types of errors that might occur in a Bali program (a program based on Bali Specs for Part 2).  Five of these examples should be syntax errors and five should be semantic errors.  Use the following format (but think up your own bad cases).

// Case 1 (syntax): Missing semicolon
int main ():
  int x 
  :
  x = 2
  return x;
end
  
// Case 2 (semantics): Wrong return type
  int main ():
  int x 
  :
  x = 2;
  return true;
end

These test cases can be used later for Part3 where one of your tasks is to have your compiler respond reasonably to errors.

Submission Instructions for Part 2A:

• You should submit 3 files: DesignDocument, TestingStrategy, and BadCases.txt.  DesignDocument and TestingStrategy can be .doc, .pdf, or .txt files.  If you use a different format then it is likely that we will be unable to read it.
• Make sure you label each file (at the top of the file) giving the assignment number, due date, and creator name(s) and Net-ID(s). 

Feedback for Part 2A:

• Each group will meet briefly with CS 212 staff to discuss their work on Part 2A.  
• Scheduling for this meeting will be done via CMS.  Instructions for setting up these meetings will be made available as soon as we work out the logistics.

Part 2B (80 points)

Write a Bali compiler that translates Bali code (satisfying the Bali Specs for Part 2) into valid sam-code. You may use any of the sam-code instructions; these are listed in the Sam Design Document. 

• You must use relative addressing.  Do not generate any code for the FBR. For this assignment, the FBR stays at zero and should not be changed.
• Your compiler must use an AST (Abstract Syntax Tree) as an intermediate stage between parsing and code generation.  
  • The entire AST must be completed before code generation begins.
  • The different node types of the AST should correspond to separate classes.  Note though that all of the AST classes should be subclasses of a single AST interface or single AST abstract class.  (For an example, see SimpleAST.java where an abstract class  is used.)
• Your compiler must use a symbol table to keep track of variable locations and variable types. For this assignment, there are just two types: int and boolean.
• 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, an interface that we provide).
  • We provide the class BC.java, a main class that handles the file I/O, initializes the scanner (Scanner212.java, another class that we provide), 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).
• Your compiler should not produce any output either to a file or to the standard output or err file. The only I/O that should take place is the I/O moderated by BC.java.
• You must generate sam-code that represents a valid translation of the supplied Bali program.  Remember to test your sam-code in the SaM Simulator.
• For this assignment, all of our test cases will be legal Bali programs, so it is not necessary to deal with Bali errors. (Although, as mentioned above, you may want to deal with such errors now to avoid code rewriting later.)
• 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
  *
  * Don Key: dk0
  * Liz Ard: la0
  **********************************

Submission Instructions for Part 2B:

• Detailed submission instructions will be placed online as the due-date approaches.