Not an official ACM page
[1991 ACM finals problem set
| My ACM problem archive
| my home page]
1991 ACM Scholastic Programming Contest Finals
sponsored by AT&T Computer Systems
Problem G
Code Generation
Your employer needs a backend for a translator for a very SIC machine
(Simplified Instructional Computer, apologies to Leland Beck). Input
to the translator will be arithmetic expressions in postfix form and
the output will be assembly language code.
The target machine has a single register and the following
instructions, where the operand is either an identifier or a storage
location.
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 and Output
The input file consists of several legitimate postfix expressions,
each on a separate line. Expression operands are single letters and
operators are the normal arithmetic operators (+, -, *, /) and unary
negation (@). Output must be assembly language code that meets the
following requirements:
- One instruction per line with the instruction mnemonic separated
from the operand (if any) by one blank.
- One blank line must separate the assembly code for successive
expressions.
- The original order of the operands must be preserved in the
assembly code.
- Assembly code must be generated for each operator as soon as
it is encountered.
- As few temporaries as possible should be used (given the
above restrictions).
- For each operator in the expression, the minimum number of
instructions must be generated (given the above restrictions).
Sample Input
AB+CD+EF++GH+++
AB+CD+-
Sample Output
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
L A
A B
ST $1
L C
A D
N
A $1
Here's some more sample input/output I thought
is interesting
Input
AB+C/
AB*C@+
AB*CD*/
More Sample Output
L A
A B
D C
L A
M B
ST $1
L C
N
A $1
L A
M B
ST $1
L C
M D
ST $2
L $1
D $2
This page maintained by
Ed Karrels.
Last updated September 20, 1999