编译原理实验六 / 代码生成器

学习经典的代码生成器代码已开源： https://github.com/LinXiaoDe/Quary/tree/master/lab6一.实验目的学习已有编译器的经典代码生成源程序二.实验任务阅读已有编译器的经典代码生成源程序，并测试代码生成器的输出三.实验内容选择一个编译器，如：TINY或PL/0，其它编译器也可（需自备源代码）。阅读TM虚拟机的有关文档（请参考《编译原理及实践》第8.7节）。

飞翔的哈士奇

3047人浏览 · 2021-01-25 20:13:15

飞翔的哈士奇 · 2021-01-25 20:13:15 发布

学习经典的代码生成器

代码已开源： https://github.com/LinXiaoDe/Quary/tree/master/lab6

一.实验目的

学习已有编译器的经典代码生成源程序

二.实验任务

阅读已有编译器的经典代码生成源程序，并测试代码生成器的输出

三.实验内容

选择一个编译器，如：TINY或PL/0，其它编译器也可（需自备源代码）。

阅读TM虚拟机的有关文档（请参考《编译原理及实践》第8.7节）。了解TM机的指令结构与寻址方式等相关内容。

阅读代码生成源程序，加上你自己的理解。尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。

测试代码生成器。请对生成的目标代码逐行加上注释，增强其可读性。

TINY语言：
测试用例一：sample.tny。
测试用例二：用TINY语言自编一个程序计算任意两个正整数的最大公约数与最大公倍数。

1.选择一个编译器

在这里，我仍然选择Tiny编译器，对于Tiny所有的代码，我们可以从实验一中获取，或者访问网址：https://github.com/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指令的文本文件，并有以下约定：

忽略空行。
以星号打头的行被认为是注释而忽略。
任何其他行必须包含整数指示位置后跟冒号再接正规指令。任何指令后的文字都被认为是注释而被忽略掉。

注意：T M模拟器没有其他特征了——特别是没有符号标号和宏能力。

TM模拟器命令：

3.阅读代码生成源程序，加上自己的理解

尤其要求对相关函数与重要变量的作用与功能进行稍微详细的描述。若能加上学习心得则更好。

(1) 程序清单

在本实验中，代码生成相关的文件有三个，下面我将会就这些文件的功能做一个快速列举。一些代码生成器需要知道的有关 TM的信息已封装在文件code.h 和code.c 中

文件名filename	相应功能
main.c	主函数，用于组织生成整个TINY的编译器，想要生成代码分析器，请设置标志位 `#define NO_CODE FALSE`
code.c	一些代码生成器需要知道的有关 T M的信息已封装在文件c o d e . h 和c o d e . c中
cgen.c	T I N Y代码生成器在文件c g e n . c中，其中提供给T I N Y编译器的唯一接口是C o d e G e n，其原型为 void CodeGen (void);
tm.c	TM模拟器的相关底层定义，T M由只读指令存储区、数据区和 8个通用寄存器构成。它们都使用非负整数地址且以 0开始。寄存器7为程序记数器，它也是唯一的专用寄存器。除此之外，还有操作指令集等等。

