Golang 编译原理

预备知识

抽象语法树

抽象语法树（Abstract Syntax Tree、AST），是源代码语法的结构的一种抽象表示，它用树状的方式表示编程语言的语法结构

抽象语法树中的每一个节点都表示源代码中的一个元素，每一棵子树都表示一个语法元素，以表达式 2 * 3 + 7 为例，编译器的语法分析阶段会生成如下图所示的抽象语法树

静态单赋值

静态单赋值（Static Single Assignment、SSA）是中间代码的特性，如果中间代码具有静态单赋值的特性，那么每个变量就只会被赋值一次

SSA 的主要作用是对代码进行优化，所以它是编译器后端的一部分

如下代码

x := 1
x := 2
y := x

第一行的赋值语句 x := 1 不会起到任何作用

下面是具有 SSA 特性的中间代码，我们可以清晰地发现变量 y_1 和 x_1 是没有任何关系的，所以在机器码生成时就可以省去 x := 1 的赋值，通过减少需要执行的指令优化这段代码

x_1 := 1
x_2 := 2
y_1 := x_2

指令集

主流的指令集：x86、arm

• 复杂指令集计算机（CISC）

  通过增加指令的类型减少需要执行的指令数，代表x86

• 精简指令集计算机（RISC）

  使用更少的指令类型完成目标的计算任务，代表arm

早期的 CPU 为了减少机器语言指令的数量一般使用复杂指令集完成计算任务，这两者并没有绝对的优劣，它们只是在一些设计上的选择不同以达到不同的目的

词法和语法分析

每个 Go 源代码文件最终都会被解析成一个独立的抽象语法树

词法分析的作用就是解析源代码文件，它将文件中的字符串序列转换成 Token 序列，方便后面的处理和解析，我们一般会把执行词法分析的程序称为词法解析器（lexer）

早期的 Go 语言虽然使用 lex 这种工具来生成词法解析器，但是最后还是使用 Go 来实现词法分析器，用自己写的词法分析器来解析自己

语法分析的输入是词法分析器输出的 Token 序列，语法分析器会按照顺序解析 Token 序列，该过程会将词法分析生成的 Token 按照编程语言定义好的文法（Grammar）自下而上或者自上而下的规约，每一个 Go 的源代码文件最终会被归纳成一个 SourceFile 结构

分析方法

• 自顶向下

  可以被看作找到当前输入流最左推导的过程，对于任意一个输入流，根据当前的输入符号，确定一个生产规则，使用生产规则右侧的符号替代相应的非终结符向下推导

一个常见的 LL 文法：

1. S→aS1
2. S1→bS1
3. S1→ϵ

以上规则和输入流 abb

1. S （开始符号）
2. aS1（规则 1)
3. abS1（规则 2)
4. abbS1（规则 2)
5. abb（规则 3)

这种分析方法一定会从开始符号分析，通过下一个即将入栈的符号判断应该如何对当前堆栈中最右侧的非终结符（S 或 S1）进行展开，直到整个字符串中不存在任何的非终结符，整个解析过程才会结束

• 自底向上

语法分析器从输入流开始，每次都尝试重写最右侧的多个符号，这其实是说解析器会从最简单的符号进行推导，在解析的最后合并成开始符号

和上面有相同效果的LR(0) 文法：

1. S→S1
2. S1→S1b
3. S1→a

同样对输入流abb

1. a（入栈）
2. S1（规则 3）
3. S1b（入栈）
4. S1（规则 2）
5. S1b（入栈）
6. S1（规则 2）
7. S（规则 1）

Lookahead 向前查看

在不同生产规则发生冲突时，当前解析器需要通过预读一些 Token 判断当前应该用什么生产规则对输入流进行展开或者归约

Go 语言的解析器使用了 LALR(1) 的文法来解析词法分析过程中输出的 Token 序列，最右推导加向前查看构成了 Go 语言解析器的最基本原理

类型检查

• 静态类型检查

  静态类型检查是基于对源代码的分析来确定运行程序类型安全的过程3，如果我们的代码能够通过静态类型检查，那么当前程序在一定程度上可以满足类型安全的要求，它能够减少程序在运行时的类型检查，也可以被看作是一种代码优化的方式

• 动态类型检查

  动态类型检查是在运行时确定程序类型安全的过程，它需要编程语言在编译时为所有的对象加入类型标签等信息，运行时可以使用这些存储的类型信息来实现动态派发、向下转型、反射以及其他特性

Go 语言的编译器不仅使用静态类型检查来保证程序运行的类型安全，还会在编程期间引入类型信息，让工程师能够使用反射来判断参数和变量的类型

当拿到一组文件的抽象语法树之后，Go 语言的编译器会对语法树中定义和使用的类型进行检查，类型检查会按照以下的顺序分别验证和处理不同类型的节点：

• 常量、类型和函数名及类型；
• 变量的赋值和初始化；
• 函数和闭包的主体；
• 哈希键值对的类型；
• 导入函数体；
• 外部的声明；

保证节点不存在类型错误，所有的类型错误和不匹配都会在这一个阶段被暴露出来，其中包括：结构体对接口的实现

遍历抽象语法树中的节点，对每个节点的类型进行检验，找出其中存在的语法错误，在这个过程中也可能会对抽象语法树进行改写，这不仅能够去除一些不会被执行的代码、对代码进行优化以提高执行效率，而且也会修改 make、new 等关键字对应节点的操作类型。

make 和 new 这些内置函数其实并不会直接对应某些函数的实现，它们会在编译期间被转换成真正存在的其他函数

中间代码生成

中间代码的生成过程是从 AST 抽象语法树到 SSA 中间代码的转换过程，在这期间会对语法树中的关键字再进行改写，改写后的语法树会经过多轮处理转变成最后的 SSA 中间代码

将编程语言到机器码的过程拆成中间代码生成和机器码生成两个简单步骤可以简化该问题，中间代码是一种更接近机器语言的表示形式，对中间代码的优化和分析相比直接分析高级编程语言更容易。

配置初始化

会缓存可能用到的类型指针、初始化 SSA 配置和一些之后会调用的运行时函数
根据传入的 CPU 架构设置用于生成中间代码和机器码的函数，当前编译器使用的指针、寄存器大小、可用寄存器列表、掩码等编译选项

遍历和替换

替换抽象语法树中节点的一些元素，将一些关键字和内建函数转换成函数调用，例如： 将 panic、recover 函数，关键字 new 也会被转换成调用runtime下的函数。从关键字或内建函数到运行时函数的映射

SSA生成

机器码生成

机器码是在目标 CPU 架构上能够运行的二进制代码

• 复杂指令集（CISC）

指令数目多并且复杂，每条指令的字节长度并不相等，x86 就是常见的复杂指令集处理器，它的指令长度大小范围非常广，从 1 到 15 字节不等，对于长度不固定的指令，计算机必须额外对指令进行判断，这需要付出额外的性能损失

• 精简指令集（RISC）

对指令的数目和寻址方式做了精简，大大减少指令数量的同时更容易实现，指令集中的每一个指令都使用标准的字节长度、执行时间相比复杂指令集会少很多，处理器在处理指令时也可以流水执行，提高了对并行的支持。作为一种常见的精简指令集处理器，arm 使用 4 个字节作为指令的固定长度，省略了判断指令的性能损失，精简指令集其实就是利用了我们耳熟能详的 20/80 原则，用 20% 的基础指令和它们的组合来解决问题

• SSA降级

不同架构调用不同架构的封装来处理
重写的过程会将通用的 SSA 中间代码转换成目标架构特定的指令

• 汇编器

Go 语言的汇编器是基于 Plan 9 汇编器的输入类型设计的

转载自

https://draveness.me/golang/