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

编译器在经过词法分析、语法分析之后，就把源代码变成了抽象语法树（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个基本块，它们之间也没有跳转，而再往后就要跳转回开头，再次检查条件表达式。