文章目录
- 一、实验要求
- 二、实验设计
- 三、实验结果
- 四、附完整代码
补录与分享本科实验，以示纪念。
一、实验要求
在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C−−源代码翻译为MIPS32指令序列（可以包含伪指令），并在 SPIM Simulator上运行。
当你完成之后，你就拥有了一个自己独立编写、可以实际运行的编译器。
- 基本要求
将中间代码正确转化为MIPS32汇编代码。
“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。 - 附加要求
- 对寄存器分配进行优化，如使用局部寄存器分配办法等。
- 对指令进行优化
- 化简要求
- 寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的正常运行，可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。
- 栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。甚至可以使用栈以外的方式对过程调用间各种数据的传递进行管理，前提是输出的目标代码“正确”。
本实验只实现了基本要求，没有实现附加要求。
二、实验设计
此次实验在原先的基础上新增加了dst_code.c和dst_code.h文件，用于将中间代码转换成目标代码。
1、程序的数据结构
typedef struct Variable {
char name[32];
int offset;
} Variable;
static IrNode *head;
FILE *fp;
static int argCount = 0;
static int size = 0;
static int count = 0;
// 变量表
static Variable table[1024];
可以看出，我们定义了IR的变量结构，使用数组的形式进行存储（table）。同时使用全局变量记录当前正在处理的函数参数个数argCount，大小size和变量个数count。
2、getOffset
根据变量名获取偏移位置。
/**
* 常数返回-1
* *&开头，不看开头
* 在table里找名字，返回offset
* @param name
* @return
*/
int getOffset(char *name) {
if (name[0] == '#')return -1;
if (name[0] == '*' || name[0] == '&')name++;
for (int i = 0; i < count; i++) {
if (strcmp(name, table[i].name) == 0)
return table[i].offset;
}
return -1;
}
3、addVar
往变量表table里加一个变量variable
/**
* 往table里加一个variable
* @param name
* @param sz
*/
void addVar(char *name, int sz) {
if (name[0] == '#')return;
if (name[0] == '*' || name[0] == '&')name++;
if (getOffset(name) != -1)return;
table[count].offset = size;
size += sz;
strcpy(table[count].name, name);
count++;
}
4、prepareReg
根据不同情况准备一个寄存器。
void prepareReg(char *name, int num) {
char temp[8];
sprintf(temp, "$t%d", num);
if (name[0] == '*') {
// 第一步：把相对栈顶偏移loc的位置的值赋给temp
fprintf(fp, " lw %s, %d($sp)\n", temp, getOffset(name));
// 第二步：将temp的值与$sp地址相加结果存入temp
fprintf(fp, " add %s, %s, $sp\n", temp, temp);
// 第三步：使用temp中的最终地址找到实际要找的值
fprintf(fp, " lw %s, 0(%s)\n", temp, temp);
}
else if (name[0] == '&') {
// 将name的地址存到t寄存器中
fprintf(fp, " li %s, %d\n", temp, getOffset(name));
}
else if (name[0] == '#') {
// 存常数
fprintf(fp, " li %s, %s\n", temp, &name[1]);
}
else {
// 普通变量从栈里拿
fprintf(fp, " lw %s, %d($sp)\n", temp, getOffset(name));
}
}
5、genOneFunction
处理每一个函数的步骤，在这里我们以函数为单位进行处理
void genOneFunction(IrNode *begin, IrNode *end) {
count = 0;
size = 0;
argCount = 0;
// 输出函数
fprintf(fp, "\n%s:\n", begin->args[1]);
// 第一次处理，产生变量表
IrNode *p = begin->next;
while (p != end) {
switch (p->argsNum) {
case 2: {
if (strcmp("GOTO", p->args[0]) != 0)
addVar(p->args[1], 4);
break;
}
case 3: {
if (strcmp(p->args[1], ":=") == 0) {
addVar(p->args[0], 4);
addVar(p->args[2], 4);
}
else if (strcmp(p->args[0], "DEC") == 0) {
int a = strtol(p->args[2], NULL, 10);
addVar(p->args[1], a);
}
break;
}
case 4: {
addVar(p->args[0], 4);
break;
}
case 5: {
addVar(p->args[0], 4);
addVar(p->args[2], 4);
addVar(p->args[4], 4);
break;
}
case 6: {
addVar(p->args[1], 4);
addVar(p->args[3], 4);
break;
}
default:
break;
}
p = p->next;
}
// 更改栈顶指针位置
fprintf(fp, " addi $sp, $sp, -%d\n", size);
// 第二次处理，生成代码
p = begin->next;
while (p != end) {
switch (p->argsNum) {
case 2: {
// GOTO x
if (strcmp(p->args[0], "GOTO") == 0) {
fprintf(fp, " j %s\n", p->args[1]);
}
// RETURN x
else if (strcmp(p->args[0], "RETURN") == 0) {
prepareReg(p->args[1], 0);
fprintf(fp, " move $v0, $t0\n");
fprintf(fp, " addi $sp, $sp, %d\n", size);
fprintf(fp, " jr $ra\n");
}
// ARG x
else if (strcmp(p->args[0], "ARG") == 0) {
prepareReg(p->args[1], 0);
fprintf(fp, " move $a%d, $t0\n", argCount);
argCount++;
}
// PARAM x
else if (strcmp(p->args[0], "PARAM") == 0) {
int para_count = 0;
IrNode *q = p;
while (strcmp(q->next->args[0], "PARAM") == 0) {
q = q->next;
para_count++;
}
fprintf(fp, " sw $a%d, %d($sp)\n", para_count, getOffset(p->args[1]));
}
// READ x
else if (strcmp(p->args[0], "READ") == 0) {
// 保存上下文环境
fprintf(fp, " addi $sp, $sp, -4\n");
fprintf(fp, " sw $ra, 0($sp)\n");
fprintf(fp, " jal read\n");
fprintf(fp, " lw $ra, 0($sp)\n");
fprintf(fp, " addi $sp, $sp, 4\n");
if (p->args[1][0] == '*') {
// 类似 prepareReg
fprintf(fp, " lw $t0, %d($sp)\n", getOffset(p->args[1]));
fprintf(fp, " add $t0, $t0, $sp\n");
fprintf(fp, " sw $v0, 0($t0)\n");
}
else
fprintf(fp, " sw $v0, %d($sp)\n", getOffset(p->args[1]));
}
// WRITE x
else if (strcmp(p->args[0], "WRITE") == 0) {
prepareReg(p->args[1], 0);
// 获取参数
fprintf(fp, " move $a0, $t0\n");
// 保存上下文环境
fprintf(fp, " addi $sp, $sp, -4\n");
fprintf(fp, " sw $ra, 0($sp)\n");
fprintf(fp, " jal write\n");
fprintf(fp, " lw $ra, 0($sp)\n");
fprintf(fp, " addi $sp, $sp, 4\n");
}
break;
}
case 3: {
// x := y
if (strcmp(p->args[1], ":=") == 0) {
prepareReg(p->args[2], 0);
if (p->args[0][0] == '*') {
// 同 prepareReg
fprintf(fp, " lw $t1, %d($sp)\n", getOffset(p->args[0]));
fprintf(fp, " add $t1, $t1, $sp\n");
fprintf(fp, " sw $t0, 0($t1)\n");
}
else {
fprintf(fp, " sw $t0, %d($sp)\n", getOffset(p->args[0]));
}
}
// DEC x [size]
else if (strcmp(p->args[0], "DEC") != 0) {
fprintf(fp, "%s:\n", p->args[1]);
}
break;
}
case 4: {
// x := CALL f
argCount = 0;
fprintf(fp, " addi $sp, $sp, -4\n");
fprintf(fp, " sw $ra, 0($sp)\n");
fprintf(fp, " jal %s\n", p->args[3]);
fprintf(fp, " lw $ra, 0($sp)\n");
fprintf(fp, " addi $sp, $sp, 4\n");
if (p->args[0][0] == '*') {
fprintf(fp, " lw $t0, %d($sp)\n", getOffset(p->args[0]));
fprintf(fp, " add $t0, $t0 ,$sp\n");
fprintf(fp, " sw $v0, 0($t0)\n");
}
else
fprintf(fp, " sw $v0, %d($sp)\n", getOffset(p->args[0]));
break;
}
case 5: {
prepareReg(p->args[2], 0);
prepareReg(p->args[4], 1);
// x := y + z x := y - z x := y * z x := y / z
switch (p->args[3][0]) {
case '+': {
fprintf(fp, " add $t0, $t0, $t1\n");
break;
}
case '-': {
fprintf(fp, " sub $t0, $t0, $t1\n");
break;
}
case '*': {
fprintf(fp, " mul $t0, $t0, $t1\n");
break;
}
case '/': {
fprintf(fp, " div $t0, $t1\n");
fprintf(fp, " mflo $t0\n");
break;
}
default:;
}
if (p->args[0][0] == '*') {
fprintf(fp, " lw $t1, %d($sp)\n", getOffset(p->args[0]));
fprintf(fp, " add $t1, $t1, $sp\n");
fprintf(fp, " sw $t0, 0($t1)\n");
}
else
fprintf(fp, " sw $t0, %d($sp)\n", getOffset(p->args[0]));
break;
}
case 6: {
// if x [relop] y GOTO z
char temp[4];
if (strcmp(p->args[2], "==") == 0)
strcpy(temp, "beq");
else if (strcmp(p->args[2], "!=") == 0)
strcpy(temp, "bne");
else if (strcmp(p->args[2], ">") == 0)
strcpy(temp, "bgt");
else if (strcmp(p->args[2], "<") == 0)
strcpy(temp, "blt");
else if (strcmp(p->args[2], ">=") == 0)
strcpy(temp, "bge");
else if (strcmp(p->args[2], "<=") == 0)
strcpy(temp, "ble");
prepareReg(p->args[1], 0);
prepareReg(p->args[3], 1);
fprintf(fp, " %s $t0, $t1, %s\n", temp, p->args[5]);
break;
}
default:
break;
}
p = p->next;
}
}
6、genDstCode
首先生成read函数和write函数的目标代码，然后使用genOneFunction处理每一个函数。
void genDstCode(IrNode *h, FILE *f) {
head = h;
fp = f;
fprintf(fp, "%s\n", ".data");
fprintf(fp, "%s\n", "_prompt: .asciiz \"Enter an integer:\"");
fprintf(fp, "%s\n", "_ret: .asciiz \"\\n\"");
fprintf(fp, "%s\n", ".globl main");
fprintf(fp, "%s\n", ".text");
fprintf(fp, "%s\n", "read:");
fprintf(fp, " %s\n", "li $v0, 4");
fprintf(fp, " %s\n", "la $a0, _prompt");
fprintf(fp, " %s\n", "syscall");
fprintf(fp, " %s\n", "li $v0, 5");
fprintf(fp, " %s\n", "syscall");
fprintf(fp, " %s\n", "jr $ra");
fprintf(fp, "\n");
fprintf(fp, "%s\n", "write:");
fprintf(fp, " %s\n", "li $v0, 1");
fprintf(fp, " %s\n", "syscall");
fprintf(fp, " %s\n", "li $v0, 4");
fprintf(fp, " %s\n", "la $a0, _ret");
fprintf(fp, " %s\n", "syscall");
fprintf(fp, " %s\n", "move $v0, $0");
fprintf(fp, " %s\n", "jr $ra");
IrNode *p = head, *q;
do {
// 定位函数
q = p->next;
while (1) {
if (strcmp(q->args[0], "FUNCTION") == 0 || q == head) break;
q = q->next;
}
// 分析函数
genOneFunction(p, q);
p = q;
} while (p != head);
}
三、实验结果
- test1.c
int main()
{
int a = 0, b = 1, i = 0, n;
n = read();
while (i < n) {
int c = a + b;
write(b);
a = b;
b = c;
i = i + 1;
}
return 0;
}
执行目标代码生成：
目标代码：
.data
_prompt: .asciiz "Enter an integer:"
_ret: .asciiz "\n"
.globl main
.text
read:
li $v0, 4
la $a0, _prompt
syscall
li $v0, 5
syscall
jr $ra
write:
li $v0, 1
syscall
li $v0, 4
la $a0, _ret
syscall
move $v0, $0
jr $ra
main:
addi $sp, $sp, -20
li $t0, 0
sw $t0, 0($sp)
li $t0, 1
sw $t0, 4($sp)
li $t0, 0
sw $t0, 8($sp)
addi $sp, $sp, -4
sw $ra, 0($sp)
jal read
lw $ra, 0($sp)
addi $sp, $sp, 4
sw $v0, 12($sp)
label0:
lw $t0, 8($sp)
lw $t1, 12($sp)
blt $t0, $t1, label1
j label2
label1:
lw $t0, 0($sp)
lw $t1, 4($sp)
add $t0, $t0, $t1
sw $t0, 16($sp)
lw $t0, 4($sp)
move $a0, $t0
addi $sp, $sp, -4
sw $ra, 0($sp)
jal write
lw $ra, 0($sp)
addi $sp, $sp, 4
lw $t0, 4($sp)
sw $t0, 0($sp)
lw $t0, 16($sp)
sw $t0, 4($sp)
lw $t0, 8($sp)
li $t1, 1
add $t0, $t0, $t1
sw $t0, 8($sp)
j label0
label2:
li $t0, 0
move $v0, $t0
addi $sp, $sp, 20
jr $ra
目标代码执行结果（输入 2）：
- test2.c
int fact(int n)
{
if (n == 1){
return n;
}
else
return (n * fact(n - 1));
}
int main()
{
int m, result;
m = read();
if (m > 1)
result = fact(m);
else
result = 1;
write(result);
return 0;
}
执行目标代码生成：
目标代码：
.data
_prompt: .asciiz "Enter an integer:"
_ret: .asciiz "\n"
.globl main
.text
read:
li $v0, 4
la $a0, _prompt
syscall
li $v0, 5
syscall
jr $ra
write:
li $v0, 1
syscall
li $v0, 4
la $a0, _ret
syscall
move $v0, $0
jr $ra
fact:
addi $sp, $sp, -16
sw $a0, 0($sp)
lw $t0, 0($sp)
li $t1, 1
beq $t0, $t1, label0
j label1
label0:
lw $t0, 0($sp)
move $v0, $t0
addi $sp, $sp, 16
jr $ra
j label2
label1:
lw $t0, 0($sp)
li $t1, 1
sub $t0, $t0, $t1
sw $t0, 4($sp)
lw $t0, 4($sp)
move $a0, $t0
addi $sp, $sp, -4
sw $ra, 0($sp)
jal fact
lw $ra, 0($sp)
addi $sp, $sp, 4
sw $v0, 8($sp)
lw $t0, 0($sp)
lw $t1, 8($sp)
mul $t0, $t0, $t1
sw $t0, 12($sp)
lw $t0, 12($sp)
move $v0, $t0
addi $sp, $sp, 16
jr $ra
label2:
main:
addi $sp, $sp, -8
addi $sp, $sp, -4
sw $ra, 0($sp)
jal read
lw $ra, 0($sp)
addi $sp, $sp, 4
sw $v0, 0($sp)
lw $t0, 0($sp)
li $t1, 1
bgt $t0, $t1, label3
j label4
label3:
lw $t0, 0($sp)
move $a0, $t0
addi $sp, $sp, -4
sw $ra, 0($sp)
jal fact
lw $ra, 0($sp)
addi $sp, $sp, 4
sw $v0, 4($sp)
j label5
label4:
li $t0, 1
sw $t0, 4($sp)
label5:
lw $t0, 4($sp)
move $a0, $t0
addi $sp, $sp, -4
sw $ra, 0($sp)
jal write
lw $ra, 0($sp)
addi $sp, $sp, 4
li $t0, 0
move $v0, $t0
addi $sp, $sp, 8
jr $ra
目标代码执行结果（输入 5）：
四、附完整代码
github 链接：https://github.com/zheliku/byyl---Target-Code-Generation。
![[FreeRTOS 内部实现] 互斥访问与回环队列](https://img-blog.csdnimg.cn/direct/51d692112eb44235b9a28860d5aa51cb.png)
![【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 局域网中的服务器个数(200分) - 三语言AC题解(Python/Java/Cpp)](https://img-blog.csdnimg.cn/direct/ad19c3bccca64c4abcca2b8eeb98f49b.png)
