通过三地址代码序列生成计算机的目标代码,在生成算法中,对寄存器的使用顺序为:寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用
单组输入,给定输出的三地址代码的个数和寄存器的个数.所有的变量为大写字母,寄存器的数量不超过9
参照示例格式输出,不需要将最后的寄存器中的值写回内存
不再使用变量不用写回内存
Input
4 2
T:=A-B
U:=A-C
V:=T+U
W:=V+U
Output
LD R0, A
SUB R0, B
LD R1, A
SUB R1, C
ADD R0, R1
ADD R0, R1
#include <bits/stdc++.h>
using namespace std;
char p[100];// 模拟寄存器的个数
char s[100][100];// 输入表达式字符串
int n,m,top = 0;//n输入的表达式,m是寄存器个数
// 寄存器中是否存在该变量
int get(char ch)
{
for(int i = 0; i < m;i ++)
{
if(ch == p[i])
return i;
}
return -1;
}
///寄存器的使用顺序为:
///寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用
//判断后面是否还会使用
//x是输入表达式的编号,语句执行顺序
//ch需要判断的字符
int use(int x, char ch)
{
for(int i = x; i < n; i ++)
{
// A:=B+C这里就是B、C
// 如果有就返回第几句用到
if(ch == s[i][3] || ch == s[i][5])
return i;
}
return n;
}
///寄存器的使用顺序为:
///寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用
int find(int x)
{
// 如果top小于m,就说明就空的寄存器可以使用
if(top < m) return top++;
//否则就是
int t = -1;
int ans = -1;
for(int i = 0; i < m; i ++)
{
// 逐个判断在第x句之后,存在寄存器中的字符的使用顺序
// 返回值k是执行顺序的标号
int k = use(x,p[i]);
// 我们的目的是找到最远不适用的,如果返回值越大,那就是最远不适用的
// 记录标号存在t里面
if(k > ans)
{
ans = k;
t = i;
}
}
return t;
}
// 减加乘除
void print1(char ch)
{
if(ch == '+')printf("ADD ");
else if(ch == '-') printf("SUB ");
else if(ch == '*') printf("MUL ");
else if(ch == '\\') printf("DIV ");
}
// 第二个操作数的使用
void print2(char ch)
{
// 查看是否在寄存器中
int x = get(ch);
// 如果在寄存器中,那就直接使用
if(x != -1){
printf("R%d\n",x);
}
else {
// 否则就直接使用内存中的即可,因为已经有一个寄存器了
printf("%c\n",ch);
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n;i ++)
{
cin >> s[i];
}
for(int i = 0; i < n; i ++)
{
// 将第1个操作数取出来,get()来获取寄存器中是否存在该变量
// T:=A-B中的A
int x = get(s[i][3]);//如果不为-1,得到的x为所在寄存器的标号
// 如果x为-1说明该数不在寄存器中,需要做处理
if(x == -1)
{
//此时的x是我们可以使用的寄存器标号
x = find(i);
// 如果p[x]中有东西,并且use(i,p[x]) < n即后面会使用到
//那我们就把原来在寄存器中的字符ST到内存中
if(p[x] != '\0' && use(i,p[x]) < n)
{
printf("ST R%d, %c\n",x,p[x]);
p[x] = NULL;
}
//将该操作数加载到我们使用的寄存器标号中
printf("LD R%d, %c\n",x,s[i][3]);
}
// 这里下面的操作就是执行运算
// 1、输出操作符,这里是加减乘除
print1(s[i][4]);
//2、输出寄存器标号,需要的操作数已经加载到里面了
printf("R%d, ",x);
//3、第二个操作数的使用
print2(s[i][5]);
// 寄存器中当前存的数值就是该表示的左边的字符,即T:=A-B中的T
p[x] = s[i][0];
}
return 0;
}