CSE 304: Principles of Programming Languages

Fall 2008

Homework #1

Due: Wed, Sep 24

This is a programming assignment. You are expected to write a Java program that implements an interpreter for a simple stack-based assembly language. The program, called Interp.java should take input from standard input (System.in) and write output to standard output (System.out). This exercise is intended to be a mild test of your Java programming skills, and have you start thinking of issues related to programming language principles as well.

The program's input consists of a sequence of instructions for a stack machine. This machine has no general purpose registers. All data is kept on a stack, and the machine has instructions to manipulate the top (few) entries on the stack. The machine manipulates only integer data. Each instruction may have an optional label.

The instructions of this machine and their meaning are given below.

ildc num: push the given integer num on to the stack.
iadd: pop the top two elements of the stack, add them, and push their sum on to the stack.
isub: pop the top two elements of the stack; subtract the second popped value from the first popped value, and push the result on to the stack.
imul: pop the top two elements of the stack, multiply them, and push their product on to the stack.
idiv: pop the top two elements of the stack; divide the first popped value by the second popped value, and push the result on to the stack.
dup: push the value on the top of stack on to the stack (i.e. duplicate the top-most entry in the stack).
swap: swap the top two values on the stack. That is, if n is the top-most value on the stack, and m is immediately below it, make m the top most value of the stack with n immediately below it.
jz label: pop the top most value from the stack; if it is zero, jump to the instruction labelled with the given label; otherwise go to the next instruction.
jnz label: pop the top most value from the stack; if it is not zero, jump to the instruction labelled with the given label; otherwise go to the next instruction.
jmp label: jump to the instruction labelled with the given label.

The input is an assembly program, i.e., a sequence of instructions. Each instruction may be preceded by an optional label and a semi-colon (":"). A label is a sequence of alphabetic characters or numeric characters, beginning with an alphabetic character. An integer num is a sequence of numeric characters, optionally preceded by a minus ("-"). The instructions in the assembly language should always be in lower-case.

The label may be separated from the following instruction by a sequence of zero or more whitespace (blank, tab, newline) characters. An instruction and its argument must be separated by a sequence of one or more whitespace characters. In the examples below, each instruction is on a line of its own; in general, though, there may be more than one instruction in a line; or a single instruction may be split over multiple lines.

When a program is evaluated, it starts with an empty stack. Program evaluation continues until the last instruction in the program is evaluated. When an input program is completely evaluated, the interpreter should print the top-most value on the stack and exit.

If an input program has errors (e.g., improperly formed labels, invalid instruction, invalid format for numbers, labels that appear in destinations of jumps but not defined elsewhere, etc.), the interpreter should give an error message and exit. The details (i.e. the source of the error, line number, etc.) in the error message are up to you. All I expect is that your interpreter should at least say that there is some error and exit instead of trying to execute an erroneous program.

Similarly, when executing a program, if the program tries to access values in an empty stack, the interpreter should signal an error and exit. Again, you can choose the error message format.

Examples:

Example 1:
- Input:
```
ildc 10
ildc 20
iadd
	    
```
- Output:
```
30
	    
```

Example 2:

Input:

      ildc 20
      ildc 5
here: ildc 1
      isub
      dup
      jz   there
      swap
      ildc 10
      iadd
      swap
      jmp  here
there:
      swap

Output:
```
60
	    
```

Project Path:

First try to see if you simply check whether programs without labels are valid or not (for example, determine whether example program 1 above is valid). Use Java library such as StreamTokenizer to simplify processing of inputs. Second, try to execute the valid programs you've identified in step 1. Third, try to determine the validity of programs with labels. Finally, try to execute these programs too.

Grading:

The homework itself is worth 3% of your overall grade. It will be graded out of 6 points. Your score will then be scaled down (by a factor of 2) when it is used to compute your overall grade.

We will use the following criteria to evaluate your program.

Design: (1 point): Does the program have sufficient structure to separate out the syntactic issues (i.e. determining the validity of the input) from the semantic issues (i.e. evaluating a valid program)?
Readability (1 points): Is the program understandable?
Correctness (4 points): Does the program take all valid inputs? Does it compute the correct results? Does it detect all invalid inputs?

Submission:

Your submission will consist of a single Java program file Interp.java.

Submit your homework using Blackboard (see Homework #1 in Assignments area) before midnight of Wed, Sep. 24.

C.R. Ramakrishnan