📄 prob_g.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb2312">
<META NAME="GENERATOR" CONTENT="Mozilla/4.03 [zhcn] (Win95; I) [Netscape]">
<TITLE>1991 ACM Finals, Problem G - Code Generation</TITLE>
<!SGML "ISO 8879:1986">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<HR NOSHADE>
<CENTER>
<H2>
<I>1991 ACM Scholastic Programming Contest Finals</I></H2></CENTER>
<CENTER>
<H4>
<I>sponsored by AT&T Computer Systems</I></H4></CENTER>
<CENTER>
<H2>
Problem G<BR>
Code Generation</H2></CENTER>
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.
<P>The target machine has a single register and the following instructions,
where the operand is either an identifier or a storage location.
<BLOCKQUOTE><TT>L -- </TT>load the operand into the register
<BR><TT>A -- </TT>add the operand to the contents of the register
<BR><TT>S -- </TT>subtract the operand from the contents of the register
<BR><TT>M -- </TT>multiply the contents of the register by the operand
<BR><TT>D -- </TT>divide the contents of the register by the operand
<BR><TT>N -- </TT>negate the contents of the register
<BR><TT>ST -- </TT>store the contents of the register in the operand location</BLOCKQUOTE>
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.
<H3>
Input and Output</H3>
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:
<OL>
<LI>
One instruction per line with the instruction mnemonic separated from the
operand (if any) by one blank.</LI>
<LI>
One blank line must separate the assembly code for successive expressions.</LI>
<LI>
The original order of the operands must be preserved in the assembly code.</LI>
<LI>
Assembly code must be generated for each operator as soon as it is encountered.</LI>
<LI>
As few temporaries as possible should be used (given the above restrictions).</LI>
<LI>
For each operator in the expression, the minimum number of instructions
must be generated (given the above restrictions).</LI>
</OL>
<H3>
Sample Input</H3>
<PRE>AB+CD+EF++GH+++
AB+CD+-</PRE>
<H3>
Sample Output</H3>
<PRE>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</PRE>
<HR NOSHADE>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -