Project 3

Option 1: Implement code generation for the language features included in Project 2.

Option 2: Implement an interpreter for the language features included in Project 2.

Due Tuesday, November 16 at 11:59pm, via turnin.

Part 3 of your project involves taking the final step to enable execution of programs.

If you choose option 1, you can implement it using another tree parser. The target language will be MIPS assembly code, to be executed by the SPIM interpreter. Details about the instruction set and using the interpreter will be added here in the near future.

If you choose option 2, you will have to implement your own routines that traverse the tree to do the interpretation. This is because loop bodies, for example, must be processed repeatedly rather just a simgle time, which is all you can express in an ANTLR tree walker. Your interpreter must manage a memory for variables that is separate, allowing you to later implement procedures.

Details

This project raises a number of interesting questions/issues. Some are specific to the interpreter or compiler, while some are important to both. This section is thus subdivided into three sections.

Important details important only for interpreters

You must manage a separate memory space which in some sense models memory. Probably the easiest way is to create a Vector of Objects, which serves as your memory store. Then each variable in the symbol table gets assigned an "address", where the address is just an index into the Vector. Keep in mind that in the next project, there will be multiple scopes, and you will need something like a frame/offset pair to serve as an address.

Important details important only for compilers

To run spim on the Cities machines, just have /usr/local/public/bin in your PATH.

If you like, you can grab your own copy of SPIM and the documentation here: ftp://ftp.cs.wisc.edu/pub/spim/

Important details important to both interpreters and compilers

There are a number of questions about the semantics of the language which were left unanswered until now. Here are some, along with answers:

What happens when you use undefined values?

That is, what happens when the first line of the program is "y := x" or "write( x )" when 'x' has not yet been assigned a value? There are a number of alternatives:

The value could simply be undefined.
This could cause a run-time error, which gracefully exits the program.
This could print an error message, but then continue by using a default value (like 0 for integers, "" for strings, and false for booleans).
You could detect this error statically in the "typechecker" and flag it then.
The program could crash.

The last option is unacceptable. The first option is acceptable only if you are writing a compiler. The other options are fine for both compilers and interpreters.

How should read() behave?

Every variable that is read must be input on its own line. That is to say, the call

   read( x, s, b );

would accept this kind of input

   42
   The quick brown fox.
   t

For integers, you should read all the digits at the front of the text read (and an optional leading minus sign), and ignore everything after the first non-digit character. For booleans, you should ignore everything on the line except the first character, which should be a 't' or an 'f'. For strings, every character up to the newline should be stored in the string. For integers and booleans, you needn't worry about "bad data", for example "foo" for an integer or "x" for a boolean--I shall not test the program with bad data.

Here are some more examples (with explicit newlines to remove any ambiguity):

   42abc\n     // legal integer (42), legal string "42abc", illegal boolean
   the foo\n   // legal boolean (true), legal string "the foo", illegal int
   \n          // legal string (""), illegal boolean, illegal int

If things are listed as "illegal" then this is bad data which I will not test your program with. I tried to make these semantics as MIPS-friendly as possible.

How should write() behave?

Each value passed to write() should be written in a string form, followed by a newline after all the parameters.

Turnin information

For this project, you will turn in a directory of all your files, which should contain

A "README" file which contains:
- Your name
- Your CoC account name
- Whether you wrote a compiler or interpreter
- Summary of what works/doesn't
- Anything out-of-the-ordinary that you want the grader to know
You should use the README template.
Two scripts, which do the following:
- A script named comp which compiles your entire project. I should be able to run
```
      ./comp 
```
  and it should compile.
- A script named run takes two arguments, a "simple" code file and an input file, and runs the program. If you have written an interpreter, it might be something
```
      java Main $1 < $2    # $1 is test01, $2 is input01
```
  whereas for a compiler it might be something like
```
      java Main $1
      spim my_file.s < $2
```
  Regardless, I should be able to type
```
      ./run test01 input01
```
  and it should process test01. Do not assume "." is in my PATH.
All the source code

The command is

   turnin  prj3  directory_which_has_all_my_files

Failure to follow turnin instructions will result in a grade deduction.