CSE 142 Spring 2002

Homework #5

PL142 Compiler

Due: Electronically, 11:00pm, Tuesday, May 14;
written report due in lecture, Wednesday, May 15.

Purpose

This assignment is more open ended than previous assignments. Many questions may arise about exactly what to do. For the most part, the answers are up to you, keeping in mind the following set of assignment goals. If what you're doing is consonant with these goals, then it's okay with us.

Develop a better understanding of what a compiler (e.g., Java) is doing by building one.
Make sure you're comfortable learning about new classes by reading the Sun Java documentation.
Further experience using everything we've learned in class so far.
Further experience designing classes (in particular, the Compiler class).

Assignment Overview and PL142 Syntax

You'll be implementing a compiler for the PL142 programming language. A quick look at a sample PL142 program and the output produced by it when run using our version of the PL142 compiler might help understand the rest of this document more easily.

PL142 is a very simple (to the point of being rather useless) language. It has only a single data type, INTEGER. The syntax to declare a variable is

    INTEGER variablename;

for example, "INTEGER nextInt;". It is an error to declare a variable more than once, and an error to try to use a variable that has not been declared.

Besides declarations, PL142 has only two kinds of statements. The print statement has syntax

    variablename;

for example, "nextInt;". When executed, this causes the current value of the variable to be printed.

The only remaining statement is one that binds a name to a new value formed by an expression containing a single binary operator:

    targetvariable = leftoperand <op> rightoperand;

Here "<op>" is one of '+' or '*', to represent addition and multiplication respectively. targetvariable must be the name of a previously declared variable. The two operands may be either the names of previously declared variables, or else INTEGER literals - strings of consecutive numeric digits ('0' through '9').

PL142 has no loops. There are no methods. There are no expressions except those containing a single binary operator. There's nothing except what is described above and "//" style comments (which are invisible to your compiler, for reasons explained below).

Compiling and Executing PL142 Programs

Your compiler must do the following. (The next section describes the software that will help you do these things.)

Examine each line of the PL142 program to understand what it means (we call this "parsing"), or to print out error messages useful to the PL142 programmer if the statement doesn't mean anything in the PL142 language.
For each variable declaration encountered, update a collection class object (we call this the "symbol table") to represent the fact that a new name has been created in the program and a new binding between that name and an instance of PL142's only data type, INTEGER (which is equivalent to the Java class BigInteger).
For each executable statement encountered, create the information you will need to execute that statement later, if no errors are found anywhere in the PL142 program when you compile it. (This is called "code generation".) That is, when you're done compiling, you'll have saved an ordered list representing what the statements of the PL142 program are trying to do. (Normally this list would be written to a file. For instance, for the real Java compiler, this list is the .class file. For C and C++ compilers, this list is (more or less) the .exe file. For your PL142 compiler, though, the list is just a collection class object.)

Those steps are what every compiler does. Your compiler also does one more thing:

Assuming compiling occurred without errors, you now run the program by going through the saved list of statement meanings and "executing" them.

