CMSC 435: Assignment 1

Overview

Modify the author’s Tiny Machine (TM) interpreter contained in tm.c. Add support for the two instructions described below. Once you implement the instructions, write a TM program that inputs two integers, a and b, and computes and outputs \(a \bmod b\), \(2^b\), and \(2^{30}\). Use ONLY SHL instructions to compute the powers of two. COMMENT each instruction of your TM program.

Once you’re familiar with the interpreter and its source code, add support for the two instructions below. Carefully COMMENT your changes, using a comment of the form /* MODIFIED: ... */ as close to the change as possible. When I grade I will literally search for the string MODIFIED to see your changes.

• a register-register MOD instruction, which computes reg(r) = reg(s) % reg(t). If reg(t) ≤ 0, return a “srNONPOSMOD” error code which will cause a “Modulus non-positive” error to be printed.

• a register-address SHL instruction, which computes reg(r) = reg(s) << d (a logical shift left of d bits). If d < 0, return a “srNEGSHIFT” error code which will cause a “Shift amount negative” error to be printed. You can use C’s shift operator to implement this TM instruction. Note that d is an immediate, and should NOT be obtained from the register file.

Next, fix the interpreter code so that it compiles WITHOUT warnings, but ensure you don’t change the meaning of the code. Input commands like i and d should work as they did before — CAREFULLY TEST THIS!

Lastly, answer the questions below.

Input Specification

All original TM inputs should still be valid. For your program you will input two integers a and b, which will be used to test your added MOD and SHL instructions.

Output Specification

Output \(a \bmod b\), \(2^b\), and \(2^{30}\) IN ORDER (see the session below). If the input causes an error, print an appropriate error message (see the precise messages to use above). An error should cause the program to halt.

Sample Session

TM  simulation (enter h for help)...
Enter command: go
Enter value for IN instruction: 17
Enter value for IN instruction: 5
OUT instruction prints: 2
OUT instruction prints: 32
OUT instruction prints: 1073741824
HALT: 0,0,0
Halted
Enter command: clear
Enter command: go
Enter value for IN instruction: 17
Enter value for IN instruction: 0
Modulus non-positive
Enter command: quit
Simulation done.

Required Types, Concepts, and Functions

None

Questions

Answer these questions in a PLAIN TEXT file named README.txt. Include the QUESTIONS in the file as well. Use whitespace for readability, and keep lines to AT MOST 80 characters.

1. Give two examples of tokens and lexemes in the TM language. Discuss one of the lexical conventions of TM (e.g., comments and whitespace).

2. Discuss the grammar of the TM language. What does a program consist of? What are valid statement/instruction formats?

3. Explain an example of semantic analysis that the TM interpreter performs.

What to Submit

Submit your modified TM interpreter tm.c, your TM program (use a .tm extension), and README.txt.

Hints

Copy tm.c and fact.tm into a directory. Compile tm.c with gcc (you will need to use an older C standard so you do NOT get errors), without modifying the source code yet. Execute the Tiny Machine interpreter and pass fact.tm as a command-line argument. The interpreter will load the instructions from fact.tm into its instruction memory. Experiment with running the program and using the commands described by the help command.

You can learn more about the TM virtual machine by reading section 8.7 in the text.

Gary M. Zoppetti, Ph.D.