编译器的前端技术
- 词法分析是把程序分割成一个个 Token 的过程，可以通过构造有限自动机来实现。
- 语法分析是把程序的结构识别出来，并形成一棵便于由计算机处理的抽象语法树。可以用递归下降的算法来实现。
- 语义分析是消除语义模糊，生成一些属性信息，让计算机能够依据这些信息生成目标代码。
词法分析
手工打造词法分析器的过程，就是写出正则表达式，画出有限自动机的图形，然后根据图形直观地写出解析代码的过程。
语法分析
语法分析的结果是生成 AST。算法分为自顶向下和自底向上算法，其中，递归下降算法是一种常见的自顶向下算法。
首先把变量声明语句（int a = 45）的规则，用形式化的方法表达一下。它的左边是一个非终结符（Non-terminal），右边是它的产生式（Production Rule）。
在语法解析的过程中，左边会被右边替代。如果替代之后还有非终结符，那么继续这个替代过程，直到最后全部都是终结符（Terminal），也就是 Token。只有终结符才可以成为 AST 的叶子节点。这个过程，也叫做推导（Derivation）过程。
带有预测的自顶向下算法，它能减少回溯的次数。
上级文法嵌套下级文法，上级的算法调用下级的算法。表现在生成 AST 中，上级算法生成上级节点，下级算法生成下级节点。这就是“下降”的含义。
程序结构基本上是跟文法规则同构的。这就是递归下降算法的优点，非常直观。
解析算术表达式的时候，会遇到更复杂的情况，这时，正则文法不够用，我们必须用上下文无关文法来表达。
通过文法的嵌套，实现对运算优先级的支持。
正则文法是上下文无关文法的一个子集。它们的区别是上下文无关文法允许递归调用，而正则文法不允许。
左递归是递归下降算法无法处理的，这是递归下降算法最大的问题。
对于左结合的运算符，递归项要放在左边；而右结合的运算符，递归项放在右边。
针对优先级、结合性和左递归这三个问题做了更系统的研究：
- 优先级 是通过在语法推导中的层次来决定的，优先级越低的，越先尝试推导。
- 结合性 是跟左递归还是右递归有关的，左递归导致左结合，右递归导致右结合。
- 左递归 可以通过改写语法规则来避免，而改写后的语法又可以表达成简洁的 EBNF 格式，从而启发我们用循环代替右递归。
理解递归下降算法中的回溯：尝试一个规则不成功之后，恢复到原样，再去尝试另外的规则，这个现象就叫做“回溯”。
语义分析
语义分析的相关知识：
- 语义分析的本质是对上下文相关情况的处理，能做词法分析和语法分析所做不到的事情。
- 了解引用消解，左值和右值的场景，可以增加对语义分析的直观理解。
- 掌握属性计算和属性文法，可以使我们用更加形式化、更清晰的算法来完成语义分析的任务。
4.1 类型系统
类型系统最大的好处，就是可以通过类型检查降低计算出错的概率。所以，现代计算机语言都会精心设计一个类型系统，而不是像汇编语言那样完全不区分类型。
根据类型检查是在编译期还是在运行期进行的，我们可以把计算机语言分为两类：
- 静态类型语言（全部或者几乎全部的类型检查是在编译期进行的）
- 动态类型语言（类型的检查是在运行期进行的）
再延伸一下，跟静态类型和动态类型概念相关联的，还有强类型和弱类型。强类型语言中，变量的类型一旦声明就不能改变，弱类型语言中，变量类型在运行期时可以改变。二者的本质区别是，强类型语言不允许违法操作，因为能够被检查出来，弱类型语言则从机制上就无法禁止违法操作，所以是不安全的。
下面表达式在不同的情况下会有不同的运行结果：
a = b + 10; - 如果 b 是一个浮点型，b+10 的结果也是浮点型。如果 b 是字符串型的，有些语言也是允许执行 + 号运算的，实际的结果是字符串的连接。这个分析过程，就是类型推导（Type Inference）。
- 当右边的值计算完，赋值给 a 的时候，要检查左右两边的类型是否匹配。这个过程，就是类型检查（Type Checking）。
- 如果 a 的类型是浮点型，而右边传过来的是整型，那么一般就要进行缺省的类型转换（Type Conversion）。
4.2 引用消解
语义分析的本质，就是针对上下文相关的情况做处理。
当使用变量 a 时，我们需要知道它是全局变量 a，还是 fun() 函数中的本地变量 a。因为不同作用域里可能有相同名称的变量，所以必须找到正确的那个。这个过程，可以叫引用消解。
做引用消解可能会产生几个结果：
- 解析出了准确的引用关系。
- 重复定义（在声明新的符号的时候，发现这个符号已经被定义过了）。
- 引用失败（找不到某个符号的定义）。
- 如果两个不同的命名空间中都有相同名称的符号，编程者需要明确指定。
4.3 左值与右值
左值（L-value）最早是在 C 语言中提出的，通常出现在表达式的左边，如赋值语句的左边。左值取的是变量的地址（或者说变量的引用），获得地址以后，我们就可以把新值写进去了。
与左值相对应的就是右值（R-value），右值就是我们通常所说的值，不是地址。
4.4 属性文法与属性计算
在语义分析阶段我们要了解的是属性文法（Attribute Grammar），属性计算需要用到属性文法。
比如，针对求左值场景中的 primary 节点，它需要计算的属性包括：
- 它的变量定义是哪个（这就引用到定义该变量的 Symbol）。
- 它的类型是什么?
- 它的作用域是什么？
- 这个节点求值时，是否该返回左值？能否正确地返回一个左值？
- 它的值是什么？
从属性计算的角度看，对表达式求值，或运行脚本，只是去计算 AST 节点的 Value 属性，Value 这个属性能够计算，其他属性当然也能计算。
属性计算的特点：它会基于语法规则，增加一些与语义处理有关的规则。
所以，我们也把这种语义规则的定义叫做语法制导的定义（Syntax directed definition，SDD）。如果变成计算动作，就叫做语法制导的翻译（Syntax directed translation，SDT）。
属性计算，可以伴随着语法分析的过程一起进行，也可以在做完语法分析以后再进行。这两个阶段不一定完全切分开。甚至，我们有时候会在语法分析的时候做一些属性计算，然后把计算结果反馈回语法分析的逻辑，帮助语法分析更好地执行（这是在工程实践中会运用到的一个技巧）。
我们没必要在语法分析阶段把属性全都计算出来，等到语法分析完毕后，再对 AST 遍历一下就好了。这时所有节点都有了，计算属性也就不是难事了。
4.5 语义分析过程
第 1 遍：类型和作用域解析。
把自定义类、函数和和作用域的树都分析出来。这么做的好处是，你可以使用在前，声明在后。比如你声明一个 Mammal 对象，而 Mammal 类的定义是在后面才出现的；在定义一个类的时候，对于类的成员也会出现使用在声明之前的情况，把类型解析先扫描一遍，就能方便地支持这个特性。
在写属性计算的算法时，计算的顺序可能是个最重要的问题。因为某属性的计算可能要依赖别的节点的属性先计算完。我们讨论的 S 属性、I 属性和 L 属性，都是在考虑计算顺序。像使用在前，声明在后这种情况，就更要特殊处理了。
第 2 遍：类型的消解。
把所有出现引用到类型的地方，都消解掉，比如变量声明、函数参数声明、类的继承等等。做完消解以后，我们针对 `Mammal m;` 这样语句，就明确的知道了 m 的类型。这实际上是对 I 属性的类型的计算。
第 3 遍：引用的消解和 S 属性的类型的推导。
这个时候，我们对所有的变量、函数调用，都会跟它的定义关联起来，并且完成了所有的类型计算。
第 4 遍：做类型检查。
比如当赋值语句左右两边的类型不兼容的时候，就可以报错。
第 5 遍：做一些语义合法性的检查。
比如 break 只能出现在循环语句中，如果某个函数声明了返回值，就一定要有 return 语句，等等。
4.6 继承和多态
- 从类型的角度，面向对象的继承和多态是一种叫做子类型的现象，子类型能够放宽对类型的检查，从而支持多态。
- 在编译期，无法准确地完成对象方法和属性的消解，因为无法确切知道对象的子类型。
- 在运行期，我们能够获得对象的确切的子类型信息，从而绑定正确的方法和属性，实现继承和多态。另一个需要注意的运行期的特征，是对象的逐级初始化过程。
运行时机制
程序主要跟 CPU、内存，以及操作系统打交道，所以需要了解的重点如下：
- CPU 上运行程序的指令，运行过程中要用到寄存器、高速缓存来提高指令和数据的存取效率。
- 内存可以划分成不同的区域保存代码、静态数据，并用栈和堆来存放运行时产生的动态数据。
- 操作系统会把物理的内存映射成进程的寻址空间，同一份代码会被映射进多个进程的内存空间，操作系统的公共库也会被映射进进程的内存空间，操作系统还会自动维护栈。
程序在运行时顺序执行代码，可以根据跳转指令来跳转；栈被划分成栈桢，栈桢的设计有一定的自由度，但通常也要遵守一些约定；栈桢的大小和结构在编译时就能决定；在运行时，栈桢作为活动记录，不停地被动态创建和释放。
生成汇编语言
对于静态编译型语言，比如 C 语言和 Go 语言，编译器后端的任务就是生成汇编代码，然后再由汇编器生成机器码，生成的文件叫目标文件，最后再使用链接器就能生成可执行文件或库文件了。
- 汇编语言是由指令、标签、伪指令和注释构成的。其中主要内容都是指令。指令包含一个该指令的助记符和操作数。操作数可以使用直接数、寄存器，以及用两种方式访问内存地址。
- 汇编指令中会用到一些通用寄存器。这些寄存器除了用于计算以外，还可以根据调用约定帮助传递参数和返回值。使用寄存器时，要区分由调用者还是被调用者负责保护寄存器中原来的内容。
从 AST 到汇编代码、汇编代码到可执行文件的完整过程中抓几个关键点：
- 首先，从 AST 生成汇编代码，可以通过比较机械的翻译来完成，我们举了加法运算的例子。阅读示例程序，你也可以看看函数调用、参数传递等等的实现过程。总体来说，这个过程并不难。
- 第二，这种机械地翻译生成的代码，一定是不够优化的。我们已经看到了加法运算不够优化的情况，所以一定要增加一个优化的过程。
- 第三，在生成汇编的过程中，最需要注意的就是要遵守调用约定。这就需要了解调用约定的很多细节。只要遵守调用约定，不同语言生成的二进制目标文件也可以链接在一起，形成最后的可执行文件。
中间代码
在后端部分所讲的 IR，目的是方便执行各种优化算法，并有利于生成汇编。这种 IR，可以看做是一种高层次的汇编语言，主要体现在：
- 它可以使用寄存器，但寄存器的数量没有限制；
- 控制结构也跟汇编语言比较像，比如有跳转语句，分成多个程序块，用标签来标识程序块等；
- 使用相当于汇编指令的操作码。这些操作码可以一对一地翻译成汇编代码，但有时一个操作码会对应多个汇编指令。
7.1 三地址代码（TAC）
三地址代码（Three Address Code，TAC）一种常见的 IR 的格式，它的优点是很简洁，所以适合用来讨论算法：
x := y op z // 二元操作
x := op y // 一元操作 每条三地址代码最多有三个地址，其中两个是源地址（比如第一行代码的 y 和 z），一个是目的地址（也就是 x），每条代码最多有一个操作（op）。
另外几种 IR 的格式：
- 首先是四元式。它是与三地址代码等价的另一种表达方式，格式是：（OP，arg1，arg2，result）所以，“a := b + c” 就等价于（+，b，c，a）。
- 另一种常用的格式是逆波兰表达式。它把操作符放到后面，所以也叫做后缀表达式。“b + c”对应的逆波兰表达式是“b c +”；而“a = b + c”对应的逆波兰表达式是“a b c + =”。
三地址代码主要是学习算法的工具，或者用于实现比较简单的后端，要实现工业级的后端，充分发挥硬件的性能，还要学习 LLVM 的 IR。
7.2 LLVM汇编码
LLVM 有很好的模块化设计，支持即时编译（JIT）和提前编译（AOT），支持全过程的优化，并且具备友好的授权，值得我们好好掌握。
LLVM 汇编码（LLVM Assembly），是 LLVM 的 IR。有的时候，我们就简单地称呼它为 LLVM 语言，因此我们可以把用 LLVM 汇编码书写的一个程序文件叫做 LLVM 程序。
首先，LLVM 汇编码是采用静态单赋值代码形式的。
在三地址代码上再加一些限制，就能得到另一种重要的代码，即静态单赋值代码（Static Single Assignment, SSA），在静态单赋值代码中，一个变量只能被赋值一次。
SSA 的形式，体现了精确的“使用 - 定义”关系。
其次，LLVM IR 比起三地址代码有更多的细节信息。比如整型变量的字长、内存对齐方式等等，所以使用 LLVM IR 能够更准确地翻译成汇编码。
LLVM 的 IR 有两种格式：
- 文本格式，文件名一般以 “.ll” 结尾
- 字节码（bitcode）格式，文件名以 “.bc” 结尾
使用 LLVM 从源代码到生成可执行文件有两条可能的路径：
- 第一条路径，是把每个源文件分别编译成字节码文件，然后再编译成目标文件，最后链接成可执行文件。
- 第二条路径，是先把编译好的字节码文件链接在一起，形成一个更大的字节码文件，然后对这个字节码文件进行进一步的优化，之后再生成目标文件和可执行文件。
第二条路径比第一条路径多了一个优化的步骤，第一条路径只对每个模块做了优化，没有做整体的优化。所以，如有可能，尽量采用第二条路径，这样能够生成更加优化的代码。
总结一下 LLVM 的命令行工具包括：
- clang 前端
- llvm-as（把文本格式转换成字节码格式）
- llc（把字节码编译成目标平台的汇编代码）
- opt（代码优化）
- llvm-dis（将字节码再反编译回 ll 文件）
- llvm-link（链接）
- 还可以看它们的 help 信息
从生成 IR 到编译执行的完整过程的重点如下：
- LLVM 用一套对象模型在内存中表示 IR，包括模块、函数、基本块和指令，你可以通过 API 来生成这些对象。这些对象一旦生成，就可以编译和执行。
- 对于 if 语句和循环语句，需要生成多个基本块，并通过跳转指令形成正确的控制流图（CFG）。当存在多个前序节点可能改变某个变量的值的时候，使用 phi 指令来确定正确的值。
- 存储在内存中的本地变量，可以多次赋值。
- LLVM 能够把外部函数和 IR 模型中的函数等价对待。
代码优化
代码优化的关键点：
- 代码优化分为本地优化、全局优化和过程间优化三个范围。有些优化对于这三个范围都是适用的，但也有一些优化算法是全局优化和过程间优化专有的。
- 可用表达式分析和活跃性分析是本地优化时的两个关键算法。这些算法都是由扫描方向、值、转换函数和初始值这四个要素构成的。
- LLVM 用 pass 来做优化，可以通过命令行或程序来使用这些 Pass，也可以编写自己的 Pass。
优化过程：
- 我们首先做一个正向扫描，进行可用表达式分析，建立可用表达式的集合，然后参照这个集合替换公共子表达式，以及做拷贝传播。
- 接着，我们做一个反向扫描，进行活跃性分析，建立活变量的集合，识别出死变量，并依据它删除给死变量赋值的代码。
- 上述优化可能需要做不止一遍，才能得到最后的结果。
在 LLVM 中，做优化算法很方便，因为它采用的是 SSA 格式。具体来说，LLVM 中定义了 Value 和 User 两个接口，它们体现了 LLVM IR 最强大的特性，即静态单赋值中的“定义 - 使用”链，这种“定义 - 使用”关系会被用到优化算法中。
- 在 User 中，可以访问所有它用到的 Value，比如一个加法指令（%c = add nsw i32 %a, %b）用到了 a 和 b 这两个变量。
- 而在 Value 中，可以访问所有使用这个值的 User，比如给 c 赋值的这条指令。
- 所以，你可以遍历一个 Value 的所有 User，把它替换成另一个 Value，这就是拷贝传播。
全局优化中的算法，不会像在本地优化中一样，只针对一个基本块。而是更复杂一些，因为要覆盖多个基本块。这些基本块构成了一个 CFG，代码在运行时有多种可能的执行路径，这会造成多路径下，值的计算问题，比如活跃变量集合的计算。
还有些优化只能在全局优化中做，在本地优化中做不了，比如：
- 代码移动（code motion）能够将代码从一个基本块挪到另一个基本块，比如从循环内部挪到循环外部，来减少不必要的计算。
- 部分冗余删除（Partial Redundancy Elimination），它能把一个基本块都删掉。
总之，全局优化比本地优化能做的工作更多，分析算法也更复杂，因为 CFG 中可能存在多条执行路径。这种基于 CFG 做优化分析的方法框架，就叫做数据流分析。
基于全局优化分析的任务的几个要点：
- 全局分析比本地分析多处理的部分就是 CFG，因为有了多条执行分支，所以要计算分支相遇时的值，当 CFG 存在环路的时候，要用不动点法来计算出所有的 V 值。
- 数据流分析框架包含方向（D）、值（V）、转换函数（F）、初始值（I）和交运算（Λ）5 个元素，只要分析清楚这 5 个元素，就可以按照固定的套路来编写分析程序。
- 对于半格理论，关键是要知道如何比较偏序集中元素的大小，理解了这个核心概念，那么求最大下界、最小上界这些也就没有问题了。
目标代码的生成和优化
代码生成部分需要考虑的问题主要有三点：
- 指令的选择。同样一个功能，可以用不同的指令或指令序列来完成，而我们需要选择比较优化的方案。
- 寄存器分配。每款 CPU 的寄存器都是有限的，我们要有效地利用它。
- 指令重排序。计算执行的次序会影响所生成的代码的效率。在不影响运行结果的情况下，我们要通过代码重排序获得更高的效率。
指令选择、寄存器分配、指令重排序这三个领域的算法，都是“NP - 完全”的，所以寻找优化的算法，是这个领域最富有挑战的任务。
- 相同的 IR 可以由不同的机器指令序列来实现。要理解瓦片为什么长那个样子，并且在大脑里建立用瓦片覆盖一棵 AST 的直观印象，最好具备多种覆盖方式，从而把这个问题由抽象变得具象。
- 寄存器分配是编译器必须要做的一项工作，它把可以使用无限多寄存器的 IR，变成了满足物理寄存器数量的 IR，超出的要溢出到内存中保管。染色算法是其中一个可行的算法。
- 要理解令重排序这个主题，首先要知道 CPU 内部是分成多个功能部件的，要知道一条指令的执行过程中，指令获取、解码、执行、访问数据都是如何发生的，这样就可以理解指令级并行的原理；其次，从算法角度，要知道 List Scheduling 的步骤，掌握基于最大时延的优先级计算策略。有了这个基础之后，就可以进一步地研究其他算法。