You are to write a translator for a Very Simple Machine (VSM not to be confused with VMS!). You may use C, C++, ADA, PASCAL, or JAVA. In C++ and C there is a very nice function in <string.h> called strtok.
VSM has 8 16-bit registers that are named 0, 1, 2, ... 7. Memory is also organized as words of 16-bits, so reading and writing are simplified. All arithmetic and boolean operations only work on registers. In other words, in order to work on a value stored in memory, it must first be loaded into a register, and in order to store a value into memory, the result must be calculated in a register and then stored into memory.
IMMEDIATE values can be symbolic addresses (names), or numbers. If they are numbers, the default base is base 10. By placing an 'h' after a number it will be assumed to be hex. For decimal numbers, you may use a - sign to indicate that the number is negative, eg. -1. For hex, you must use 2's complement to represent a negative. There are no # signs in VSM.
Examples:
| VSM Code | Explanation | |
|---|---|---|
| ADD 0,1,1 | reg0 = reg1 + reg1 | |
| ADD 1,4,5 | reg1 = reg4 + reg5 | |
| LOAD 3,TOTAL ADD 1,1,3 |
Bring the memory location TOTAL into a register and then add it to register 1 | |
| LOAD 3,5 | Load the contents of memory location 5 into register 3 | |
| MOVI 5,5 ADD 1,1,3 |
Bring the immediate value 5 into register 5, then add it to register 1 | |
| MOVI 5,0Fh | Bring the immediate value of 0F hex into register 5 | |
| MOVI 5,0FFFFh | Bring the immediate value of -1 hex into register 5 | |
| TOP: ... ... JMP TOP |
A jump to a label |
Here are the instructions that VSM understands. DEST, SRCA, and SRCB are always numbers from 0 to 7, representing registers. IMMEDIATE is any number, or a symbolic name representing a number (a variable name in higher level languages).
ADD DEST, SRCA, SRCB DEST = SRCA + SRCB Add SRCB to SRCA store result in DEST. Affects all four condition codes: C, V, Z, N. All operands are registers.
AND DEST, SRCA, SRCB DEST = SRCA AND SRCB Perform Boolean AND of SRCB with SRCA store result in DEST. Affects condition codes N and Z; clears C and V. All operands are registers.
NOT DEST, SRCB DEST = NOT SRCB Perform Boolean NOT of SRCB store result in DEST. Affects condition codes N and Z; clears C and V. All operands are registers.
MOV DEST, SRCA DEST = SRCA Copy SRCA to DEST. Affects condition codes N and Z; clears C and V. All operands are registers.
MOVI DEST, IMMEDIATE DEST = IMMEDIATE Copy IMMEDIATE value to DEST. Affects condition codes N and Z; clears C and V. DEST is a register, IMMEDIATE is a number or a symbolic constant.
LSH DEST, SRCA DEST = LSH SRCA Shift SRCA 1 bit to the left store result in DEST, fill with 0. Affects condition codes N, Z and C; clears V. All operands are registers.
RSH DEST, SRCA DEST = RSH SRCA Shift SRCA 1 bit to the right store result in DEST, fill with 0. Affects condition codes N and Z; clears O and V. All operands are registers. LOAD DEST, IMMEDIATE Read the value from memory that is stored at the address held in IMMEDIATE. Store the result in DEST. DEST is a register, IMMEDIATE is a number or a symbolic constant, representing an address in memory. Affects condition codes N and Z; clears C and V.
STORE IMMEDIATE, SRCA Write the value in SRCA to the memory location whose address is the value of IMMEDIATE. DEST is a register, IMMEDIATE is a number or a symbolic constant, representing an address in memory. Doesn't affect any condition codes. JMP IMMEDIATE Jump to the address IMMEDIATE. Doesn't affect any condition codes. JMPZ IMMEDIATE Jump to the address IMMEDIATE if the results of the last operation was zero. Doesn't affect any condition codes. JMPN IMMEDIATE Jump to the address IMMEDIATE if the results of the last operation was negative. Doesn't affect any condition codes. JMPC IMMEDIATE Jump to the address IMMEDIATE if the results of the last operation caused an unsigned overflow. Doesn't affect any condition codes. JMPV IMMEDIATE Jump to the address IMMEDIATE if the results of the last operation caused a signed overflow. Doesn't affect any condition codes. IMMEDIATE: A label. This is the target of a jump. A label can precede any statement or can appear on a line by itself. The ':' must directly follow the IMMEDIATE value (this makes it easier for you to parse).
It has been decided by the system analyst (me) that this language is too tedious to use for programming, however the hardware will not be redesigned. So, the programmer (you) has been instructed to create a translator that will translate a language that is Much Better Intuitively (MBI) into the above language. Here are the instructions that MBI will understand. In the following, X, Y, and LABEL are either numbers representing addresses, symbolic names representing addresses, or immediate values. Immediate values in MBI are preceded by a # sign. MBI does not have access to the registers of VSM. Negative numbers will be stored in 2's complement.
ADD X, Y X = X + Y SUB X, Y X = X - Y. Subtraction is performed by using 2's complenent. MUL X, Y X = X * Y. Repeated addition will be fine for this. Assume each number is between -128 and 127. So, you need to worry about the sign. NOT X X = NOT X AND X, Y X = X AND Y OR X, Y X = X OR Y. Use some Boolean Algebra to rewrite this using only ANDs and NOTs. XOR X, Y X = X XOR Y. Use some Boolean Algebra to rewrite this using only ANDs and NOTs. MOV X, Y X = Y SHL X, Y Shift Y to the left X number of places. Fill vacated bits with zeroes. SHRA X, Y Shift Y to the right X number of places. Fill vacated bits with copies of the sign bit. Arithmetic shift right. SHRL X, Y Shift Y to the right X number of places. Fill vacated bits with zeroes.
Logical shift right. JA LABEL Jump to the given label if X > Y as unsigned numbers. The X and Y would be from the previous arithmetic instruction. JB LABEL Jump to the given label if X < Y as unsigned numbers. The X and Y would be from the previous arithmetic instruction. JG LABEL Jump to the given label if X > Y as signed numbers. The X and Y would be from the previous arithmetic instruction. Signed numbers are stored in 2's complement. JL LABEL Jump to the given label if X < Y as signed numbers. The X and Y would be from the previous arithmetic instruction. Signed numbers are stored in 2's complement. JEQ LABEL Jump to the given label if X = Y. The X and Y would be from the previous arithmetic instruction. JNEQ LABEL Jump to the given label if X <> Y.The X and Y would be from the previous arithmetic instruction. LABEL: This is the target of a jump. A label can precede any statement or can appear on a line by itself. The ':' must directly follow the LABEL value (this makes it easier for you to parse).
An MBI program cannot access any of the registers of the VSM machine. For ADD, SUB, MUL, OR, XOR the second operand can be a symbolic address, an address or an immeditae value. For the shift instructions, the first operand may be a symbolic address, an address or an immediate value. All immediate values in MBI will be preceded by the # sign, otherwise they will be considered addresses. VSM immediate values do not have a # sign, they can only be in one instruction: MOVI.
Your translator should read a file that is written in MBI and translate it to a program in VSM. Be sure that you don't duplicate any labels in the VSM program. For instance, if there is more than one JG instruction in the MBI program, be sure that all the labels are unique in the VSM program.
For each language, there will only be one instruction per line. You may use symbolic addresses in each language. Do not be concerned with where these symbolic addresses are created. Assume that some other module will be handling the symbol table. If there is a symbolic address in the MBI program, then use the same symbolic address in the VSM program.
Notice that in the VSM language, all instructions work on registers, except for the instructions MOVI, LOAD, STORE and all the JMP instructions. When referencing a register, just use the number for the register: 0, 1, 2, ... 7.
If an MBI instruction contains a symbolic address, like NUM, as a source then in VSM you must first LOAD the value from NUM into a register. If the symbolic address is used as a destination, then you must STORE the contents of the register into memory at NUM.
Do not be too concerned about multiplying large numbers. Just write the routine to perform multiplication for two numbers that are both between -127 and 128. This way you will avoid the problem of having a result that won't fit in a register.
I will provide a test program at a later date. Test the program using your own test program until that time.