编译原理：抽象语法树是怎么变成机器码的

编译器在经过词法分析、语法分析之后，就把源代码变成了抽象语法树（AST）。

接下来，编译器的任务就是把AST变成机器码。

AST，是一个表示代码逻辑的树形结构，它是不能直接顺序遍历的，而只能递归遍历。

递归遍历的逻辑更复杂，不适合用在机器码、汇编码、字节码上。

越是底层代码越贴近数字电路，而数字电路不适合直接处理复杂的逻辑。

递归也属于复杂的逻辑，

所以C语言的入门程序之一就是“汉诺塔”，而数学归纳法可以成为一种常用的证明方法。

AST的树形结构，肯定是不适合直接在CPU上运行的，而要先把它变成机器码。

AST是怎么变成机器码的？

1，语义分析，

语义分析的作用有3个：

1）类型检查，

2）常量表达式的计算，

3）函数重载，

如果不是OOP语言，语义分析时不需要考虑函数重载问题。

语义分析最主要的作用还是类型检查。

编译器报出来的很多错误或警告信息，都是类型检查时给出来的，例如：

A* p = malloc(sizeof(A));

在C++中就会报错：从void指针到A的指针没有加类型转换（type cast）。

AST

赋值运算符=两边的类型，是语义分析时首先要检查的（其他运算符也一样）。

如果类型不匹配，在强类型语言的编译器里就要给出错误提示。

另外，sizeof(A) 都是常量表达式，也要在语义分析时计算出来。

把常量表达式提前在编译时计算出来，可以提高运行时的速度。

如果是脚本语言的解释器的话，在语义分析之后，就可以直接在AST运行了：

给每个运算符节点定义一个处理函数，该调用哪个就调用哪个，就可以得出程序的结果；

if / while / for 等分支循环的关键字，也可以一样看做是运算符。

如果是编译器或虚拟机，还需要继续往下处理。

虚拟机也是运行机器码的，只是和CPU的机器码不一样：虚拟机的机器码一般叫字节码。

2，三地址码的生成，

三地址码，是编译器的后端常用的中间代码。

生成了三地址码之后，就把AST的树形结构变成了顺序结构了，跟汇编码、机器码、字节码一样了。

struct A { int x, y; };

A* p = malloc(sizeof(A));

生成的三地址码是这样的：

call ret; malloc, 8

assign p; ret

第一个词是三地址码的指令（opcode），分号前面的是目的操作数（dst operand），分号后面的是源操作数列表（src operands list），多个源操作数之间以逗号分隔。

按照源代码的执行顺序，把AST遍历一遍，就可以生成三地址码。

源代码里分为顺序语句、if else语句、while语句、for语句等等，每种语句类型生成的三地址码是不一样的。

if else语句的三地址码会有分支跳转：往函数的结尾方向跳转。

while语句、for语句的三地址码会有循环跳转：往函数的开头方向跳转。

for (i = 0; i < 10; i++) printf("%dn", i);

上述for循环的AST和三地址码

从图中可以看出来，三地址码跟汇编码的差异非常小！

汇编码，是机器码的人类阅读版[呲牙]

生成了三地址码之后，把它变成机器码还是很容易的（如果不考虑运行效率的话）。

编译器后端的各种优化，主要还是为了让生成的机器码运行更快，而不仅仅是为了让机器码运行正确。

编译器的后端优化是个无底洞，因为程序员对代码的理解总是比编译器更深刻。

毕竟程序员是个大活人，而编译器有赖于程序员给它升级版本。

3，正确运行相关的优化，

加载（load）和保存（save）指令的位置，都是跟机器码的正确运行相关的优化。

除非每条运算指令都把结果写到内存，否则加载和保存指令的位置必须正确。

加载指令的位置在基本块的开头，保存指令的位置在基本块的末尾。

基本块，指的是没有跳转指令的顺序语句块。

for (i = 0; i < 10; i++) printf("%dn", i);

