During this activity, students should be able to:
This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.
This activity can be solved individually or in teams of two people.
This problem was adapted from: 1991 ACM Finals, Problem G - Code Generation
Your employer needs a backend for a translator for a very SIC machine (Simplified Instructional Computer). Input to the translator will be a string containing an arithmetic expressions in postfix form and the output will be a list containing assembly language code. You must write a Clojure function called sic that solves this problem.
The target machine has a single register and the following instructions, where the operand is either an identifier or a storage location.
| Operator | Description |
|---|---|
| L | Load the operand into the register. |
| A | Add the operand to the contents of the register. |
| S | Subtract the operand from the contents of the register. |
| M | Multiply the contents of the register by the operand. |
| D | Divide the contents of the register by the operand. |
| N | Negate the contents of the register. |
| ST | Store the contents of the register in the operand location. |
An arithmetic operation replaces the contents of the register with the expression result. Temporary storage locations are allocated by the assembler for an operand of the form "$n" where n is a single digit.
Input expression operands are single letters and operators are the normal arithmetic operators (+, -, *, /) and unary negation (@). Output must be a list of assembly language code that meets the following requirements:
Make sure your solution works with the following unit tests:
(deftest test-sic
(is (= '([L A]
[A B]
[D C])
(sic "AB+C/")))
(is (= '([L A]
[M B]
[ST $1]
[L C]
[N]
[A $1])
(sic "AB*C@+")))
(is (= '([L A]
[M B]
[ST $1]
[L C]
[M D]
[ST $2]
[L $1]
[D $2])
(sic "AB*CD*/")))
(is (= '([L A]
[A B]
[ST $1]
[L C]
[A D]
[ST $2]
[L E]
[A F]
[A $2]
[ST $2]
[L G]
[A H]
[A $2]
[A $1])
(sic "AB+CD+EF++GH+++")))
(is (= '([L A]
[A B]
[ST $1]
[L C]
[A D]
[N]
[A $1])
(sic "AB+CD+-"))))
Using the Online
Assignment Delivery System (SETA), deliver a single file called
sic.clj containing the problem solution and the unit tests.
No assignments will be accepted through e-mail or any other means.
IMPORTANT: The program source file must include at the top the authors' personal information (name and student id) within comments. For example:
;;; ITESM CEM, May 9, 2011.
;;; Clojure Source File
;;; Activity: Final Project: SIC Machine
;;; 457754 Jane Foster
;;; 1161611 Donald Blake
.
. (The rest of the program goes here)
.
Due date: Monday, May 9, 9:00 a.m.
This activity will be evaluated using the following criteria:
| -10 | The program doesn't contain within comments the authors' personal information. |
|---|---|
| 10 | The program contains syntax errors. |
| DA | The program was plagiarized. |
| 20-50 | The program doesn't work, but it seams that some significant amount of time was spent in it. |
| 60-90 | The program works, but has some flaws. |
| 100 | The program works as requested. |