简单的代码生成程序 SDUT 【编译原理】C++

目录

Description

代码：

分析：

通过三地址代码序列生成计算机的目标代码,在生成算法中,对寄存器的使用顺序为:寄存器中存有 > 空寄存器 > 内存中存有 > 以后不再使用 > 最远距离使用

Input

单组输入,给定输出的三地址代码的个数和寄存器的个数.所有的变量为大写字母,寄存器的数量不超过9

Output

参照示例格式输出,不需要将最后的寄存器中的值写回内存，不再使用变量不用写回内存

Sample

4 2
T:=A-B
U:=A-C
V:=T+U
W:=V+U

LD R0, A
SUB R0, B
LD R1, A
SUB R1, C
ADD R0, R1
ADD R0, R1

#include 
using namespace std;
const int inf = 0x3f3f3f;
string sentence[200];
char reg[10];
int n, m, top;

int index_reg(char ch);//查找ch在寄存器中的位置
int exist_behind(int id, char ch);//查找ch在第id条语句后再次出现的语句序号
int chose_reg(int id);//已经遍历到第id条语句，现在选取一个合适的寄存器
void printf_ans(int id, int index);//输出运算语句+ - * 

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) //输入
		cin >> sentence[i];
	for (int i = 0; i < n; i++){//遍历所有语句，生成程序
		int index = index_reg(sentence[i][3]);//查看第一个运算符在寄存器中的位置
		if (index == inf) {//第一个运算符不在寄存器中
			index = chose_reg(i);
			printf("LD R%d, %cn", index, sentence[i][3]);
		}
		printf_ans(i, index);
	}
	return 0;
}
int index_reg(char ch) {//查找ch在寄存器中的位置
	for (int i = 0; i < m; i++)
		if (reg[i] == ch) return i;
	return inf;
}
int exist_behind(int id, char ch) {//查找ch在第id条语句后再次出现的语句序号
	for (int i = id; i < n; i++)
		if (ch == sentence[i][3] || ch == sentence[i][5]) return i;
	return inf;
}
int chose_reg(int id) {//已经遍历到第id条语句，现在选取一个合适的寄存器
	if (top < m) return top++;//还有空闲寄存器
	int Max = -1, index = 0;
	for (int i = 0; i < m; i++) //找出最远再次使用的变量
		if (exist_behind(id, reg[i]) > Max) {
			Max = exist_behind(id, reg[i]);
			index = i;
		}
	if (reg[index] != '' && exist_behind(id, reg[index]) != inf) {//腾出寄存器
		printf("ST R%d, %cn", index, reg[index]);
		reg[index] = NULL;
	}
	return index;
}
void printf_ans(int id, int index) {//输出加减乘除的运算语句
	char temp = sentence[id][4];
	if (temp == '+') cout << "ADD ";
	else if (temp == '-') cout << "SUB ";
	else if (temp == '*') cout << "MUL ";
	else if (temp == '\') cout << "DIV ";
	cout << "R" << index << ", ";//输出第一个运算符所在的寄存器
	if (index_reg(sentence[id][5]) == inf) cout << sentence[id][5] << endl;//输出第二个运算符,可能在寄存器中
	else cout << "R" << index_reg(sentence[id][5]) << endl;
	reg[index] = sentence[id][0];//将运算结果存入第一个运算符的寄存器
}

分析：

例如输入一条语句为：a:=b+c。

这里的过程是：

1.首先判断b是否在寄存器中，①b在寄存器中，直接将c的值与b相加，这里b使用的是寄存器地址。②b不在寄存器中，选择一个合适的寄存器将b存储进去，再与c相加。

2.调取c时同样需要判断c是否在寄存器中，因为c可能在之前计算过，然后存入了寄存器。这里c在寄存器就使用寄存器地址，不在寄存器就使用c自己的地址（即输出时时间输出c）。

3.选取合适的寄存器，首先从前向后扫描，有空闲的优先使用空闲的寄存器；没有空闲的，找出寄存器中，在当前遍历语句后面不再使用的变量或最晚再次使用的变量，将其存入内存，在使用该寄存器。