CS 202: Programming Assignment 3

Assignment 3: Assignment for Topic 3, SubClasses

(this is a revision of a project created by
Prof. Cindy Norris of CS, Appalachian State University)

The goal of this assignment is to give you practice with subclasses in a setting where they are particularly useful. You will write an interpreter for a minimal machine language - MML. The general form of a machine language instruction is

label instruction register-list

label is the label for the line. Other instructions might "jump" to that label.

instruction is the actual instruction. In MML, there are instructions for adding, multiplying and so on, for storing and retrieving integers, and for conditionally branching to other labels (like an if statement).

register-list is the list of registers that the instruction manipulates. Registers are simple, integer, storage areas in computer memory, much like variables. In MML, there are 32 registers, numbered 0, 1, ..., 31.

MML has the following instructions:

L1 add r s1 s2 - Add the contents of registers s1 and s2 and store the result in register r.
L1 sub r s1 s2 - Subtract the contents of register s2 from the contents of s1 and store the result in register r.
L1 mul r s1 s2 - Multiply the contents of registers s1 and s2 and store the result in register r.
L1 div r s1 s2 - Divide (Java integer division) the contents of register s1 by the contents of register s2 and store the result in register r.
L1 out s1 - Print the contents of register s1 on the Java console (using println).
L1 lin r x - Store integer x in register r.
L1 bnz s1 L2 If the contents of register s1 is not zero, then make the statement labeled L2 the next one to execute.

We kept the number of different instructions small so that you would have less work to do. For example, there could have been other branch instructions, a negation instruction, an input instruction, and so on. But once you implement this little language, you will be easy for you to add more instructions.

L1 is any identifier --actually, any sequence of non-whitespace characters. Each statement of a program must be labeled with a different identifier. Each of s1, s2, and r is an integer in the range 0..31 and refers to one of the 32 registers in the machine that executes language MML. Here is an example of an MML program to compute factorial 6. Note that adjacent fields of an instruction (label, opcode, and operands) are separated by whitespace.

Instructions of a program are executed in order (starting with the first one), unless the order is changed by execution of a bnz instruction. Execution terminates when its last instruction has been executed (and doesn't change the order of execution).

Your interpreter will

Obtain from the user the name of a file that contains the program,
Read the program from the file and translate it into an internal form,
Print the program,
Execute the program, and
Print the final value of the registers.

This looks like a tall order, but have no fear; we provide you with a lot of the code, so that you can concentrate on the interesting use of subclasses. Follow our directions on doing the project, and the project should take 3-5 hours at most, once you have read and understood this document.

Design of the program

We provide some of the classes, provide specifications of a few, and leave a few to you. The code we give you does the dirty work of reading in a program and translating it to an internal form, so you can concentrate just on the code that executes the program.

Here are the files that you will work with. You can get them either individually or as a .zip file:

Machine.java Translator.java Labels.java Registers.java Instruction.java zipped files

Study class Machine first, for it is the heart of the program. As you look at this class and others, be conscious of the presentation --the indentation, the terse but precise method specifications, the descriptions of variables, loop invariants, and so forth. Make your code as easy to read as this code.

Studying the program

Looks at the fields of class Machine, which contain exactly what is needed to execute MML program: the labels defined in the program, the program itself in an internal form, the registers of the machine, and the "program counter": the number of the next instruction to execute. Take a quick look at classes Labels and Registers, which we give to you.

Vectors are used for the labels and the instructions of the machine because there is no limit to the size of an MML program. An array is used for the registers because there are always exactly 32 registers.

Now read method Machine.execute, which executes the program. It is a typical fetch-execute cycle that all machines have in some form. At each iteration, the instruction to execute is fetched, the program counter is incremented, and the instruction is executed. The order of the last two instructions is important, because an instruction (e.g. bnz) might change the program counter.

Finally, study method main.

Class Translator contains the methods that read in the program and translate it into an internal form. Very little error checking goes on here. For example, there is no checking for duplicate label definitions, for the use of a label that doesn't exist, and for a register number not in the range 0..31.

Class Instruction and it subclasses

All the programming that you do has to do with class Instruction and its subclasses. The specification of class Instruction has been given to you --open file Instruction.java and look at it. This class is abstract, because it should not be instantiated. Method execute is abstract, so that every subclass has to implement it. Every instruction has a label and an operation --that is exactly what is common to every instruction. Therefore, these properties are maintained in the superclass of all instructions.

You first job is to complete the methods in class Instruction --this may require you to add some fields, which should be protected, so that they are accessible in subclasses.

Now create a subclass of Instruction for each kind of MML instruction and fix method Translator.getInstruction so that it properly translates that kind of instruction. WE STRONGLY SUGGEST THAT YOU DO ONE INSTRUCTION AT A TIME AND CHECK IT OUT THOROUGHLY, BEFORE PROCEEDING TO THE NEXT! For example, your first program will consist only of add instructions; after instruction add is checked out and works correctly, work with add and subtract instructions, etc. As you do this, you will see that each successive class can be written by duplicating a previous one and modifying it.

For each instruction, the subclass needs appropriate fields, a constructor, method toString, and method execute; toString and execute should override the same methods in class Instruction.

Start with the add instruction, because the code for translating it is already there --in method Translator.getInstruction. This code will give an idea what the constructor for the subclass will look like. Initially, the program will not compile because there is no class for the instruction add. Once that class is suitably written, the program will compile.

After you finish writing a subclass for an MML (except for add), you have to add code in method Translator.getInstruction to translate that instruction. The code for translating add should help you with this.

This should be enough information for you to do this project. However, if you run into trouble and have a question, contact a grader, Ezick, or Gries immediately! Do spend some time investigating the problem you have encountered. Don't waste time floundering, but get help.

Last Modified: Wednesday, February 06, 2002 11:56:03 AM