This function isn't really part of what a compiler is, but we've included it as part of the PL142 compiler for simplicity. (The point being that by the time you're running the program, "compiling" is over.)

Some Software Details

You'll be provided with four Java source files (Compiler.java, Scanner.java, Statement.java, and Variable.java) implementing the following four classes.

Scanner is a class that can provide the next "token" in the PL142 program - the next String from the program text that is of interest to the compiler. A Compiler object (described below) creates a Scanner object and uses it to read the PL142 program token by token (by calling the Scanner's hasNextToken() and getNextToken() methods).

Variable is a class used to represent both variables declared in the PL142 program and INTEGER literals (e.g., 123). Each object of this class has two properties, a String name and a BigInteger value. (BigInteger is a Sun Java API class. You'll have to read the documentation to find out more about it, but basically it's an integer, except that unlike int it can hold integers of virtually unlimited size.) The PL142 data type INTEGER corresponds to the Java class BigInteger.

Statement is a class used to represent the PL142 print and assignment statements. When used for print statements, it contains a reference to a single Variable object (the one to be printed, of course). When used for assignment statements, it contains a reference to three Variable objects - the one to the left of the "=" and the two operands. In this case, it also holds an int whose value indicates whether to add or multiply when the statement is executed.

Finally, the Compiler class is the compiler. It has two main methods, compile() and run(). compile() should scan the PL142 program, preforming the steps listed in the previous section to convert it into something that can be executed.

Downloading the Skeleton Code

Download the four .java files plus the sample PL142 program (testProgram) using one of these methods:

HW5.jar
HW5.zip
Download each file separately. A link to each is included in the text above.

Running the Skeleton Code

To begin with, note that the skeleton code has been largely disabled by the removal of almost all of the Compiler code and some of the Statement code. This means that if you just run the skeleton code, it won't do much. (Your job is to turn it into a working compiler.)

There are at least two ways to run the code as you work on it, and since there are three possible tools you might be using, there are at least six different, cogent approaches. Each of these is similar to a method from HW4, so look at that assignment for mechanical details if they're not familiar to you by now. The rest of this section describes just what the approaches are.

One thing you can do is use BlueJ or Jeva to create a Compiler object. It requires a String argument. If that argument is null, the PL142 program will be read from the keyboard. Otherwise, the argument should be the name of a file containing the PL142 program to be compiled. Once you've created the Compiler object, invoke its compile() method. If it returns true no errors have occurred, and you should invoke its run() method to execute the compiled code.

Another thing you can do is invoke Compiler.main(), which is a driver that does all of the above for you. It takes a similar argument (null or the name of a file). See this page for an explanation of main() and how to invoke it.

Other Rules

You can modify any of the skeleton code you want to.
Your compiler should correctly compile and run an error-free PL142 program. Note that this means any error-free PL142 program, not just the sample program.
Your compiler should not compile or run a PL142 programs that contains syntax errors - statements that do not follow the rules for PL142 programs given above. (The PL142 program can still have bugs, of course, just not syntax errors.)
If your compiler is asked to compile a PL142 program with syntax errors, it would be very nice to print error messages that would help the PL142 programmer debug his or her program. If that's too much implementation work, it would be nice (but not "very nice") to at least halt the compiler gracefully. Finally, it would be arguably minimally acceptable to have the compiler crash when asked to compile an incorrect PL142 program, so long as it works correctly for a correct one.

How to Proceed

Look at the skeleton code for Compiler, Variable, and Statement. (You shouldn't need to look at Scanner - you can if you want to (you can even modify it if you want to, but that voids your warrantee).)
Re-read this assignment writeup.
If you're confused about what Scanner does, invoke Scanner.main() and type at it. It will print out the tokens returned by calls to getNextToken() as you hit enter on each line. (It also works to pass the name of a file to Scanner.main() - it will print out each token it finds in the file.) Note that you can create "end-of-file" on a "Command Prompt" window by typing ^Z (control-Z). (I don't know how to do it in BlueJ.)
Now try writing out the code for one Compiler method in pseudo-code - use whatever editor you use to write Java, but instead of worrying about all the details needed to write a working Java program right away, instead write part-Java and part-English (or whatever language you like). Use English to express ideas that are simple to state in English but are too complicated for you to see how to write in Java right away. Use Java where it's easy and natural enough to do so. The idea is to write out the large-scale structure of the method this easier way before moving on to refine it into pure Java. Try to write the entire method in pseudo-code before worrying about refining any one piece.
Using Exercise 1 from HW4 as an example, my initial pseudo-code might look like:
```
    while there is an unvisited Rectangle in the data HashSet {
	Rectangle nextRect = the next rectangle from the HashSet;
        add a reference to that rectangle to the result ArrayList;
    }
    dataSource.registerResult( resultList );
```
Only that last line is actually Java.
Once you have the entire method written out, it should be the case that you can work on turning it into Java by working on one English phrase at a time, without worry about the other phrases. (This is the ideal, although I have to admit that sometimes as you refine you realize there are interactions among the pieces you hadn't thought of at first.) For my example, my first refinement might be:
```
    iterator = dataSet.iterator();
    while ( iterator.hasNext() ) {
	Rectangle nextRect = the next rectangle from the HashSet;
        add a reference to that rectangle to the result ArrayList;
    }
    dataSource.registerResult( resultList );
```
Keep doing this until it's all Java.
One thing to look out for in this assignment is that you might (should, I think) want to add some methods to the Compiler class to help you with your code. Writing the intial pseudo-code should help identify what would be useful - if the same "idea" comes up a few times in English, or if some line of English describes a simple idea that you guess will nonetheless result in a lot of Java code (so that it would be easier to read the final Java code by just having a method invocation there than the long block of code required to actually get it done (even if the method is invoked only once)), then feel free to create a new method.
Use office hours - we all much prefer seeing people to sitting in the office waiting.

Additional Documentation

Sun documentation
Javadoc documentation on HW5 and DataSource classes. Note that the documentation for Compiler is for a sample solution the staff wrote, not the skeleton code. It's included so that you can see the interface used in one implementation of the compiler, in case that helps.

Turning in the Completed Project

Use this turnin form.

Written Report

In lecture on Wednesday, May 15, you must turn in a short (no more than one page) written report about your project. Include your name, section, homework number and date at the top. If you didn't get the program finished, describe what still does not work, and your best guess as to what is needed to fix it. Whether or not you finished it, describe the most important things you learned from this project, which could be new ideas that you have never seen before, or misconceptions that you had that the project helped you straighten out. If what a real compiler is still isn't quite clear to you, let us know about that as well.