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



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


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;
  return y;

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.

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.


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; 
    y = 0;

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.

Consider the following code fragment.

loop while x < 5;

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:

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:, 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, see the instructions for Part 2B, below.

Part 2A (20 points)

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

Submission Instructions for Part 2A:

Feedback for Part 2A:

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

Submission Instructions for Part 2B: