Golang – 编译器原理

编译器分为前端和后端。编译器前端的工作有：

• 词法分析
• 语法分析
• 类型检查
• 中间代码生成

编译器后端的工作有：

• 目标代码的生成和优化

Go 的编译器在逻辑上可以被分成四个阶段：

• 词法与语法分析(Parsing)
• 类型检查和 AST 转换(Type-checking and AST transformations)
• 通用 SSA 生成(Generic SSA)
• 机器代码生成(Generating machine code)

编译器的源码文件在：GOROOT/src/cmd/compile 目录下。 go-1-16\src\cmd\compile\main.go 编译的入口 mian 函数源码为：

Main 解析命令行参数中指定的标志和 Go 源文件，对解析的 Go 包进行类型检查，将函数编译为机器代码，最后将编译后的包定义写入磁盘。

词法分析的作用就是解析源代码文件，将文件中的字符串序列转换成 Token 序列，方便后面的处理和解析。执行词法分析的程序称为词法解析器（lexer）。也叫扫描器（scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。

这个 Token 序列，其实就是不包括空格、换行等字符的序列。词法分析器就是将源代码，根据一定的规则，转换解析成字符序列。而 lexer 词法解析器定义了这个规则，例如有如下规则：

这个规则的意思就是，package 关键字翻译成 Token 为 PACKAGE，以此类推，如果一个简单的 main 函数：

那么根据转换规则，lexer 词法解析器会将上面的源代码，转换成 Token 序列为：

生成这个 Token 后，语法分析器会对这个 Token 序列做进一步的转换。

词法分析器 Scanner 源码位置在：

入口文件：（src/cmd/compile/internal/syntax/scanner.go ）

token类型：（src/cmd/compile/internal/syntax/tokens.go ）

2. 语法分析

词法分析器生成 Token 后，语法分析过程就是将这个 Token 按照语言定义好的语法（Grammar）自下而上或者自上而下的进行规约，每一个 Go 的源代码文件最终会被归纳成一个 SourceFile 结构。

所谓的语法分析就是将 Token 转化为可识别的程序语法结构，而 AST 就是这个语法的抽象表示。每一个 AST 都对应着一个单独的 Go 语言文件，这个抽象语法树中包括当前文件属于的包名、定义的常量、结构体和函数等。构造这颗树有两种方法：

• 自上而下
  这种方式会首先构造根节点，然后就开始扫描 Token，遇到 String 或者其它类型就知道这是在进行类型申明，Func 就表示是函数申明。就这样一直扫描直到程序结束。
• 自下而上
  这种是与上一种方式相反的，它先构造子树，然后再组装成一颗完整的树。

抽象语法树（Abstract Syntax Tree、AST），是源代码语法的结构的一种抽象表示，它用树状的方式表示编程语言的语法结构。抽象语法树中的每一个节点都表示源代码中的一个元素，每一棵子树都表示一个语法元素。

作为编译器常用的数据结构，抽象语法树抹去了源代码中不重要的一些字符 – 空格、分号或者括号等等。编译器在执行完语法分析之后会输出一个抽象语法树，这个抽象语法树会辅助编译器进行语义分析，我们可以用它来确定语法正确的程序是否存在一些类型不匹配的问题。

go 语言进行语法分析使用的是自下而上的方式来构造 AST，下面我们就来看一下go语言通过 Token 构造的这颗树是什么样子。

1. 词法分析器

词法分析是将字符序列转换为Tokens（或称Token序列、单词序列）的过程。其工作原理是对输入的代码文本进行词法分析，将一个个字符以从左到右的顺序读入，根据构词规则识别单词，最终得到Token（单词）。Token是语言中的最小单位，它可以是变量、函数、运算符或数字。

例如“x*i+1”文本表达式，通过Lexer词法分析器处理后得到Token序列。Lexer词法分析器解析后的结果为：

1. 语法分析器

通过 Lexer 词法分析器得到 Token 序列以后，它将被传递给 Parser 语法解析器。解析器是编译器的一个阶段，它将 Token 序列转换为抽象语法树（AST，Abstract Syntax Tree）。抽象语法树也被称为语法树（Syntax Tree），是编程语言源码的抽象语法结构的树状表现形式，树上的每个节点都表示源码中的一种结构。

yuroyoro/goast-viewer   就是一个将 golang 源代码转成 AST 可视化的项目。

抽象语法树是源码的结构化表示。在抽象语法树中，我们能够看到程序结构，例如函数和常量声明。将上面 “x*i+1” 表达式的 Token 转成 AST 抽象语法树为：

首先，词法分析和语法分析用到的结构体有：

• noder : 表示每一个文件的语法树，转成一个 Node tree
• File : 表示每个文件生成的 Token 值。
• Node : 是具体的 Node Tree 中的每一个节点
• parser : 语法解析器
• scanner : 词法解析器

在 src/compile/internal/gc/noder.go 文件中，定义了 noder 结构体，该结构体中，每一个 noder 对象相当于 AST 语法树中的节点，构成了整个语法树。noder 结构体定义如下，最关键的字段就是：

• file : syntax.File 结构体就是保存了词法分析的结果。

