编译原理目录
1、词法分析
2、语法分析（重点）
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化
五、代码生成
代码生成任务：抽象语法树 => 翻译1 => 中间表示1 => 翻译2 => 中间表示2 => ... => 翻译n => 中间表示n => 汇编
最简单的结构
抽象语法树 => 翻译（代码生成） => 汇编
6.1 代码生成的任务
负责把源程序翻译成“目标机器”上的代码
- 目标机器：可以是真实物理机器、可以是虚拟机。
两个重要任务：
- 给源程序的数据分配计算资源
- 给源程序的代码选择指令
6.1.1 给数据分配计算资源
源程序的数据：
- 全局变量、局部变量、动态分配
机器计算资源：
- 寄存器、数据区、代码区、栈区、堆区
根据程序的特点和编译器的设计目标，合理的为数据分配计算资源
- 例如：变量放在内存里还是寄存器里？
6.1.2 给代码选择合适的机器指令
源程序的代码：
- 表达式运算、语句、函数等
机器指令：
- 算术运算、比较、跳转、函数调用返回
用机器指令实现高层代码的语义
- 等价性
- 对机器指令集体系结构（ISA）的熟悉
6.1.3 路线图
为了理清代码生成涉及的重要问题和解决方案，将研究两种不同的ISA上的代码生成技术
- 栈计算机Stack
- 寄存器计算机Reg
6.2 栈式计算机
- 栈式计算机在历史上非常流行（上世纪70年代曾有很多栈式计算机）
- 但今天已经基本上已经退出了历史舞台（效率问题）
我们还要讨论栈式计算机的代码生成技术的原因是：
- 给栈式计算机生成代码是最容易的
- 仍然有许多栈式的虚拟机：
Pascal P code、Java virtual machine (JVM)、Postscript...
6.2.1 栈式计算机Stack的结构
- 内存：存放所有的变量
- 栈：进行运算的空间
- 执行引擎：指令的执行
6.2.2 栈计算机的指令集（ISA）
是Java字节码的一个子集！
指令的语义：
- push
push NUM:
top++;
stack[top] = NUM;- load x
load x:
top++;
stack[top] = x; // 从内存中加载到栈顶- store x
store x:
x = stack[top];
top--;- add
add:
temp = stack[top-1] + stack[top];
top -= 2;
push temp;- times
times:
temp = stack[top-1] * stack[top];
top -= 2;
push temp;- and
and:
temp = stack[top-1] && stack[top];
top -= 2;
push temp;6.2.3 变量的内存分配伪指令
- Stack机器只支持一种数据类型int，并且给变量x分配内存的伪指令是：
.int x - Stack机器在装载一个程序时，就会读取伪指令，并且给相关变量分配内存空间。
示例：
6.3 栈式计算机的代码生成
6.3.1 ++递归下降代码生成算法++ ：从C--到Stack
6.3.2 表达式的代码生成
// 不变式：表达式的值总在栈顶
Gen_E(E e)
switch (e)
case n: emit ("push n"); break;
case id: emit ("load id"); break;
case true: emit ("push 1"); break;
case false: emit ("push 0"); break;
case e1+e2: Gen_E (e1);
Gen_E (e2);
emit ("add");
break;
case e1&&e2: Gen_E (e1);
Gen_E (e2);
emit ("and");
break;6.3.3 语句的代码生成
// 不变式：栈的规模不变
Gen_S(S s)
switch (s)
case id=e: Gen_E(e);
emit("store id");
break;
case printi(e): Gen_E(e);
emit ("printi");
break;
case printb(e): Gen_E(e);
emit ("printb");
break;6.3.4 类型的代码生成
// 不变式：只生成.int类型
Gen_T(T t)
switch (t)
case int: emit (".int");
break;
case bool: emit (".int");
break;6.3.5 变量声明的代码生成
// 不变式：只生成.int类型
Gen_D(T id; D)
Gen_T (T);
emit (" id");
Gen_D (D);6.3.6 程序的代码生成
Gen_P(D S)
Gen_D (D);
Gen_S (S);6.4 寄存器计算机及其代码生成
寄存器计算机是目前最流行的机器体系结构之一
- 效率很高
- 机器体系结构规整
机器基于寄存器架构：
- 典型的有16、 32或更多个寄存器，所有操作都在寄存器中进行。
- 访存都通过
load/store进行，内存不能直接运算。
6.4.1 寄存器计算机Reg的结构
- 内存：存放溢出的变量
- 寄存器：进行运算的空间，假设有无限多个
- 执行引擎：指令的执行
6.4.2 寄存器计算机的指令集
注意：movn n, r 是把整数n的值赋给r，源操作数在左，目的操作数在右。后面同理
6.4.3 变量的寄存器分配伪指令
- Reg机器只支持一种数据类型int，并且给变量x分配寄存器的伪指令是：
.int x - 在代码生成的阶段，假设Reg机器上有无限多个寄存器。因此每个声明变量和临时变量都会占用一个（虚拟）寄存器。
- 把虚拟寄存器分配到物理寄存器的过程称为寄存器分配。
6.4.4 递归下降代码生成算法：从C--到Reg
6.4.5 表达式的代码生成
// 不变式：表达式的值在函数返回的寄存器中
R_t Gen_E(E e)
switch (e)
case n: r = fresh(); //拿到一个寄存器
emit ("movn n, r");
return r;
case id: r = fresh ();
emit ("mov id, r");
return r;
case true: r = fresh ();
emit ("movn 1, r");
return r;
case false: r = fresh ();
emit ("movn 0, r");
return r;
case e1+e2: r1 = Gen_E(e1);
r2 = Gen_E(e2);
r3 = fresh();
emit ("add r1, r2, r3");
return r3;
case e1&&e2: r1 = Gen_E(e1);
r2 = Gen_E(e2);
r3 = fresh();
emit ("and r1, r2, r3");
return r3; // 非短路6.4.6 语句的代码生成
Gen_S(S s)
switch (s)
case id=e: r = Gen_E(e);
emit("mov r, id");
break;
case printi(e): r = Gen_E(e);
emit ("printi r");
break;
case printb(e): r = Gen_E(e);
emit ("printb r");
break;6.4.7 类型的代码生成
// 不变式：只生成.int类型
Gen_T(T t)
switch (t)
case int: emit (".int");
break;
case bool: emit (".int");
break;6.4.8 变量声明的代码生成
// 不变式：只生成.int类型
Gen_D(T id; D)
Gen_T (T);
emit (" id");
Gen_D (D);6.4.9 程序的代码生成
Gen_P(D S)
Gen_D (D);
Gen_S (S);6.4.10 示例
- - - 结束 - - -