湖南大学编译原理实验六：代码生成器
由于这个版本并不完善，所以对应的代码仅供参考。对于某些较为复杂的样例：涉及到参数传递的函数调用是没有办法正确运行的。（因为在这个代码的语义分析部分，将数组元素作为了ID来处理，这就比较麻烦了。）链接同样的，我也是抄的。上面的链接给出了原本的代码。但是存在的问题除了上面所讲的，还有无法正确处理数组元素。在我这个版本修复了这个问题。至于什么时候把他改成一个可以完美运行的Compiler，再说吧。代码链
由于这个版本并不完善，所以对应的代码仅供参考。对于某些较为复杂的样例：涉及到参数传递的函数调用是没有办法正确运行的。（因为在这个代码的语义分析部分，将数组元素作为了ID来处理，这就比较麻烦了。）
链接
同样的，我也是抄的。上面的链接给出了原本的代码。但是存在的问题除了上面所讲的，还有无法正确处理数组元素。在我这个版本修复了这个问题。至于什么时候把他改成一个可以完美运行的Compiler，再说吧。
代码链接：编译原理实验六
实验六代码生成器
（一）学习经典的代码生成器（2小时）
一、实验目的
学习已有编译器的经典代码生成源程序。
二、实验任务
阅读已有编译器的经典代码生成源程序，并测试代码生成器的输出。
三、实验内容
-
选择一个编译器，如：TINY或PL/0，其它编译器也可（需自备源代码）。
-
阅读TM虚拟机的有关文档（请参考《编译原理及实践》第8.7节）。了解TM机的指令结构与寻址方式等相关内容。
-
阅读代码生成源程序，加上你自己的理解。尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。
-
测试代码生成器。请对生成的目标代码逐行加上注释，增强其可读性。
TINY语言：
测试用例一：sample.tny。
测试用例二：用TINY语言自编一个程序计算任意两个正整数的最大公约数与最大公倍数。
（二）实现一门语言的代码生成器（6小时）
一、实验目的
通过本次实验，加深对代码生成的理解，学会编制代码生成器。
二、实验任务
用C或JAVA语言编写一门语言的代码生成器。
三、实验内容
- 语言确定：C－语言，其定义在《编译原理及实践》附录A中。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。
- 完成对TM机的改造设计，以满足C－语言的要求。详情请参见C－语言的定义文档。
- 仿照前面学习的代码生成器，编写选定语言的代码生成器。
- 准备2~3个测试用例，测试你的程序，并逐行解释生成的目标代码。
实验步骤
了解TM虚拟机的指令结构和寻址方式
TM由只读指令存储区、数据区和8个通用寄存器构成。寄存器7为程序记数器，它也是唯一的专用寄存器。
#define IADDR_SIZE ...
/* size of instruction memory */
#define DADDR_SIZE...
/* size of data memory */
#define NO_REGS 8 /* number of registers */
#define PC_REG 7
Instruction iMem[IADDR_SIZE];
int dMem[DADDR_SIZE];
int reg[NO_REGS];
TM执行一个常用的取指-执行循环
do
/* fetch */
current Instruction = iMem [reg[pcRegNo]++];
/* execute current instruction */
. . .
while (!(halt || error));
在开始点，TinyMachine将所有寄存器和数据区设为0，然后将最高正规地址的值(名为DADDR_SIZE-1)装入到dMem[0]中。TM然后开始执行iMem[0]指令。机器在执行到HALT指令时停止。
在执行时也要检查错误：IMEM_ERR(它发生在取指步骤中若reg[PC_REG]<0或reg[PC_REG]≥IADDR_SIZE时)，以及两个条件DMEM_ERR和ZERO-DIV
TM指令集包括两种基本指令格式：寄存器，即RO指令。寄存器-存储器，即RM指令。
寄存器RO指令
这里操作数r、s、t为正规寄存器。
这样这种指令有3个地址，且所有地址都必须为寄存器。
寄存器-存储器RM指令
在代码中r和s必须为正规的寄存器(装入时检测)，而d为代表偏移的正、负整数。
这种指令为两地址指令，第1个地址总是一个寄存器，而第2个地址是存储器地址a，用a=d+reg[s]给出，这里a必须为正规地址(0≤a＜DADDR_SIZE)。如果a超出正规的范围，在执行中就会产生DMEM_ERR。
寻址方式
跳转：
通过将PC作为目标寄存器，来实现无条件指令跳转：
LDA 7,d(s) 会转移到位置a = d + reg[s]。
LD 7,0(1) 转移到由寄存器1指示地址的指令。
条件转移指令(JLT等)可以与程序中当前位置相关，只要把PC作为第2个寄存器
例如 JEQ 0,4(7) 导致TM在寄存器0的值为0时向前转移5条指令
无条件转移也可以与PC相关，只要PC两次出现在LDA指令：中LDA 7,-4(7) 执行无条件转移回退3条指令。
TINY代码生成源程序
code.[ch]
/* pc = program counter */
#define pc 7
/* mp = "memory pointer" points
* to top of memory (for temp storage)
*/
#define mp 6
/* gp = "global pointer" points
* to bottom of memory for (global)
* variable storage
*/
#define gp 5
/* accumulator */
#define ac 0
/* 2nd accumulator */
#define ac1 1
进行一些基本的寄存器定义。TM虚拟机总共有8个寄存器，且第7号为PC寄存器。
定义两个寄存器 mp 和 gp ，mp 用来访问临时变量，并总是包含最高正规内存位置，而 gp 用于所有命名变量访问，并总是包含 0。
这样由符号表计算的绝对地址可以生成相对 gp 的偏移来使用。
剩余的两个寄存器用于分配给累加器，为ac和ac1，最终的结果保存在ac
emitComment函数会以注释格式将其参数串打印到代码文件中的新行中。下两个函数emitRO和emitRM为标准的代码发行函数用于RO和RM指令类。除了指令串和3个操作数之外，每个函数还带有1个附加串参数，它被加到指令中作为注释。
/* Procedure emitComment prints a comment line
* with comment c in the code file
*/
void emitComment( char * c );
/* Procedure emitRO emits a register-only
* TM instruction
* op = the opcode
* r = target register
* s = 1st source register
* t = 2nd source register
* c = a comment to be printed if TraceCode is TRUE
*/
void emitRO( char *op, int r, int s, int t, char *c);
/* Procedure emitRM emits a register-to-memory
* TM instruction
* op = the opcode
* r = target register
* d = the offset
* s = the base register
* c = a comment to be printed if TraceCode is TRUE
*/
void emitRM( char * op, int r, int d, int s, char *c);
具体的参数传入方式即上面TM规定的RO和RM指令
emitSkip则是跳过一定数量的指令，用于在之后反填，在实现跳转指令时需要用到。典型的应用是调用emitSkip(1)，它跳过一个位置，这个位置后来会填上转移指令，而emitSkip(0)不跳过位置，调用它只是为了得到当前位置以备后来的转移引用。
emitBackup用于设置当前指令位置到先前位置来反填，emitRestore用于返回当前指令位置给先前调用emitBackup的值。
emitRM_Abs用来产生诸如反填转移或任何由调用emitSkip返回的代码位置的转移的代码。它将绝对代码地址转变成pc相关地址，这由当前指令位置加1(这是pc继续执行的地方)减去传进的位置参数，并且使用pc做源寄存器。通常地，这个函数仅用于条件转移
常用组合：
emitBackup(savedLoc1) ;
emitRM_Abs(args) ;
emitRestore() ;
/* Function emitSkip skips "howMany" code
* locations for later backpatch. It also
* returns the current code position
*/
int emitSkip(int howMany);
/* Procedure emitBackup backs up to
* loc = a previously skipped location
*/
void emitBackup(int loc);
/* Procedure emitRestore restores the current
* code position to the highest previously
* unemitted position
*/
void emitRestore(void);
/* Procedure emitRM_Abs converts an absolute reference
* to a pc-relative reference when emitting a
* register-to-memory TM instruction
* op = the opcode
* r = target register
* a = the absolute location in memory
* c = a comment to be printed if TraceCode is TRUE
*/
void emitRM_Abs(char *op, int r, int a, char *c);
cgen.[ch]
外部调用入口：CodeGen函数，设置启动时运行环境之后，在语法树上调用cGen并且最终产生一个HALT指令，可以看作是一个简单的入口
void codeGen(TreeNode * syntaxTree, char * codefile)
{ char * s = malloc(strlen(codefile)+7);
strcpy(s,"File: ");
strcat(s,codefile);
emitComment("TINY Compilation to TM Code");
emitComment(s);
/* generate standard prelude */
emitComment("Standard prelude:");
emitRM("LD",mp,0,ac,"load maxaddress from location 0");
emitRM("ST",ac,0,ac,"clear location 0");
emitComment("End of standard prelude.");
/* generate code for TINY program */
cGen(syntaxTree);
/* finish */
emitComment("End of execution.");
emitRO("HALT",0,0,0,"");
}
这里在9行10行是对mp的初始化，将其置0表示最高正规内存位置，之后讲0位置清除。
cGen则是遍历语法树，识别当前结点是句子结点还是表达式结点，然后对应的在相应的结点调用genStmt和genExp，并且递归调用自身，起到遍历的效果。
static void cGen( TreeNode * tree)
{ if (tree != NULL)
{ switch (tree->nodekind) {
case StmtK:
genStmt(tree);
break;
case ExpK:
genExp(tree);
break;
default:
break;
}
cGen(tree->sibling);
}
}
在genStmt和genExp函数内部，则是根据当前结点的具体属性，来调用emit系列函数生成目标代码
目标代码注释
* TINY Compilation to TM Code
* File: sample.tm
* Standard prelude: * 初始化
0: LD 6,0(0) load maxaddress from location 0 * mp清0
1: ST 0,0(0) clear location 0
* End of standard prelude.
2: IN 0,0,0 read integer value * 读入 放入reg[0] (read x;)
3: ST 0,0(5) read: store value * 将 reg[0] 存入 dMem[0 + reg[5]] gp
* -> if
* -> Op
* -> Const
4: LDC 0,0(0) load const * 加载常量0 reg[0] = 0
* <- Const
5: ST 0,0(6) op: push left * 将 reg[0] 存入 dMem[0 + reg[6]] mp
* -> Id
6: LD 0,0(5) load id value * 将 dMem[0 + reg[5]] 装入 reg[0]
* <- Id
7: LD 1,0(6) op: load left * 将 dMem[0 + reg[6]] 装入 reg[1]
8: SUB 0,1,0 op < * 做减法 reg[0] = reg[1] - reg[0]
9: JLT 0,2(7) br if true * reg[0] == 0 ? reg[7] += 3 ==> 12
10: LDC 0,0(0) false case * reg[0] = 0 false情况
11: LDA 7,1(7) unconditional jmp * 无条件跳转reg[7] = reg[7] + 2 ==> 13
12: LDC 0,1(0) true case * reg[0] = 1 true情况 (if 0 < x then)
* <- Op
* if: jump to else belongs here
* -> assign
* -> Const
14: LDC 0,1(0) load const * reg[0] = 1
* <- Const
15: ST 0,1(5) assign: store value * reg[0] 存入 dMem[1 + reg[5]] gp
* <- assign * (fact := 1)
* -> repeat
* repeat: jump after body comes back here
* -> assign
* -> Op
* -> Id
16: LD 0,1(5) load id value * reg[0] = dMem[1 + reg[5]] (fact)
* <- Id
17: ST 0,0(6) op: push left * reg[0] 存入 dMem[0 + reg[6]]
* -> Id
18: LD 0,0(5) load id value * reg[0] = dMem[0 + reg[5]] (x)
* <- Id
19: LD 1,0(6) op: load left * reg[1] = dMem[0 + reg[6]]
20: MUL 0,1,0 op * * reg[0] = reg[1] * reg[0]
* <- Op * (fact := fact * x)
21: ST 0,1(5) assign: store value * reg[0] 存入 dMem[1 + reg[5]] (fact)
* <- assign
* -> assign
* -> Op
* -> Id
22: LD 0,0(5) load id value * reg[0] = dMem[0 + reg[5]] (x)
* <- Id
23: ST 0,0(6) op: push left * reg[0] 存入 dMem[0 + reg[6]] (x)
* -> Const
24: LDC 0,1(0) load const * reg[0] = 1
* <- Const
25: LD 1,0(6) op: load left * reg[1] = dMem[0 + reg[6]] (x)
26: SUB 0,1,0 op - * reg[0] = reg[1] - reg[0] (x := x - 1)
* <- Op
27: ST 0,0(5) assign: store value * reg[0] 存入 dMem[0 + reg[5]] (更新x)
* <- assign
* -> Op
* -> Id
28: LD 0,0(5) load id value * reg[0] = dMem[0 + reg[5]] (x)
* <- Id
29: ST 0,0(6) op: push left * reg[0] 存入 dMem[0 + reg[6]]
* -> Const
30: LDC 0,0(0) load const * reg[0] = 0
* <- Const
31: LD 1,0(6) op: load left * reg[1] = dMem[0 + reg[6]] (x)
32: SUB 0,1,0 op == * reg[0] = reg[1] - reg[0]
33: JEQ 0,2(7) br if true * reg[0] == 0 ? reg[7] += 2 ==> 35
34: LDC 0,0(0) false case * reg[0] = 0
35: LDA 7,1(7) unconditional jmp * reg[7] = reg[7] + 2 ==> 37
36: LDC 0,1(0) true case * reg[0] = 1
* <- Op
37: JEQ 0,-22(7) repeat: jmp back to body * reg[0] == 0 ? reg[7] -= 21 ==> 26
* <- repeat
* -> Id
38: LD 0,1(5) load id value * reg[0] = dMem[1 + reg[5]]
* <- Id
39: OUT 0,0,0 write ac * write fact
* if: jump to end belongs here
13: JEQ 0,27(7) if: jmp to else * reg[0] == 0 ? reg[7] += 28 ==> 41
40: LDA 7,0(7) jmp to end * reg[7] = reg[7] + 1 ==> 41
* <- if
* End of execution.
41: HALT 0,0,0 * HALT
C－代码生成器的实现
与TINY语言相比，很明显的就能看出，C Minus语言所需要的目标代码远不止TINY这么简单，还要涉及到函数的调用、数组的处理等问题。
因此相对于TINY，在这里还增加了ebp和esp两个寄存器，用来保存栈帧信息：
#define esp 6
#define ebp 4
初始化时，esp也要进行初始化，以为全局变量留下一定的空间：
static void codeGenInit(void) {
int size = get_global_var_num();
emitComment("Standard prelude:");
emitRM("LD", gp, 0, 0, "gp=dMem[0] (dMem[0]==maxaddress)");
emitRM("ST", 0, 0, 0, "dMem[0]=0 (clear location 0)");
emitRM("LDA", esp, -size + 1, gp, "esp=gp-global_var_num+1");
emitComment("End of standard prelude.");
}
通过语义分析时保存的符号表，使用get_global_var_num进行遍历就能够得到全局变量的数量。
与TINY不同的第二点，在于标准IO作为函数的形式出现，所以需要先为其生成相应的目标代码，以便在之后跳转时得到对应的地址：
static void codeGenInput(void) {
if (TraceCode) emitComment("-> pre-defined function: input");
TreeNode *inputTree = st_func_lookup("input");
FuncInfo *funcInfo = makeFuncInfo(inputTree);
funcInfo->inst_addr = emitSkip(0);
if ((inputTree != NULL) && (funcInfo != NULL))
push_func(funcInfo);
else
exit(-1);
func_in("input");
emitRO("IN", ac, 0, 0, "input ac");
func_ret();
if (TraceCode) emitComment("<- pre-defined function: input");
}
static void codeGenOutput(void) {
if (TraceCode) emitComment("-> pre-defined function: output");
TreeNode *outputTree = st_func_lookup("output");
FuncInfo *funcInfo = makeFuncInfo(outputTree);
funcInfo->inst_addr = emitSkip(0);
if ((outputTree != NULL) && (funcInfo != NULL))
push_func(funcInfo);
else
exit(-1);
func_in("output");
emitRM("LD", ac, 2, ebp, "ac=dMem[ebp+2] (param 0)");
emitRO("OUT", ac, 0, 0, "output ac");
func_ret();
if (TraceCode) emitComment("<- pre-defined function: output");
}
这里可以看到使用了一个新的数据结构：FuncInfo，保存了每个函数的信息，这里之后在详细介绍。通过emitSkip函数，可以获得当前指令的地址，只需要将参数设为0不跳过任何值即可，这也为之后的函数调用提供了跳转的地址。
变量相关部分
数据结构：
int globalIndex = 0;
typedef struct varNode {
char *name;
int index;
struct varNode *next;
} VarNode;
static VarNode *globalVars = NULL;
通过varNode的结构体保存了每个变量的信息，包括名称和在当前作用域内的相对位置即index值。
static void push_global(char *name) {
VarNode *v = (VarNode *)malloc(sizeof(VarNode));
v->name = copyString(name);
v->index = globalIndex++;
v->next = globalVars;
globalVars = v;
}
static void traverseGlobal(TreeNode *root) {
if (root == NULL)
return;
if (root->nodekind == StmtK) {
if ((root->kind.stmt == VarDecK) || (root->kind.stmt == ArrayDecK))
push_global(root->attr.name);
}
traverseGlobal(root->sibling);
}
static int isGlobalVar(TreeNode *t) {
VarNode *v = globalVars;
if (t->declNode->scope == 0) {
while (v != NULL) {
if (strcmp(v->name, t->attr.name) == 0)
return TRUE;
v = v->next;
}
}
return FALSE;
}
对于全局变量，其不在任何作用域内，所以需要单独进行插入，遍历抽象语法树，可以得到相应的声明的变量，这里可以看到只是访问其兄弟节点（line 18），所以就避免了访问在作用域内变量的情况。如果检测到了一个变量，那么就调用push_global函数将其插入到之前声明的globalVars链表内。还提供了一个判断是否是全局变量的函数，实质与语义分析中符号表的查找函数类似，即遍历链表查看名称是否相同。
函数声明部分
数据结构
typedef struct funcInfo {
char *name;
int para_num; // 参数数量
int var_num; // 作用域内变量数量
int inst_addr; // 起始地址
TreeNode *dec; // 对应的抽象语法树结点
VarNode *vars; // 作用域内的变量链表
VarNode *params;// 传入的参数链表
struct funcInfo *next;
} FuncInfo;
static FuncInfo *functionList = NULL;
通过FuncInfo的结构体，保存每个函数内的变量信息。具体每一部分的值都在注释中说明。
构造函数信息
在遇到每个函数名时，首先调用了makeFuncInfo函数来进行函数信息的构建。特别的，对于input和output两个内置函数，不需要遍历只是简单按照其特性进行赋值即可：
if (strcmp(dec->attr.name, "input") == 0) {
info->var_num = 0;
info->vars = NULL;
info->para_num = 0;
info->params = NULL;
return info;
} else if (strcmp(dec->attr.name, "output") == 0) {
info->var_num = 0;
info->vars = NULL;
info->para_num = 1;
vTmp = (VarNode *)malloc(sizeof(VarNode));
vTmp->index = 0;
vTmp->name = copyString(dec->child[0]->attr.name);
if (info->params == NULL)
info->params = vTmp;
else {
vTmp->next = info->params;
info->params = vTmp;
}
return info;
}
对于input函数，不存在参数，只是设置其函数信息即可；对output还需要设置参数。
对于其他的函数，则需要获取其树节点，遍历参数列表和变量列表：
params = dec->child[0]; // 用于获取参数
compound_stmt = dec->child[1];
local_declarations = compound_stmt->child[0]; // 用于获取变量
获取参数部分：
if (params->type == Void)
info->para_num = 0;
else {
tmp = params;
while (tmp != NULL) {
if (tmp->kind.exp == IdArrayK) {
info->para_num += tmp->child[0]->attr.val;
}
else info->para_num++;
vTmp = (VarNode *)malloc(sizeof(VarNode));
if (tmp->kind.exp == IdArrayK) {
vTmp->index = index;
index += tmp->child[0]->attr.val;
}
else vTmp->index = index++;
vTmp->name = copyString(tmp->attr.name);
if (info->params == NULL)
info->params = vTmp;
else {
vTmp->next = info->params;
info->params = vTmp;
}
tmp = tmp->sibling;
}
}
首先判断参数是否为空，不为空则需要进行遍历。这里还需要进行的判断，就是当前的参数是不是数组形式，如果是，那么对应的参数个数不能只是简单的+1，而应该加上这个数组的个数（line 6 - 9），并且对于数组的偏移即index值，也要进行相应的处理（line 11 - 15）。之后就是将得到的参数插入到当前函数的参数链表中（line18-23）。
获取变量部分：
if (local_declarations == NULL)
info->var_num = 0;
else {
index = 0;
tmp = local_declarations;
while (tmp != NULL) {
if (tmp->kind.exp == IdArrayK) {
info->var_num += tmp->child[0]->attr.val;
}
else info->var_num++;
vTmp = (VarNode *)malloc(sizeof(VarNode));
if (tmp->kind.exp == IdArrayK) {
vTmp->index = index;
index += tmp->child[0]->attr.val;
}
else vTmp->index = index++;
vTmp->name = copyString(tmp->attr.name);
if (info->vars == NULL)
info->vars = vTmp;
else {
vTmp->next = info->vars;
info->vars = vTmp;
}
tmp = tmp->sibling;
}
}
其具体的处理都和参数部分相同，只不过修改的函数信息都是和变量相关而非和参数相关。
构造之后还要把它放到声明好的函数信息链表中：
static void push_func(FuncInfo *f) {
f->next = functionList;
functionList = f;
}
查找功能
查找当前函数的函数信息，这部分只需要简单的遍历链表进行查找即可。同样的，也是根据名字是否匹配来作为是否查找到的标准
static FuncInfo *lookup_func(char *name) {
FuncInfo *func_ret = functionList;
while (func_ret != NULL) {
if (strcmp(func_ret->name, name) == 0)
return func_ret;
func_ret = func_ret->next;
}
return NULL;
}
查找变量的偏移值。对于一个变量而言，要么在该函数内作为参数，要么为被声明的变量，所以对于函数信息维护的两个链表都进行查找即可完成
static int offset(char *name) {
FuncInfo *f = lookup_func(currentFuncName);
VarNode *vTmp;
if (f != NULL) {
vTmp = f->vars;
while (vTmp != NULL) {
if (strcmp(vTmp->name, name) == 0) {
return vTmp->index;
}
vTmp = vTmp->next;
}
vTmp = f->params;
while (vTmp != NULL) {
if (strcmp(vTmp->name, name) == 0) {
return vTmp->index;
}
vTmp = vTmp->next;
}
}
return -1;
}
判断是否为参数，同样是对于链表进行遍历查找，如果存在于函数信息维护的参数链表中，则是参数：
static int isParam(char *name) {
int func_ret;
int ofs = offset(name);
if (ofs == -1)
return -1;
FuncInfo *f = lookup_func(currentFuncName);
VarNode *params = f->params;
while (params != NULL) {
if (strcmp(params->name, name) == 0)
return TRUE;
params = params->next;
}
return FALSE;
}
函数调用
这一部分仿照x86架构的汇编代码实现，通过ebp和esp寄存器开辟一个栈，并在退出时销毁。这就涉及到两个部分：保存现场和恢复现场
进入新栈帧
static void func_in(char *name) {
FuncInfo *f = lookup_func(name);
int size = f->var_num;
if (TraceCode) emitComment("-> function head");
push_reg(ebp, "PUSH EBP");
emitRM("LDA", ebp, 0, esp, "MOV EBP, ESP");
emitRM("LDA", esp, -size, esp, "ESP -= # var");
if (TraceCode) emitComment("<- function head");
}
进入新的栈帧时，要做的自然就是保存之前的ebp，以便于在退出时正确的恢复上一个栈空间；之后，将ebp移到esp指向的位置，然后esp移动一定的位置，开辟新的栈。这一个移动的位置，是根据当前函数中包含的变量的数量决定的。
退出栈帧
static void func_ret() {
if (TraceCode) emitComment("-> function tail");
emitRM("LDA", esp, 0, ebp, "MOV ESP, EBP");
pop_reg(ebp, "POP EBP");
pop_reg(pc, "Return addr; POP PC");
if (TraceCode) emitComment("<- function tail");
}
退出时，同样的，首先摧毁这一个栈，通过移动esp来实现，之后得到旧的ebp，然后得到返回地址赋值给PC，从而实现了正常得退出。
函数调用
static void call(FuncInfo *f) {
char *name = f->name;
int inst_addr = f->inst_addr;
int arg_num = f->para_num;
if (TraceCode) {
emitComment("-> call");
emitComment(name);
}
emitRM("LDA", ac, 3, pc, "ac = pc + 3 (next pc)");
push_reg(ac, "PUSH AC (return address)");
emitRM("LDC", pc, inst_addr, 0, "pc = address (jmp to called function)");
emitRM("LDA", esp, arg_num, esp, "esp = esp + arg_num");
if (TraceCode) emitComment("<- call");
}
上述进入栈时，还未实现的部分就是保存返回地址，这一部分放在了函数调用部分实现。通过调用call函数，将返回地址压栈，然后PC指向跳转到的函数的起始地址，并且esp移动一定的位置用于保存传入的参数。
压栈弹栈
上面的操作大多都涉及到了push_reg和pop_reg两个函数
static void push_reg(int reg, char *str) {
emitRM("LDA", esp, -1, esp, str);
emitRM("ST", reg, 0, esp, "");
}
static void pop_reg(int reg, char *str) {
emitRM("LD", reg, 0, esp, str);
emitRM("LDA", esp, 1, esp, "");
}
由于每次压栈弹栈都是要在栈顶进行操作，所以都是对esp进行移动。压栈时将esp - 1（栈向低地址增长），然后将相应的寄存器的值压入esp指向的内存中。而弹栈则是相反的操作：先把元素弹出，esp + 1
获取局部变量
由于在函数内部操作时，需要得到参数或者内部声明的变量，此时就需要获得之前对每个变量设置的index，从而得到在该作用于范围内的位置。通过一个getVar函数实现
void getVar(TreeNode *var) {
int isPar = isParam(var->attr.name);
int isGlob = isGlobalVar(var);
int ofs = offset(var->attr.name);
if (isGlob == FALSE && ofs == -1) {
printf("%s\n", var->attr.name);
printf("some error! in getVar\n");
return;
}
if (TraceCode) emitComment("-> get variable");
if (isPar == TRUE) {
if (var->kind.exp == IdK) {
emitRM("LDA", ac, ofs + 2, ebp, "ac = ebp+offset+2");
} else if (var->kind.exp == IdArrayK) {
emitRM("LDA", ac1, ofs + 2, ebp, "ac1 = ebp+offset+2");
}
} else {
if (var->nodekind == ExpK) {
switch (var->kind.exp) {
case IdK:
if (isGlobalVar(var))
emitRM("LDA", ac, -ofs, gp, "ac = gp - offset");
else
emitRM("LDA", ac, -1 - ofs, ebp, "ac = ebp-offset-1");
break;
case IdArrayK:
if (isGlobalVar(var))
emitRM("LDA", ac1, -ofs, gp, "ac1 = gp - offset");
else
emitRM("LDA", ac1, -1 - ofs, ebp, "ac1 = ebp-offset-1");
break;
default:
break;
}
}
}
if (TraceCode) emitComment("<- get variable");
} /* getVar */
首先进行合法性检查（line 6 - 10）。之后，如果是参数的话，其对应的位置位于 ebp + 2 + offset 处，因为ebp和ebp + 1处分别为old ebp以及返回地址，所以从ebp + 2开始取参数（line 13 - 19）。如果是变量，则要看是否为全局变量，在进行相应的地址的读取（line 20 - 38）。
这里处理数组时，将数组的起始地址加载进了ac1寄存器而非ac寄存器，因为之后读取数组的下标时，要存放到ac寄存器，之后再做减法才能得到数组元素的地址。所以这里加载进ac1，之后减法为：ac = ac1 - ac，这样就可以把数组元素的地址加载进入ac。
代码生成
通过codeGen接口开始进入代码生成部分，调用cGen对语法树进行遍历，通过不同的树结点类型：Stmt或Exp来调用genStmt或genExp函数从而再执行对应的代码生成部分。
由于程序的入口位于main函数，所以在codeGen内，需要先进行emitSkip，为main函数留出分配的地址，最后回填。
emitComment("skip 5 instr: call main, waiting for addr of main");
mainLoc = emitSkip(5);
emitRO("HALT", 0, 0, 0, "stop program");
……
emitBackup(mainLoc);
call(lookup_func("main"));
emitRestore();
这里跳过5的原因，是因为在call调用时，会压入5条指令，要为这5条指令留出空间。
变量
变量涉及到取地址还是取值的问题：
case IdK:
if (TraceCode) emitComment("-> Id");
getVar(tree);
if (getInfo == VALUE)
emitRM("LD", ac, 0, ac, "ac=dMem[ac]");
if (TraceCode) emitComment("<- Id");
break;
case IdArrayK:
if (TraceCode) emitComment("-> Array Id");
getVar(tree);
saved_config = getInfo;
getInfo = ADDRESS;
cGen(tree->child[0]);
getInfo = saved_config;
emitRO("SUB", ac, ac1, ac, "ac=ac1-ac (array offset)");
if (getInfo == VALUE)
emitRM("LD", ac, 0, ac, "ac=dMem[ac]");
if (TraceCode) emitComment("<- Array Id");
break;
通过一个getInfo保存当前要取得状态，如果取地址，则不执行LD命令的代码生成，否则执行LD的代码生成，将ac寄存器指向的内存的值存入ac寄存器。
很显然的，当前结点为数组类型，那么取其起始地址时应当是取地址操作（line 13），因为这样才能在取数组元素时得到正确的地址。之后要根据取数组前的状态来进行选择。
在赋值ASSIGN操作中，左值应当对应的是地址，右值对应的是值，因为最终是要把右值写入左值对应的内存中。
在调用call进行函数调用时，参数压栈时也应当压入的是值。
CALL函数调用
在对CALL进行代码生成时，涉及到参数压栈的操作：
TreeNode *p = tree->child[0];
while (p != NULL) {
pushParam(p);
p = p->sibling;
}
siblingRecur = FALSE;
while ((p = popParam()) != NULL) {
getInfo = VALUE;
cGen(p);
push_reg(ac, "PUSH AC (for argument)");
}
siblingRecur = TRUE;
这里首先把参数保存在链表中，之后依次取出，对参数按照其类型进行代码生成（调用cGen），再把对应的ac寄存器压入栈中（此时ac寄存器保存的是该参数的值）。这里设置了siblingRecur变量，为了防止在cGen函数内对其sibling结点的递归调用（那样的话，就没有办法把ac寄存器压栈了）。
while循环
这里的while循环实质上就是替代了TINY的repeat和until语句
case WhileK:
if (TraceCode) emitComment("-> while");
savedLoc1 = emitSkip(0);
emitComment("while: comes back here after body");
cGen(tree->child[0]);
savedLoc2 = emitSkip(1);
emitComment("while: conditional jmp to end");
cGen(tree->child[1]);
emitRM("LDC", pc, savedLoc1, 0, "while: go back; pc=addr of condition");
currentLoc = emitSkip(0);
emitBackup(savedLoc2);
emitRM("JEQ", ac, currentLoc, 0, "while: if ac==0, pc=addr of endwhile");
emitRestore();
if (TraceCode) emitComment("<- while");
break;
首先通过emitSkip函数获得循环起始地址，生成条件式，在进行一个emitSkip(1)跳过一条语句，用于之后不符合要求时回填。之后生成循环体，再加入两个条件判断语句，看要如何跳转。
剩余的部分都和TINY部分大致相同。
实验结果
测试样例1 test.cm
/* A Program to perform Euclid`s
Algorithm to computer gcd */
int gcd (int u, int v)
{
if (v == 0) return u;
else return gcd(v,u-u/v*v);
/* u-u/v*v == u mod v */
}
void main(void)
{
int x; int y;
x = input(); y = input();
output(gcd(x, y));
}
运行结果：
测试样例2 Arraytest.cm
void main(void)
{
int a[3]; int b[3];
int x; int y;
a[0] = 1; a[1] = 2; a[2] = 3;
x = 4; y = 5;
output(a[0]); output(a[1]); output(a[2]);
b[0] = a[2]; b[1] = a[1]; b[2] = y;
output(b[0]); output(b[1]); output(b[2]);
}
运行结果：
结果均与预期相符。
惟楚有才，于斯为盛。欢迎来到长沙！！！ 茶颜悦色、臭豆腐、CSDN和你一个都不能少~
更多推荐
1
0- 0
已为社区贡献4条内容
所有评论(0)