也就是说，词法解析器的结果会附加到 noder 结构体中的 File 字段中，表示词法分析的结果 Token。下面是 syntax.File 结构体，syntax.File 结构体在 src\cmd\compile\internal\gc\noder.go 文件中，有几个地方需要注意：

• Pragma : 是词法分析的结果，其中，此法分析的函数主要是 ：type PragmaHandler func(pos Pos, blank bool, text string, current Pragma) Pragma
• PkgName : 就是编译的 package 的名称
• DeclList []Decl : 我的理解，DeclList 是需要编译的每一行代码的 Token 值。Decl 是一个继承了 Node 接口的接口。
• Lines : 表示一共有多少行代码需要编译
• node : 是一个 Node Tree 的节点，这个 node 结构体中只有在源代码中的位置属性，并且实现了 Node 接口。

gc.noder 和 syntax.File 结构体用于保存解析后的结果，接下来就是怎么解析成这个结果，有两个解析器，一个是词法解析器，一个是语法解析器，先来看语法解析器，因为在语法解析器的结构体中，包含了词法解析器。

parser 结构体位于 src\cmd\compile\internal\syntax\parser.go 文件中，该结构体定义了解析器需要用到的变量，关键属性有：

• pragh PragmaHandler : 该 Hanlder 函数主要用于语法的分析，主要作用有
  • 遇到关键字 package, import, const, func, type, var 等，会将语法保存在 File, ImportDecl, ConstDecl, FuncDecl, TypeDecl,  VarDecl node
  • 遇到 // 开头的代码行，直接跳过
  • 初始为 nil
• scanner : 表示词法解析器

语法解析器 parse 结构体中包含了词法解析器 scanner，scanner 结构体位于 src\cmd\compile\internal\syntax\scanner.go 文件中，scanner 主要的属性有

• source : 源码文件对象，source 结构体中保存了 io.Reader 等等属性
• tok token : 当前的 Token 值，在调用next() 方法之后有效，我的理解是，tok 表示当前行的 Token 值，调用 next() 方法后，解析下一行的 Token 值并存入。

在 src\cmd\compile\main.go 的主程序入口文件中，调用 gc.Main 函数，而 gc.Main 函数就是 go build 的主要构建过程。gc.Main 函数位于 src\cmd\compile\internal\gc\main.go 文件。

gc.Main 函数前面的主要内容是分析当前系统架构，根据不同的架构运行不同的参数，并且分析 go build 时用户传入的参数，根据不同的参数执行不同的功能。在 gc.Main 函数中，实现词法分析和语法分析的过程在调用 parseFiles 的函数时。

parseFiles 函数位于 src\cmd\compile\internal\gc\noder.go ，该函数的主要功能及解析过程为：

• 创建 所有文件的 noder 列表，每一个文件保存为一个 noder
• 遍历所有文件
  • 每一个文件对应生成一个 noder ，添加到 noder 列表
  • 开一个 Goroutine 来解析源文件，将解析的结果保存到 noder 结构体中的 File 结构中
  • 注意：解析的文件的过程在 syntax.Parse() 函数中。
• 遍历结束后，将该 Node 节点加入到 xtop tree 中，也就是 AST 抽象语法树
• 生成 Node Tree 树的过程在 p.node() 函数中，就是将 noder 结构体转换成 Node 节点类型，添加到 xtop tree 中，xtop 就是这颗语法树，供后面类型检查使用。

可以看到上面代码中，解析的过程调用了syntax.Parse() 函数，该函数位于 src\cmd\compile\internal\syntax\syntax.go 文件，该函数就是词法解析的过程。

词法解析器主要有两个主要的步骤：

• p.next() : 文件有可能是一些注释信息，如果当前 position 的字符是特殊字符，就使用对应的常量替代，如果不是特殊字符，就根据关键词生成 token。
• p.fileOrNil() : 根据 Token 中关键字符，例如 package，import 等，就将对应的 结构体添加到 DeclList 中。例如，是 import 关键字，添加的就 importDecl 结构体。

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

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

通过对整棵抽象语法树的遍历，在每个节点上都会对当前子树的类型进行验证，以保证节点不存在类型错误，所有的类型错误和不匹配都会在这一个阶段被暴露出来，其中包括：结构体对接口的实现。

通过Parser解析器得到抽象语法树之后，需要对抽象语法树中定义和使用的类型进行检查。对每一个抽象语法树节点进行遍历，在每个节点上对当前子树的类型进行验证，进而保证不会出现类型错误。抽象语法树一般有多种遍历方式，比如深度优先搜索（DFS）遍历和广度优先搜索（BFS）遍历等。

根据源码，可以发现类型检查一共有9个阶段:

• 检查常量、类型和函数的类型；
• 处理变量的赋值；
• 对函数的主体进行类型检查；
• 决定如何捕获变量；
• 检查内联函数的类型；
• 进行逃逸分析；
• 将闭包的主体转换成引用的捕获变量；
• 编译顶层函数；
• 检查外部依赖的声明；

类型检查，主要函数就是 typecheck1 。大部分的代码都是由一个巨型 switch/case 构成的，根据当前语句不同的类型，例如切片，数组，函数等，进一步做检查。