CSE 304: Compiler Design

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.

The assembly language consists of the following instructions.

• 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.
• pop: pop the top-most element of 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.

Note that instructions ildc, jz, jnz and jmp take one argument; the other instructions have no arguments.

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

The input assembly program may also have comments. A comment begins with "#" symbol and ends at the end of the line.

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:
          pop
    	    

  • Output:

    60
    	    

Project Path:

Second, consider programs without labels that may have errors. Now you have to first check for errors before you try to execute an input program. Modify your code to do this.

Finally consider programs with labels and comments.

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:

• Name the directory with your Blackboard userid.
• Put all your sources in that directory (including the source lexical analysis specification).
• Place a "Makefile" in that directory. Typing make from that directory should be able to fully compile your program.
• Add a README.txt file ot note anything special.
• If you have specific test cases you want me to look at, put these in a separate sub-directory.

      tar   cvf   yourid.tar   yourid
    

Note: The way Blackboard is set up, you can submit this assignment only once. To avoid problems, please submit only when you are ready!