(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 FALSE

int 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;
  repeat
    fact := fact * x;
    x := x - 1
  until x = 0;
  write fact  { output factorial of x }
end

执行./tiny samples/sample1.tny 生成目标代码：

下面是目标代码sample.tm，我将会对生成的目标代码逐行加上注释，增强其可读性，由于篇幅限制，我截取了其中的一部分。

* 标准预处理
  0:     LD  6,0(0) 	从位置0加载maxaddress
  1:     ST  0,0(0) 	清除位置0
* 预处理结束
  2:     IN  0,0,0 		读入整型数据
  3:     ST  0,0(5) 	存储read进来的数据
  4:    LDC  0,0(0) 	加载const 0
  5:     ST  0,0(6) 	压入比较操作的做操作数op: push left
* -> Id
  6:     LD  0,0(5) 	加载 id = x 
* <- Id
  7:     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 jmp
 12:    LDC  0,1(0) 	true case
.........................................
* repeat: 循环操作 jump after body comes back here
 16:     LD  0,1(5) 	加载 id = x
 17:     ST  0,0(6) 	op：压如左操作数
 18:     LD  0,0(5) 	加载id = x
 19:     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 else
 40:    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 := cur
end;
repeat
    cur := x - (x / y)*y;
    x := y;
    y := cur
until y = 0;
write x;
write (S / x)

执行./tiny samples/Euclid.tny 生成目标代码：

下面是目标代码Euclid.tm，我将会对生成的目标代码逐行加上注释，增强其可读性，由于篇幅限制，我截取了其中的一部分。

* 标准预处理
  0:     LD  6,0(0) 	从位置0加载maxaddress
  1:     ST  0,0(0) 	清除位置0
* 预处理结束
  2:     IN  0,0,0 		read 读入整型数据 x
  3:     ST  0,0(5) 	read: 保存数据 x
  4:     IN  0,0,0 		read 读入整型数据 y
  5:     ST  0,1(5) 	read: 保存数据 y
MUL 乘法 操作：
  6:     LD  0,0(5) 	加载 id 值 x 
* <- 压入操作数 x
  7:     ST  0,0(6) 	op: push left
* -> Id
  8:     LD  0,1(5) 	加载 id = y
* <- 压入操作数 y
  9:     LD  1,0(6) 	加载操作数 y
 10:    MUL  0,1,0 		做乘法操作
* <- Op
 11:     ST  0,2(5) 	assign: 保存到2(5)位置
* 下面的 if 操作和 reapt操作在sample1中已经分析过了，我们跳过，重点看一看除法操作
* -> 除法
* -> Id
 31:     LD  0,0(5) 	load id 加载id变量
* <- Id
 32:     ST  0,-1(6) 	op: 加入左操作数
* -> Id
 33:     LD  0,1(5) 	load id 加载id变量
* <- Id
 34:     LD  1,-1(6) 	op: 加载id
 35:    DIV  0,1,0 		op / 执行除发法操作	
* <- Op
 36:     ST  0,-1(6) 	op: push left
* -> Id
 37:     LD  0,1(5) 	load id value

* <- Op
 64:    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中我新增了许多变量，现在我吧他们列举在下面：

函数 / 变量声明	作用
static char buffer[1000];	缓冲区
ofpFO	读取文件的偏移量
retFO	返回值的偏移量
initFO	初始偏移量
globalOffset	全局偏移量
localOffset	局部偏移量
numOfParams	当前帧中的参数数
isInFunc	显示当前节点是否在功能块中的标志。此标志用于计算函数声明的localOffset。
mainFuncLoc	mainFuncLoc是main函数的位置
cGen	内部递归代码生成器原型
getBlockOffset	函数getBlockOffset返回list所在块中临时变量的偏移量
genStmt	过程genStmt在语句节点生成代码
genExp	过程genExp在表达式节点生成代码
static void genDecl( TreeNode * tree)	过程genDecl在声明节点生成代码
static void genParam( TreeNode * tree)	过程genParam在声明参数节点生成代码
static void cGen( TreeNode * tree )	过程cGen通过树遍历递归地生成代码
void genMainCall()	代码生成器的主调用
void codeGen(TreeNode * syntaxTree, char * codefile)	生成代码树的代码遍历程序。第二个参数（codefile）是代码文件的文件名，用于将文件名打印为代码文件中的注释

下面我将对其中几个重要部分进行详细说明。

(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;
      else
        varOffset = -(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");
          else
            emitRO("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");
        else
          emitRO("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加载gp
  1:    LDA  6,0(5) 	复制 gp 到 mp
  2:     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类型值
* <- Id
 10:     ST  0,-4(6) 	op: 左操作数
* -> Const
 11:    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
* <- Id
 27:     ST  0,-6(6) 	call: 压入返回参数
* -> Op
* -> Id (u)
 28:    LDC  0,-2(0) 	加载id
 29:    ADD  0,6,0 		id计算返回地址
 30:     LD  0,0(0) 	加载变量
.....
 49:     ST  0,-7(6) 	call: 压入变量
 50:     ST  6,-4(6) 	call: 存储当前的mp
 51:    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当前函数栈
....省略一些常见基本操作，直接看到函数调用
* -> Call
 94:     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: 无条件跳转到main
 98:     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加载gp
  1:    LDA  6,0(5) 	复制 gp 到 mp
  2:     ST  0,0(0) 	清除 0
* 标准预处理结束
...跳过一下我们已经分析过的基础操作，看到while循环...
* while: jump to end belongs here
 26:    LDC  0,-2(0) 	id: 加载变量偏移量
 27:    ADD  0,6,0 		id: 计算地址
 28:    LDA  0,0(0) 	load id 加载id地址
* <- Id
 29:     ST  0,-4(6) 	assign: push 压入左操作数
* -> Const
 30:    LDC  0,2(0) 	load 加载常数
* <- Const
 31:     LD  1,-4(6) 	assign: load 加载左操作数
 32:     ST  0,0(1) 	assign: 保存变量
* <- assign
* <- compound
 33:    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;
}