学习经典的代码生成器
代码已开源： /LinXiaoDe/Quary/tree/master/lab6一.实验目的
学习已有编译器的经典代码生成源程序
二.实验任务
阅读已有编译器的经典代码生成源程序，并测试代码生成器的输出
三.实验内容
选择一个编译器，如：TINY或PL/0，其它编译器也可（需自备源代码）。
阅读TM虚拟机的有关文档（请参考《编译原理及实践》第8.7节）。了解TM机的指令结构与寻址方式等相关内容。
阅读代码生成源程序，加上你自己的理解。尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。
测试代码生成器。请对生成的目标代码逐行加上注释，增强其可读性。
TINY语言：
测试用例一：sample.tny。
测试用例二：用TINY语言自编一个程序计算任意两个正整数的最大公约数与最大公倍数。
1.选择一个编译器
在这里，我仍然选择Tiny编译器，对于Tiny所有的代码，我们可以从实验一中获取，或者访问网址：/bigconvience/BooksCode 获取，注意，我使用的是Linux操作系统，所以下载Linux版本的包。如下图所示：
2.阅读TM虚拟机的有关文档，了解TM机的指令结构与寻址方式等相关内容
参考《编译原理及实践》第8.7节，我了解了了TM机的指令结构与寻址方式等相关内容，下面我将从这几个方面来阐述内容：(1) Tiny Machine的基本结构
TM由只读指令存储区、数据区和 8个通用寄存器构成。它们都使用非负整数地址且以 0开始。寄存器7为程序记数器，它也是唯一的专用寄存器，如下面所描述的那样。 C的声明：#define IADDR_SIZE 1024 // size of instruction memory 读指令存储区大小#define DADDR_SIZE 1024 // size of data memory 数据区大小#define NO_REGS 8 // 通用寄存器个数#define PC_REG 7 // 程序计数器INSTRUCTION iMem [IADDR_SIZE]; // 定义读指令存储区大小int dMem [DADDR_SIZE];// 数据区大小 int reg [NO_REGS]; // 定义寄存器
T M执行一个常用的取指-执行循环，取指，译码，执行：
do/* fetch */current Instruction = iMem [reg[pcRegNo]++];/* execute current instruction */...while (!(halt||error));
指令执行过程：
在开始点， Tiny Machine将所有寄存器和数据区设为 0，然后将最高正规地址的值 (名为D A D D R _ S I Z E - 1)装入到d M e m [ 0 ]中。 (由于程序可以知道在执行时可用内存的数量，所以它允许将存储器很便利地添加到 T M上)。 T M然后开始执行i M e m [ 0 ]指令。机器在执行到H A L T指令时停止。可能的错误条件包括 I M E M _ E RR (它发生在取指步骤中若r e g [ P C _ R E G ]< 0或r e g [ P C _ R E G ]≥I A D D R _ S I Z E时)，以及两个条件D M E M _ E R R和Z E R O - D I V，它们发生在下面描述的指令执行中
TINY Machine 的完全指令集如下，基本指令格式有两种：寄存器，即RO指令。寄存器-存储器，即RM指令。他们都在tm.c中被定义：
(2) TM模拟器特性
TM模拟器约定：这个模拟器接受包含上面所述的T M指令的文本文件， 并有以下约定：
忽略空行。以星号打头的行被认为是注释而忽略。任何其他行必须包含整数指示位置后跟冒号再接正规指令。任何指令后的文字都被认为是注释而被忽略掉。
TM模拟器命令：注意：T M模拟器没有其他特征了——特别是没有符号标号和宏能力。
3.阅读代码生成源程序，加上自己的理解
尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。
(1) 程序清单
在本实验中，代码生成相关的文件有三个，下面我将会就这些文件的功能做一个快速列举。一些代码生成器需要知道的有关 TM的信息已封装在文件code.h和code.c中
(2) 文件code.h 和code.c
一些代码生成器需要知道的有关 TM的信息已封装在文件code.h 和code.c 中
寄存器值的定义：
代码生成器和代码发行实用程序必须知道 pc。另外还有TINY语言的运行时环境，将数据存储时的顶部分配给临时存储 (以栈方式)而底部则分配给变量。由于 T I N Y中没有活动记录(于是也就没有f p ) (没有作用域和过程调用 )，变量和临时存储的位置可认为是绝对的。然而， T M机的L D操作不允许绝对地址，而必须有一个寄存器基值来计算存储装入的地址。这样我们分配两个寄存器
称为mp (内存指针)和gp (全程指针)来指示存储区的顶部和底部：
mp将用于访问临时变量，并总是包含最高正规内存位置gp用于所有命名变量访问，并总是包含 0。这样由符号表计算的绝对地址可以生成相对 g p的偏移来使用。例如，如果程序使用两个变量x和y，并有两个临时值存在内存中，那么d M e m将如下所示，t 1的地址为0 ( m p )，t 2为- 1 ( m p )，x的地址为0 ( g p )，而y为1 ( g p )。在这个实现中， g p是寄存器5， m p是寄存器6。
/* 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
另两个代码生成器将使用的寄存器是寄存器 0和1，寄存器 0和1，称之为“累加器”并命令名为 ac和ac1。它们被当作相等的寄存器来使用。通常计算结果存放在 a c中。注意寄存器2、 3和4没有命名(且从不使用1 )
7个代码发行函数
emitComment：如果TraceCode标志置位，emitComment函数会以注释格式将其参数串打印到代码文件中的新行中。
void emitRM( char * op, int r, int d, int s, char *c){fprintf(code,"%3d: %5s %d,%d(%d) ",emitLoc++,op,r,d,s);if (TraceCode) fprintf(code,"\t%s",c) ;fprintf(code,"\n") ;if (highEmitLoc < emitLoc) highEmitLoc = emitLoc ;} /* emitRM */
emitRO和emitRM：
emitRO和emitRM为标准的代码发行函数用于R O和R M指令类。除了指令串和3个操作数之外，每个函数还带有1个附加串参数，它被加到指令中作为注释 (如果TraceCode标志置位)。
void emitRO( char *op, int r, int s, int t, char *c){fprintf(code,"%3d: %5s %d,%d,%d ",emitLoc++,op,r,s,t);if (TraceCode) fprintf(code,"\t%s",c) ;fprintf(code,"\n") ;if (highEmitLoc < emitLoc) highEmitLoc = emitLoc ;} /* emitRO */void emitRM( char * op, int r, int d, int s, char *c){fprintf(code,"%3d: %5s %d,%d(%d) ",emitLoc++,op,r,d,s);if (TraceCode) fprintf(code,"\t%s",c) ;fprintf(code,"\n") ;if (highEmitLoc < emitLoc) highEmitLoc = emitLoc ;} /* emitRM */
产生和回填转移
接下来的3个函数用于产生和回填转移。 emitSkip函数用于跳过将来要反填的一些位置并返回当前指令位置且保存在code.c内部。典型的应用是调用emitSkip(1)，它跳过一个位置，这个位置后来会填上转移指令，而emit Skip(0)不跳过位置，调用它只是为了得到当前位置以备后来的转移引用。函数emitBackup用于设置当前指令位置到先前位置来反填，emitRestore用于返回当前指令位置给先前调用emitBackup的值。
int emitSkip( int howMany){int i = emitLoc;emitLoc += howMany ;if (highEmitLoc < emitLoc) highEmitLoc = emitLoc ;return i;} /* emitSkip */void emitBackup( int loc){if (loc > highEmitLoc) emitComment("BUG in emitBackup");emitLoc = loc ;} /* emitBackup */void emitRestore(void){emitLoc = highEmitLoc;}
最后代码发行函数(emitRM_Abs)用来产生诸如反填转移或任何由调用emitSkip返回的代码位置的转移的代码。它将绝对代码地址转变成 pc相关地址，这由当前指令位置加 1 (这是pc继续执行的地方 )减去传进的位置参数，并且使用 p c做源寄存器。通常地，这个函数仅用于条件转移，比如JEQ或使用LDA和pc作为目标寄存器产生无条件转移
void emitRM_Abs( char *op, int r, int a, char * c){fprintf(code,"%3d: %5s %d,%d(%d) ",emitLoc,op,r,a-(emitLoc+1),pc);++emitLoc ;if (TraceCode) fprintf(code,"\t%s",c) ;fprintf(code,"\n") ;if (highEmitLoc < emitLoc) highEmitLoc = emitLoc ;} /* emitRM_Abs */
(3) TINY代码生成器
TINY代码生成器在文件cgen.c中，其中提供给TINY编译器的唯一接口是CodeGen，函数CodeGen产生一些注释和指令 (称为标准序言(standard prelude)) 、设置启动时的运行时环境，然后在语法树上调用 cGen，最后产生H A L T指令终止程序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,"");}
函数cGen负责完成遍历并以修改过的顺序产生代码的语法树，函数c G e n仅检测节点是句子或表达式节点 (或空)，调用相应的函数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);}}
函数genExp：包含大量switch语句来区分5种句子，它产生代码并在每种情况递归调用cGen，genExp函数也与之类似。在任意情况下，子表达式的代码都假设把值存到 a c中而可以被后面的代码访问。当需要访问变量时 (赋值和read语句以及标识符表达式)，通过loc = lookup(tree->attr.name);操作访问符号表.
static void genExp( TreeNode * tree){int loc;TreeNode * p1, * p2;switch (tree->kind.exp) {case ConstK :if (TraceCode) emitComment("-> Const") ;/* gen code to load integer constant using LDC */emitRM("LDC",ac,tree->attr.val,0,"load const");if (TraceCode) emitComment("<- Const") ;break; /* ConstK */.........case IdK :if (TraceCode) emitComment("-> Id") ;.........break; /* IdK */case OpK :if (TraceCode) emitComment("-> Op") ;p1 = tree->child[0];p2 = tree->child[1];/* gen code for ac = left arg */emitRM("LD",ac1,++tmpOffset,mp,"op: load left");switch (tree->attr.op) {case PLUS :emitRO("ADD",ac,ac1,ac,"op +");case MINUS :emitRO("SUB",ac,ac1,ac,"op -");case TIMES :case OVER :case LT :case EQ :default:emitComment("BUG: Unknown operator");break;} /* case op */if (TraceCode) emitComment("<- Op") ;break; /* OpK */default:break;}} /* genExp */
4.测试代码生成器
首先我们要对请对生成的目标代码逐行加上注释，增强其可读性。
main.c中的编译选项进行适当修改，以便用代码生成器生成代码，另外如果想要产生注释需要设置TraceCode=TRUE，下面是我设置的结果：#define NO_PARSE FALSE#define NO_ANALYZE FALSE#define NO_CODE FALSEint EchoSource = FALSE;int TraceScan = FALSE;int TraceParse = FALSE;int TraceAnalyze = TRUE;int TraceCode = TRUE;
(1) 测试样例sample1.tny
下面是我准备的测试代码，它只是简单读入一个整数并且对它进行判断：read x; {input an integer }if 0 < x then {don't compute if x <= 0 }fact := 1;repeatfact := fact * x;x := x - 1until x = 0;write fact {output factorial of x }end
执行./tiny samples/sample1.tny生成目标代码： 下面是目标代码sample.tm，我将会对生成的目标代码逐行加上注释，增强其可读性，由于篇幅限制，我截取了其中的一部分。
* 标准预处理0:LD 6,0(0) 从位置0加载maxaddress1:ST 0,0(0) 清除位置0* 预处理结束2:IN 0,0,0 读入整型数据3:ST 0,0(5) 存储read进来的数据4: LDC 0,0(0) 加载const 05:ST 0,0(6) 压入比较操作的做操作数op: push left* -> Id6:LD 0,0(5) 加载 id = x * <- Id7:LD 1,0(6) op：加载左操作数8: SUB 0,1,0 op < 做小于比较9: JLT 0,2(7) 为真，小于10: LDC 0,0(0) 为假11: LDA 7,1(7) unconditional jmp12: LDC 0,1(0) true case.........................................* repeat: 循环操作 jump after body comes back here16:LD 0,1(5) 加载 id = x17:ST 0,0(6) op：压如左操作数18:LD 0,0(5) 加载id = x19:LD 1,0(6) 加载组左操作数20: MUL 0,1,0 op *乘法操作21:ST 0,1(5) assign: 赋值存储乘法结果.........................................39: OUT 0,0,0 write 操作，输出结果* if: 跳转到程序末尾13: JEQ 0,27(7) if: jmp to else40: LDA 7,0(7) jmp to end* <- if* End of execution.41: HALT 0,0,0 HALT 停机
(2) 测试样例Euclid.tny
这是我用TINY语言自编一个程序计算任意两个正整数的最大公约数与最大公倍数。read x;read y;S:=x*y;if x < y then cur := x;x := y;y := curend;repeatcur := x - (x / y)*y;x := y;y := curuntil y = 0;write x;write (S / x)
执行./tiny samples/Euclid.tny生成目标代码： 下面是目标代码Euclid.tm，我将会对生成的目标代码逐行加上注释，增强其可读性，由于篇幅限制，我截取了其中的一部分。
* 标准预处理0:LD 6,0(0) 从位置0加载maxaddress1:ST 0,0(0) 清除位置0* 预处理结束2:IN 0,0,0 read 读入整型数据 x3:ST 0,0(5) read: 保存数据 x4:IN 0,0,0 read 读入整型数据 y5:ST 0,1(5) read: 保存数据 yMUL 乘法 操作：6:LD 0,0(5) 加载 id 值 x * <- 压入操作数 x7:ST 0,0(6) op: push left* -> Id8:LD 0,1(5) 加载 id = y* <- 压入操作数 y9:LD 1,0(6) 加载操作数 y10: MUL 0,1,0 做乘法操作* <- Op11:ST 0,2(5) assign: 保存到2(5)位置* 下面的 if 操作和 reapt操作在sample1中已经分析过了，我们跳过，重点看一看除法操作* -> 除法* -> Id31:LD 0,0(5) load id 加载id变量* <- Id32:ST 0,-1(6) op: 加入左操作数* -> Id33:LD 0,1(5) load id 加载id变量* <- Id34:LD 1,-1(6) op: 加载id35: DIV 0,1,0 op / 执行除发法操作* <- Op36:ST 0,-1(6) op: push left* -> Id37:LD 0,1(5) load id value* <- Op64: OUT 0,0,0 write ac 输出结果ac* End of execution.65: HALT 0,0,0 HALT停机
实现一门语言的代码生成器
一.实验目的
通过本次实验，加深对代码生成的理解，学会编制代码生成器。
##二.实验任务
用C或JAVA语言编写一门语言的代码生成器。
三.实验内容
语言确定：C－语言，其定义在《编译原理及实践》附录A中。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。完成对TM机的改造设计，以满足C－语言的要求。详情请参见C－语言的定义文档。仿照前面学习的代码生成器，编写选定语言的代码生成器。准备2~3个测试用例，测试你的程序，并逐行解释生成的目标代码。
1. 语言确定
C－语言，其定义在《编译原理及实践》附录A中。也可选择其它语言，不过要有该语言的详细定义（可仿照C－语言）。一旦选定，不能更改，因为要在以后继续实现编译器的其它部分。鼓励自己定义一门语言。
同样的，在本次实验中我仍然选择的是Cminus语言，我将采用增量编程的思想，借鉴TINY的设计思想进行设计。
2.完成对TM机的改造设计
完成对TM机的改造设计，以满足C－语言的要求。详情请参见C－语言的定义文档。
分析：对于Cminus虚拟机，我借鉴TINY虚拟机的寄存器，存储区，以及指令设计，下面是Cminux 的TM虚拟机设计：
Cminus TM由只读指令存储区、数据区和 8个通用寄存器构成。它们都使用非负整数地址且以 0开始。寄存器7为程序记数器，它也是唯一的专用寄存器，如下面所描述的那样。 C的声明：
#define IADDR_SIZE 1024 // size of instruction memory 读指令存储区大小#define DADDR_SIZE 1024 // size of data memory 数据区大小#define NO_REGS 8 // 通用寄存器个数#define PC_REG 7 // 程序计数器INSTRUCTION iMem [IADDR_SIZE]; // 定义读指令存储区大小int dMem [DADDR_SIZE];// 数据区大小 int reg [NO_REGS]; // 定义寄存器
Cminus T M执行一个常用的取指-执行循环，取指，译码，执行：
do/* fetch */current Instruction = iMem [reg[pcRegNo]++];/* execute current instruction */...while (!(halt||error));
指令执行过程：
在开始点， Cminus Machine将所有寄存器和数据区设为 0，然后将最高正规地址的值 (名为D A D D R _ S I Z E - 1)装入到d M e m [ 0 ]中。 (由于程序可以知道在执行时可用内存的数量，所以它允许将存储器很便利地添加到 T M上)。 T M然后开始执行i M e m [ 0 ]指令。机器在执行到H A L T指令时停止。可能的错误条件包括 I M E M _ E RR (它发生在取指步骤中若r e g [ P C _ R E G ]< 0或r e g [ P C _ R E G ]≥I A D D R _ S I Z E时)，以及两个条件D M E M _ E R R和Z E R O - D I V，它们发生在下面描述的指令执行中
Cminus Machine 的完全指令集如下，基本指令格式有两种：寄存器，即RO指令。寄存器-存储器，即RM指令。他们都在tm.c中被定义：
3.仿照前面学习的代码生成器，编写选定语言的代码生成器。
对于代码生成器，我们要修改的文件是cgen.c，代码生成器。下面我将会结合Cminus的语言进行设计：
(1) 新增变量和函数声明
在代码生成器cgen.c中我新增了许多变量，现在我吧他们列举在下面：
下面我将对其中几个重要部分进行详细说明。
(2) genStmt 语句节点生成代码
算法思想：getStmt——分析含有保留关键字语句的函数，该函数的作用主要是处理Cminus语言中所包含的关键字;
typedef enum{START,INLT,INGT,INEQ,INNOT,INSLASH,INCOMMENT,INCOMMENTSTAR,INNUM,INID,DONE }StateType;
这里以if作为一个例子来分析说明这个函数需要做的工作：if结点包括三个子结点，if本身的判断表达式、{}、以及else（通常，else可以被省略）。我们对于每个if的子结点递归分析（因为if的子结点可能也会是一个表达式，比如if的条件判断，这样的话就需要对它进行递归分析）。
用savedLoc变量记录递归的返回位置，待分析完这一条路径之后，就可以找到函数在哪里被调用了，在调用的过程中，由于各个节点都需要递归地访问，因此这里在处理下一个节点的时候，使用了emitSkip这个函数，用于跳过并保存当前点的位置，以便于函数最后的返回工作。（也就是回填）
int emitSkip( int howMany){int i = emitLoc;emitLoc += howMany ;if (highEmitLoc < emitLoc) highEmitLoc = emitLoc ;return i;} /* emitSkip */
其他的处理也是类似的。
如何处理子结点？如图所示，我们获取了结点的类型，也能够获取结点的逻辑关系，此时，只要调用刚刚提到的函数emit，就可以将这条指令写到输出文件中，使得最后的Cminus虚拟机能够执行完成。
case RetK:if (TraceCode) emitComment("-> return");p1 = tree->child[0];/* generate code for expression */cGen(p1);emitRM("LD",pc,retFO,mp,"return: to caller");if (TraceCode) emitComment("<- return");break; /* return_k */default:break;
下面是部分genStmt其他关键字的实现过程：
// 过程genStmt在语句节点生成代码static void genStmt( TreeNode * tree ){TreeNode * p1, * p2, * p3;int savedLoc1,savedLoc2,currentLoc;int loc;int offset;switch (tree->kind.stmt) {case CompK:if (TraceCode) emitComment("-> compound");p1 = tree->child[0];p2 = tree->child[1];/* update localOffset with the offset derived from declarations */offset = getBlockOffset(p1);localOffset -= offset;/* push scope */sc_push(tree->attr.scope);/* generate code for body */cGen(p2);/* pop scope */sc_pop();/* restore localOffset */localOffset -= offset;if (TraceCode) emitComment("<- compound");break;case IfK:if (TraceCode) emitComment("-> if");p1 = tree->child[0];p2 = tree->child[1];p3 = tree->child[2];/* generate code for test expression */cGen(p1);savedLoc1 = emitSkip(1);emitComment("if: jump to else belongs here");/* recurse on then part */cGen(p2);savedLoc2 = emitSkip(1);emitComment("if: jump to end belongs here");currentLoc = emitSkip(0);emitBackup(savedLoc1);emitRM_Abs("JEQ",ac,currentLoc,"if: jmp to else");emitRestore();/* recurse on else part */cGen(p3);currentLoc = emitSkip(0);emitBackup(savedLoc2);emitRM_Abs("LDA",pc,currentLoc,"jmp to end");emitRestore();if (TraceCode) emitComment("<- if");break; /* select_k */case IterK:.............case RetK:............. }} /* genStmt */
(3) genExp 表达式节点生成代码
算法思想: 如果表达式的结点类型是ID或者数字，那么直接使用LD命令加载它。如果结点是一个运算符，运算符是由子结点构成的 例如：[id op id ]，它的子结点就是运算的两个数字，或者是ID字符。我们需要使用LD命令将子结点里面的具体数字或字符读取出来，再根据运算符的类型构造相应的TM code命令,op类型有：PLUS，MINUS，TIMES，OVER，LT，LTEQ，GT，GTEQ，EQ，NEQ
乘法op表达式节点对应的操作：
case PLUS:emitRO("ADD",ac,ac1,ac,"op +");break;
比较op表达式节点对应操作：
case EQ:emitRO("SUB",ac,ac1,ac,"op ==");emitRM("JEQ",ac,2,pc,"br if true");emitRM("LDC",ac,0,ac,"false case");emitRM("LDA",pc,1,pc,"unconditional jmp");emitRM("LDC",ac,1,ac,"true case");break;
下面是所有类型的实现（部分代码展示）
// 过程genExp在表达式节点生成代码static void genExp( TreeNode * tree, int lhs ){int loc;int varOffset, baseReg;int numOfArgs;TreeNode * p1, * p2;switch (tree->kind.exp) {case AssignK:if (TraceCode) emitComment("-> assign");p1 = tree->child[0];p2 = tree->child[1];genExp(p1, TRUE);emitRM("ST", ac, localOffset--, mp, "assign: push left (address)");cGen(p2);emitRM("LD", ac1, ++localOffset, mp, "assign: load left (address)");emitRM("ST", ac, 0, ac1, "assign: store value");if (TraceCode) emitComment("<- assign");break; /* assign_k */case OpK:if (TraceCode) emitComment("-> Op");p1 = tree->child[0];p2 = tree->child[1];cGen(p1);emitRM("ST",ac,localOffset--,mp,"op: push left");cGen(p2);emitRM("LD",ac1,++localOffset,mp,"op: load left");switch (tree->attr.op) {case PLUS:case MINUS:case TIMES:case OVER:case LT:case LTEQ:case GT:case GTEQ:case EQ:case NEQ:default:emitComment("BUG: Unknown operator");break;} /* case op */if (TraceCode) emitComment("<- Op");break; /* OpK */case ConstK:if (TraceCode) emitComment("-> Const") ;emitRM("LDC",ac,tree->attr.val,0,"load const");if (TraceCode) emitComment("<- Const") ;break; /* ConstK */case IdK:case ArrIdK:if (TraceCode) {sprintf(buffer, "-> Id (%s)", tree->attr.name);emitComment(buffer);}loc = st_lookup_top(tree->attr.name);if (loc >= 0)varOffset = initFO - loc;elsevarOffset = -(st_lookup(tree->attr.name));emitRM("LDC", ac, varOffset, 0, "id: load varOffset");if (tree->kind.exp == ArrIdK) {if (loc >= 0 && loc < numOfParams) {emitRO("ADD", ac, mp, ac, "id: load the memory address of base address of array to ac");emitRO("LD", ac, 0, ac, "id: load the base address of array to ac");} else {if (loc >= 0)emitRO("ADD", ac, mp, ac, "id: calculate the address");elseemitRO("ADD", ac, gp, ac, "id: calculate the address");}emitRM("ST", ac, localOffset--, mp, "id: push base address");p1 = tree->child[0];cGen(p1);emitRM("LD", ac1, ++localOffset, mp, "id: pop base address");emitRO("SUB", ac, ac1, ac, "id: calculate element address with index");} else {if (loc >= 0)emitRO("ADD", ac, mp, ac, "id: calculate the address");elseemitRO("ADD", ac, gp, ac, "id: calculate the address");}if (TraceCode) emitComment("<- Call");break; /* CallK */default:break;}} /* genExp */
(4) genParam在声明参数节点生成代码
实现思路：对当前语法树节点进行判断，如果说是数组声明，或者非数组声明，localOffset 减1，numOfParams参数数量加一；如果编译选项TraceCode被设置为TRUE，那么需要调用emitComment打印注释emitComment("<- param");.
static void genParam( TreeNode * tree){switch (tree->kind.stmt) {case ArrParamK:case NonArrParamK:if (TraceCode) emitComment("-> param");emitComment(tree->attr.name);--localOffset;++numOfParams;if (TraceCode) emitComment("<- param");break;default:break;}} /* genParam */
4.样例测试与分析
准备2~3个测试用例，测试你的程序，并逐行解释生成的目标代码。
(1) 测试样例sample1.c
下面是我准备的测试代码，自编一个程序计算任意两个正整数的最大公约数与最大公倍数。int gcd (int u, int v){if (v == 0) return u;else return gcd(v,u-u/v*v);}void main(void){int x; int y;x = input(); y = input();output(gcd(x,y));}
执行./cminus samples/sample1.c生成目标代码：
下面是目标代码sample1.tm，我将会对生成的目标代码逐行加上注释，增强其可读性，由于篇幅限制，我截取了其中的一部分。
* 标准预处理:0:LD 5,0(0) 用maxaddress加载gp1: LDA 6,0(5) 复制 gp 到 mp2:ST 0,0(0) 清除 0* 标准预处理结束* -> 函数段 Function (gcd)4:ST 1,-2(5) func: 保存当前函数的位置* func:无条件跳转到下一个声明属于这里* 函数体3: LDC 1,6(0) func: 加载函数位置6:ST 0,-1(6) func: 保存函数返回值地址* 参数处理7: LDC 0,-3(0) id: 加载变量的偏移量8: ADD 0,6,0 id: 计算地址9:LD 0,0(0) 加载id类型值* <- Id10:ST 0,-4(6) op: 左操作数* -> Const11: LDC 0,0(0) load 加载常数...这里是一些常规操作，与前面重复，我skip到return这些关键位置注释...* <- return返回语句* if: if跳转的最后位置18: JEQ 0,5(7) if: else 分支* -> return* -> Call* -> Id (v)24: LDC 0,-3(0) id: 加载变量的初始值25: ADD 0,6,0 id: 计算偏移量26:LD 0,0(0) 加载id* <- Id27:ST 0,-6(6) call: 压入返回参数* -> Op* -> Id (u)28: LDC 0,-2(0) 加载id29: ADD 0,6,0 id计算返回地址30:LD 0,0(0) 加载变量.....49:ST 0,-7(6) call: 压入变量50:ST 6,-4(6) call: 存储当前的mp51: LDA 6,-4(6) call: push新的函数栈52: LDA 0,1(7) call: 将返回值保存在ac寄存器53:LD 7,-2(5) call: 相对跳转到函数项54:LD 6,0(6) call: pop当前函数栈....省略一些常见基本操作，直接看到函数调用* -> Call94:ST 6,0(6) call: 保存当前mp指针95: LDA 6,0(6) call: push 一个新的帧栈96: LDA 0,1(7) call: 用ac保存返回值97: LDC 7,60(0) call: 无条件跳转到main98:LD 6,0(6) call: 弹出当前函数栈* <- Call* End of execution.99: HALT 0,0,0 HALT停机
(2) 测试样例sample2.tny
下面是我准备的测试代码, 包含数组的定义以及while循环和函数调用。void nil(void){;}int gcd(int a[], int b){a[2] = 1;b = 2;while(b < 3){int i;i = 5;if(i>5){int j;i = i+1;j = j+1;}i = a[2] + 5;}if(b > 10){b = b + 1;}else{b = b - 1;}return a[3];}void main(void){int k[10];int m;int n;gcd(k,m);}
执行./cminus samples/sample2.c生成目标代码： 下面是目标代码sample2.tm，我将会对生成的目标代码逐行加上注释，增强其可读性，由于篇幅限制，我截取了其中的一部分。
* 标准预处理:0:LD 5,0(0) 用maxaddress加载gp1: LDA 6,0(5) 复制 gp 到 mp2:ST 0,0(0) 清除 0* 标准预处理结束...跳过一下我们已经分析过的基础操作，看到while循环...* while: jump to end belongs here26: LDC 0,-2(0) id: 加载变量偏移量27: ADD 0,6,0 id: 计算地址28: LDA 0,0(0) load id 加载id地址* <- Id29:ST 0,-4(6) assign: push 压入左操作数* -> Const30: LDC 0,2(0) load 加载常数* <- Const31:LD 1,-4(6) assign: load 加载左操作数32:ST 0,0(1) assign: 保存变量* <- assign* <- compound33: LDA 7,-20(7) while: 跳转到条件测试25: JEQ 0,8(7) while: 跳转到end结束* while: jump after body comes back here 函数体回来后再跳........* <- Call* End of execution.55: HALT 0,0,0
(3) 测试样例error.c
为了保证我的程序可以顺序测试出一些语法错误，我使用了一个错误的样例对代码生成器进行测试int total(int i); /* error : semi */int unique(int i); /* error : semi */int main(){/* error : parameter */int N;int D;int A;D=total(N);A=unique(N);return 0;}
测试结果：
当我试图生成代码的时候，程序检测到了语法错误，并且抛出异常，Syntax error at line 1: syntax error，与预期相符合。
