编译原理入门-编译的全过程

概述：

编译就是把源代码变成目标代码的过程

如果源代码在操作系统上运行：目标代码就是“汇编代码”。再通过汇编和链接的过程形成可执行文件，然后通过加载器加载到操作系统执行。 如果源代码在虚拟机(解释器)上运行：目标代码就是“解释器可以理解的中间形式的代码”，比如字节码(中间代码)IR、AST语法树。

词法分析(Lexical Analysis)

词法分析是将输入的字符串以单词符号的结果进行输出

程序里面的单词叫做Token，Token的类型包括：关键字、标识符、字面量、操作符等

词法分析就是把字符串转换成一个个Token的过程

语法分析(Syntactic Analysis)

每一个程序代码，实际上可以通过树这种结构表现出其语法规则。

语法分析阶段把Token串，转换成一个体现语法规则的、树状数据结构，即抽象语法树AST。

AST树反映了程序的语法结构。

语义分析

语义分析阶段的任务：理解语义，语句要做什么。

比如+号要执行加法、=号要执行赋值、for结构要去实现循环、if结构实现判断。

所以语义阶段要做的内容有：上下文分析（包括引用消解、类型分析与检查等）

引用消解：找到变量所在的作用域，一个变量作用范围属于全局还是局部。

类型识别：比如执行a+3，需要识别出变量a的类型，因为浮点数和整型执行不一样，要执行不同的运算方式。

类型检查：比如int b = a + 3，是否可以进行定义赋值。等号右边的表达式必须返回一个整型的数据、或则能够自动转换成整型的数据，才能够对类型为整型的变量b进行复制。

比如之前的一段C语言代码，经过语义分析后获得的信息（引用消解信息、类型信息），可以在AST上进行标注，形成下面的“带有标注的语法树”，让编译器更好的理解程序的语义。

也会将这些上下文信息存入“符号表”结构中，便于各阶段查询上下文信息。

符号表是有层次的结构：我们只需要逐级向上查找就能找到变量、函数等的信息(作用域、类型等)

接下来就可以 解释执行：实现一门解释型的语言

Tip:编译型语言需要生成目标代码，而解释性语言只需要解释器去执行语义就可以了。

实现AST的解释器：在语法分析后有了程序的抽象语法树，在语义分析后有了“带有标注的AST”和符号表后，就可以深度优先遍历AST，并且一边遍历一边执行结点的语义规则。整个遍历的过程就是执行代码的过程。

举一个解释执行的例子，比如执行下面的语义：

• 遇到语法树中的add “+”节点：把两个子节点的值进行相加，作为“+”节点的值。
• 遇到语法树中的变量节点(右值)：就取出变量的值。
• 遇到字面量比如数字2：返回这个字面量代表的数值2。

中间代码生成

在编译前端完成后(编译器已经理解了词法和语义)，编译器可以直接解释执行、或则直接生成目标代码。对于不同架构的CPU，还需要生成不同的汇编代码，如果对每一种汇编代码做优化就很繁琐了。所以我们需要增加一个环节：生成中间代码IR，统一优化后中间代码，再去将中间代码生成目标代码。

中间代码IR的两个用途：解释执行 、代码优化

解释执行：解释型语言，比如Python和Java，生成IR后就能直接执行了

优化代码：比如LLVM等工具；在生成代码后需要做大量的优化工作，而很多优化工作没必要使用汇编代码来做(因为不同CPU体系的汇编语言不同)，而可以基于IR用统一的算法来完成，降低编译器适配不同CPU的复杂性。

代码优化(Optimization)

为什么需要进行代码优化呢?

1. 源语言和目标语言有差异
2. 程序员写的代码不是最优的，编译器会帮助纠正

优化器分类

而采用中间代码来编写优化算法的好处，是可以把大部分的优化算法，写成与具体CPU架构无关的形式，从而大大降低编译器适配不同CPU的工作量。并且，如果采用像LLVM这样的工具，我们还可以让多种语言的前端生成相同的中间代码，这样就可以复用中端和后端的程序了。

目标代码生成

目标代码生成，也就是生成虚拟机执行的字节码，或则操作系统执行的汇编代码

代码生成的过程，其实很简单，就是将中间代码IR逐个翻译成想要的汇编的代码

那么目标代码生成阶段的任务就有：

选择合适指令，生成性能最高的代码。 优化寄存器的分配，让频繁访问的变量，比如循环语句中的变量放到寄存器中，寄存器比内存快 在不改变运行结果下，对指令做重排序优化，从而充分运用CPU内部的多个功能部件的并行能力

目标代码生成之后，整个编译过程就完成了

本文参考：

编译原理实战课