还是以前面的for循环为例子：

assign i, 0

这就是第1个基本块，因为接下来就要比较 i < 10了，而且还可能从后面跳回来多次比较。

cmp i, 10

这是第2个基本块，接下来会根据i < 10的比较结果进行跳转。

call printf, "%dn", i

inc i

这两行是第3个基本块，它们之间也没有跳转，而再往后就要跳转回开头，再次检查条件表达式。

跳转的源位置和跳转的目的位置，都是一个新的基本块的开始位置：

因为它们（前面或后面）的代码的执行分支是可能变化的，所以要单独划到一个基本块里。

for循环的流程图

如果在某个基本块里修改了某个变量，就要在末尾把它保存到内存。

如果在某个基本块里要使用某个变量，就要在开头把它加载到寄存器。

如上图：

对 i 赋值 0 之后要把它保存到内存，见绿色的save i指令；

在比较i < 10之前要把它从内存加载到寄存器，见绿色的load i指令。

这样生成指令，就可以保证运行结果的正确。

但为了让它运行的更快，一般会把循环内的加载放到循环的开头，把循环内的保存放到循环的末尾。

当然，这么做的前提是：循环的出口和入口必须都是唯一的。

goto不受待见，从编译器的层面来看，就是goto会导致循环的出口和入口有多个。

4，变量之间的冲突，

互相冲突的变量不能使用相同的寄存器，这是寄存器分配的原则。

怎么判断变量之间互相冲突呢？

就是某个变量如果在后面还要用，那么它跟其他变量就是冲突的。

例如：

a = 1;

b = 2;

c = a + b;

那么a和b就是冲突的。

因为第3行代码都要用到它们两个，所以在第2行代码的时候：a占用的寄存器不能腾出来，b必须找其他寄存器用。

第3行代码之后，a和b都没用了，c可以跟a或b的任何一个使用相同的寄存器。

所以上面的代码翻译成汇编，可以这样：

mov eax, 1

mov ebx, 2

add eax, ebx

a和c都使用eax，b使用ebx。

但是a和b不能都使用eax，否则结果就是错的。

变量之间是否冲突，要从后往前看。

编译器里在检查变量的冲突时，都是从函数的末尾往开头反向遍历每一条代码，看看哪些变量之间是冲突的。

有兴趣的可以看看我写的scf编译器框架的代码，在文件scf_basic_block.c里。

5，寄存器的分配，

确定了变量之间的冲突情况之后，就可以给代码里的变量分配寄存器了。

例如：

a = 2;

b = 3;

c = 4;

d = a + b + c;

这个例子的abc三者之间都是冲突的，因为在第4行同时用到了它们3个。

画个变量的冲突图如下：

变量的冲突图

a, b, c之间是互相冲突的，每一对冲突的变量之间有一条连线，所以正好画成一个三角形。

在分配寄存器时，abc互相之间不能分配相同的寄存器。

也就是说，把寄存器的编号作为颜色的话，上图三角形的3个顶点不能着同样的颜色。

在变量的冲突图上，每一条边的两个端点必须着不同的颜色。

这就是用于寄存器分配的图的着色算法。

分配完寄存器之后就好办了，按照每种CPU的手册生成指令的机器码就可以了。

例如：

给a, b, c分别分配eax, ebx, ecd，

d与a共用eax，

那么汇编指令就是：

mov eax, 2

mov ebx, 3

mov ecx, 4

add eax, ebx

add eax ecx.

x64的机器码我实在记不住，但在汇编层面，我还是可以充当个人形编译器的[大笑]

有兴趣的可以看看我的scf编译器框架的源码，非常的清晰。

编译原理（龙书）确实没怎么细说后端是怎么写的，只是提了一下图的着色算法。

不过对于我来说，我只要知道有这么个软件，我就能把它写出来！

求个赞赏[捂脸]

虽然重阳一生不弱于人，但还是要靠九阴真经来破解古墓派的武功啊。