【翻译】Go 编译器理解: 新增一个关键字语句-Part 1
原文发表在 thegreenplace，推荐观看原文Go compiler internals: adding a new statement to Go - Part 1 - Eli Bendersky’s website (thegreenplace.net)
这是该系列第一篇文章，文章将简单介绍Go 的编译器。编译器知识非常庞大，一般需要一本书才能详细描述。因此本文章只是一个快速的叫深入的介绍。我计划未来写更多的关于编译器的文章。
在本系列中，我们将向Go编译器中添加一个新的语言关键字，建立一个可修改的编译器。（译者注：Go实现了自举，因此Go编译器也其实是一个Go应用，只要理解其中的原理，添加一个新的关键字特性也并非难事）
新增一个关键字语句(statement)
大多数语言有一个while语言，在Go中并未直接有该语句，但是可以通过for实现：
for <some-condition> {
<loop body>
}
增加一个while语句并不重要，因为for能实现该功能。因此我们实现一个更有挑战的功能，添加until语句，until和while功能大体一致，只是当条件为否时才执行循环。下述一个例子：
i := 4
// i == 0 为否时才循环，等于 i != 0
until i == 0 {
i--
fmt.Println("Hello, until!")
}
和下述语句一致:
i := 4
// i != 0 为 true 时进行循环
for i != 0 {
i--
fmt.Println("Hello, until!")
}
同时，我们能在循环声明的时候使用一个初始化语句，如下例：
until i := 4; i == 0 {
i--
fmt.Println("Hello, until!")
}
声明 - 这仅仅是一个供学习的小玩具，我不认为增加until对Go是一个好的注意。因为Go的极简机制是一个绝对正确的设计。
Go编译器的总体架构
Go编译器（Go compiler (gc)）是一个经典的编译器架构，如果你了解过其他编译器你会立刻感觉熟悉。架构如下图：
Go编译器的实现在Go源码的src/cmd/compile/internal目录中；后序本文中提到的代码路径都是该目录下的相对路径。整个编译器是由Go实现，因此阅读起来很容易。这篇文章我们将一个一个解释这些步骤，以及增加一个until关键字需要的编码。
查看src/cmd/compile下的 README 文件可以简单的了解这些编译步骤。这个文件是这篇文章的一个好的补充。
注：scan ->Parse->AST，这三步实际就是一个字符串处理程序，将一个Go源文件转换为树的结构。
Scan
扫描器（scanner ）（也称为lexer）将源代码解析成独立的实体（Token）。例如，for将解析成_For，···将解析成_DotDotDot，·将成为_Dot，等等。
scanner实现在 syntax包中。因此我们需要在这里新增一个关键字until，syntax/tokens.go文件有一个编译器中需要的所有tokens列表。因此我们新增加一个until：
_Fallthrough // fallthrough
_For // for
_Until // until 新增的
_Func // func
token 产量右边的注释是重要的，因为它用于标识文本中的 token。syntax/tokens.go是被用来生成syntax/token_string.go的，该代码在 Token 列表的上方有如下一行：：
//go:generate stringer -type token -linecomment
go generate 能手动运行然后输出文件 (syntax/token_string.go) 。为了重新生成它，我从syntax目录运行了以下命令：
GOROOT=<src checkout> go generate tokens.go
当我们修改编译器，重新生成 (syntax/token_string.go) 时， “ GOROOT” 设置从Go 1.12起是必不可少的，并且必须指向源代码的跟目录。
运行代码生成器并验证syntax / token_string.go现在具有until Token后，我尝试重建编译器，但遇到了 panic：
panic: imperfect hash
panic发生在 syntax/scanner.go文件的下述代码中:
// 这是一个关键字的hash函数，假定关键字长度至少为2
// hash is a perfect hash function for keywords.
// It assumes that s has at least length 2.
func hash(s []byte) uint {
return (uint(s[0])<<4 ^ uint(s[1]) + uint(len(s))) & uint(len(keywordMap)-1)
}
var keywordMap [1 << 6]token // size 必须时2的次方数 size must be power of two
func init() {
// populate keywordMap
// 构建 keywordMap
for tok := _Break; tok <= _Var; tok++ {
h := hash([]byte(tok.String()))
if keywordMap[h] != 0 {
panic("imperfect hash")
}
keywordMap[h] = tok
}
}
编译器尝试构建一个“完美的”哈希表，以从hash 查找到关键字字符串(Token)。 “完美”表示它不希望发生冲突，而只是一个线性数组，其中每个关键字都映射到一个索引（哈希可能发生冲突）。而我们添加的until关键字刚好发生了冲突。因为该哈希函数是一个针对该问题特定的函数（例如，它仅查看关键字字符串的前两个字符的内容）。并且去调试 until为何会产生冲突的原因并不容易。为了解决此问题，我将查找表的大小更改为“ [1 << 7] token”，从而将查找数组的大小从64更改为128。这为哈希函数提供了更多的空间来分配其键，冲突消失了。
Parse
Go有一个标准的递归下降解析器 (parser)，它转换 scanner 扫描的 Token 流 到一个正确的语法树。我们将在 syntax/nodes.go中增加一个新的until 节点类型 :
UntilStmt struct {
Init SimpleStmt // 初始化
Cond Expr //条件表达式
Body *BlockStmt // 循环体
stmt // 主要是接口信息 Pos() 表示在源代码中的位置
}
for 循环的节点类型定义ForStmt，我们仿照定义了UntilStmt。我们的新until和for是及其相似的，因此我们的until语句有几个可选的子语句
until <init>; <cond> {
<body>
}
<init> 和<cond> 是可选的。UntilStmt.stmt是嵌入字段，被用于语法树中所有的 statements （区分一下statements 和 expression）语句，其中包含了该语句的位置信息。
解析代码是在syntax/parser.go中完成的。parser.stmtOrNil方法解析当前位置的一个语句。
它查看当前 Token 并决定要解析的语句。这是一个包含我们添加代码的摘录：
switch p.tok {
case _Lbrace:
return p.blockStmt("")
// ...
case _For:
return p.forStmt()
case _Until: // 如果都是 _Until
return p.untilStmt() // 进行解析
}
untilStmt如下:
func (p *parser) untilStmt() Stmt {
if trace {
defer p.trace("untilStmt")()
}
s := new(UntilStmt)
s.pos = p.pos()
s.Init, s.Cond, _ = p.header(_Until) // 只使用前两个
s.Body = p.blockStmt("until clause")
return s
}
parser.header方法被使用来解析if 和 for 语句的头部（也就是Init和Cond），这和 until的头部是一样的，因此我们直接重用该方法。一般的形式下，它支持三个部分（以分号分隔）。在for语句中，第三部分可用于“ post”语句，但是我们不会在until中支持它，因此我们只使用前两部分。注意，header方法参数接受源 Token （判断是解析if还是for），以便能够区分所服务的语句类型。例如，它将拒绝if的post语句。我们也应该在header方法 的实现中添加当为 until时拒绝一个post语句，但是现在我们并没有实现这部分。
这是解析器中需要做的所有更改。由于until在结构上与现有语句非常相似，因此我们可以重用许多功能。而不必添加太多代码。
在使用编译器解析下述代码解析成语法树untilStmt节点后， 使用syntax.Fdump可打印出untilStmt的信息。
i = 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
我们将得到until语句对应的untilStmt结构
84 . . . . . 3: *syntax.UntilStmt {
85 . . . . . . Init: nil
86 . . . . . . Cond: *syntax.Operation {
87 . . . . . . . Op: ==
88 . . . . . . . X: i @ ./useuntil.go:13:8
89 . . . . . . . Y: *syntax.BasicLit {
90 . . . . . . . . Value: "0"
91 . . . . . . . . Kind: 0
92 . . . . . . . }
93 . . . . . . }
94 . . . . . . Body: *syntax.BlockStmt {
95 . . . . . . . List: []syntax.Stmt (2 entries) {
96 . . . . . . . . 0: *syntax.AssignStmt {
97 . . . . . . . . . Op: -
98 . . . . . . . . . Lhs: i @ ./useuntil.go:14:3
99 . . . . . . . . . Rhs: *(Node @ 52)
100 . . . . . . . . }
101 . . . . . . . . 1: *syntax.ExprStmt {
102 . . . . . . . . . X: *syntax.CallExpr {
103 . . . . . . . . . . Fun: *syntax.SelectorExpr {
104 . . . . . . . . . . . X: fmt @ ./useuntil.go:15:3
105 . . . . . . . . . . . Sel: Println @ ./useuntil.go:15:7
106 . . . . . . . . . . }
107 . . . . . . . . . . ArgList: []syntax.Expr (1 entries) {
108 . . . . . . . . . . . 0: *syntax.BasicLit {
109 . . . . . . . . . . . . Value: "\"Hello, until!\""
110 . . . . . . . . . . . . Kind: 4
111 . . . . . . . . . . . }
112 . . . . . . . . . . }
113 . . . . . . . . . . HasDots: false
114 . . . . . . . . . }
115 . . . . . . . . }
116 . . . . . . . }
117 . . . . . . . Rbrace: syntax.Pos {}
118 . . . . . . }
119 . . . . . }
构建AST
现在，我们得到了具有源代码的语法树表示形式，编译器据此将构建“抽象语法树”。我过去曾经写过抽象与具体语法树-如果你不熟悉抽象语法树和具体语法树，可参考这篇文章。因此现在Go代码编译过程中，存在两颗语法树，但是，未来可能会更改。 因为Go编译器最初是用C编写的，后来实现了自举，采用Go编写。所以它的某些部分是较旧的C时代的遗迹，而某些部分则是较新的Go。将来的重构可能只剩下一种语法树，但是现在（Go 1.12）是构建两颗语法树的结果。
AST代码位于gc包中，并且节点类型在gc/syntax.go中定义（不要与定义真实语法树的syntax包混淆！上述Parse中的结构都是真实语法树的部分）
Go AST的结构与CST不同。并非每个节点类型都有其专用的结构类型，所有AST节点都使用syntax.Node类型，这是一种“区分联合”类型，其中包含许多不同类型的字段。但是，大多数节点类型中的某些字段是通用的：
// A Node is a single node in the syntax tree.
// Actually the syntax tree is a syntax DAG, because there is only one
// node with Op=ONAME for a given instance of a variable x.
// The same is true for Op=OTYPE and Op=OLITERAL. See Node.mayBeShared.
type Node struct {
// Tree structure.
// Generic recursive walks should follow these fields.
Left *Node
Right *Node
Ninit Nodes
Nbody Nodes
List Nodes
Rlist Nodes
// ...
我们首先添加一个新的常量来标识一个until节点：
// statements
// ...
OFALL // fallthrough
OFOR // for Ninit; Left; Right { Nbody }
OUNTIL // until Ninit; Left { Nbody }
然后我们在gc/syntax.go上再次运行go generate，以生成新节点类型的字符串表示形式：
// from the gc directory
GOROOT=<src checkout> go generate syntax.go
更新后gc/op_string.go文件将包含OUNTIL。现在我们需要为的OUNTIL节点类型编写 CST-> AST转换代码。
转换在gc/noder.go中完成。该文件中的stmtFall方法中包含不同类型的switch分支， 我们在现有的for语句解析之后添加UntilStmt解析分支：
case *syntax.ForStmt:
return p.forStmt(stmt)
case *syntax.UntilStmt:
return p.untilStmt(stmt)
然后我们添加新的untilStmt方法添加到noder类型中：
// untilStmt converts the concrete syntax tree node UntilStmt into an AST
// node.
// 输入参数是真实语法树 UntilStmt节点，输出是抽象语法树节点
func (p *noder) untilStmt(stmt *syntax.UntilStmt) *Node {
p.openScope(stmt.Pos())
var n *Node
n = p.nod(stmt, OUNTIL, nil, nil)
if stmt.Init != nil {
n.Ninit.Set1(p.stmt(stmt.Init)) //真实语法树 Init 放入抽象语法树节点 Ninit中
}
if stmt.Cond != nil {
n.Left = p.expr(stmt.Cond) //真实语法树 Cond 放入抽象语法树节点 Left中
}
n.Nbody.Set(p.blockStmt(stmt.Body)) //真实语法树 Body 放入抽象语法树节点 Nbody中
p.closeAnotherScope()
return n
}
回想一下上面解释的通用“ Node”字段。在这里，我们将Init字段可选的初始化条件，将Left字段用于条件，并将Nbody字段用于循环体。
上述是我们为until语句构造AST节点所需要做的一切。完成上述部分后，我们可以得到 untilStmt 的AST节点，结果如下：
. . UNTIL l(13)
. . . EQ l(13)
. . . . NAME-main.i a(true) g(1) l(6) x(0) class(PAUTO)
. . . . LITERAL-0 l(13) untyped number
. . UNTIL-body
. . . ASOP-SUB l(14) implicit(true)
. . . . NAME-main.i a(true) g(1) l(6) x(0) class(PAUTO)
. . . . LITERAL-1 l(14) untyped number
. . . CALL l(15)
. . . . NONAME-fmt.Println a(true) x(0) fmt.Println
. . . CALL-list
. . . . LITERAL-"Hello, until!" l(15) untyped string
Type-check 类型检查
当AST转换完成时，编译的下一步是类型检查。除了检测类型错误外，Go中的类型检查还包括类型推断，这使我们可以编写如下语句：
res, err := func(args)
无需明确声明res和err的类型，Go类型检查器会自动推断。 初次之外，Go类型检查器还执行其他一些任务，例如将标识符链接到它们的声明以及计算编译时常量。该代码在gc/typecheck.go中。再一次，我们在for语句参数检查的分支下添加一个新的分支处理 OUNTIL，我们将这个分支添加到typecheck方法中（Go 1.15 是 typecheck1方法）：
case OUNTIL:
ok |= ctxStmt
typecheckslice(n.Ninit.Slice(), ctxStmt)
decldepth++
n.Left = typecheck(n.Left, ctxExpr)
n.Left = defaultlit(n.Left, nil)
if n.Left != nil {
t := n.Left.Type
if t != nil && !t.IsBoolean() {
yyerror("non-bool %L used as for condition", n.Left)
}
}
typecheckslice(n.Nbody.Slice(), ctxStmt)
decldepth--
它将类型分配给语句的各个部分，还检查条件是否是布尔值。
Analyze and rewrite AST 分析和重写 AST
经过类型检查后，编译器将经历AST分析和重写的多个阶段。确切的顺序在gc/main.go的gc.Main函数中列出( 代码中Phase1 , Phase2 等等)。在编译器命名法中，此类阶段通常称为 passes。
许多 passes 不需要修改就可以支持until，因为它们通常对所有语句类型起作用（在这里，gc.Node的通用结构很有用）。但是，有些passes 需要修改代码以支持until。例如逃逸分析，它试图找到哪些变量“逃逸”了它们的作用域，因此必须在堆而不是栈上进行分配。
逃逸分析适用于每种语句类型，因此我们必须在Escape.stmt（在 escape.go文件中）中添加以下switch分支：
case OUNTIL:
e.loopDepth++
e.discard(n.Left)
e.stmts(n.Nbody)
e.loopDepth--
最后，gc.Main调用可移植代码生成器（gc/pgen.go）来编译分析后的代码。代码生成器通过应用一系列AST转换开始，以将AST降低为更易于编译的形式。这是在compile函数中完成的，该函数首先调用 order。
这种转换（在gc/order.go中）对语句和表达式进行重新排序，以强制执行评估顺序。例如，它将把foo / = 10重写为foo = foo / 10，用多个单赋值语句替换多赋值语句，依此类推。
为了支持until语句，我们将其添加到Order.stmt中。
case OUNTIL:
t := o.markTemp()
n.Left = o.exprInPlace(n.Left)
n.Nbody.Prepend(o.cleanTempNoPop(t)...)
orderBlock(&n.Nbody, o.free)
o.out = append(o.out, n)
o.cleanTemp(t)
在order之后，compile会调用在gc/walk.go中的walk。此过程收集了一堆AST转换，这些转换有助于以后将AST降低到SSA。例如，它使用显式循环变量1。它还重写对运行时调用的映射访问等。
为了在walk中支持新语句，我们必须在walkstmt函数中添加一个switch分支。顺便说一句，我们也在这里将until语句重写成编译器已经知道如何处理的 AST 节点。 （这时因为，untilAST节点最终必须编译成SSA 和机器码，第一种方法，我们可以自己写编译成SSA 和机器码的代码；第二种方法将untilAST节点重写成已支持的节点）在until的情况下很容易，因为until和 for语句及其相似，我们只需将其重写为具有相反条件的for循环，如文章开头所示。这是转换代码：
case OUNTIL:
if n.Left != nil {
walkstmtlist(n.Left.Ninit.Slice())
init := n.Left.Ninit
n.Left.Ninit.Set(nil)
n.Left = nod(ONOT, walkexpr(n.Left, &init), nil)
n.Left = addinit(n.Left, init.Slice())
n.Op = OFOR
}
walkstmtlist(n.Nbody.Slice())
请注意，我们用包裹旧的n.Left的ONOT类型该条件代表一元运算符！）的新节点替换了旧n.Left，并用OFOR替换了n.Op（关键的一步，使用OFOR逻辑）。
如果我们在walk之后再次打印AST，我们将看到OUNTIL节点消失了，而新的OFOR节点取代了它。
尝试使用
现在，我们可以尝试使用经过修改的编译器，并运行一个使用until语句的示例程序：
$ cat useuntil.go
package main
import "fmt"
func main() {
i := 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
}
$ <src checkout>/bin/go run useuntil.go
Hello, until!
Hello, until!
Hello, until!
Hello, until!
提醒： <src checkout>是我们 Clone 的 Go 源码目录，对其进行更改并对其进行编译的目录（有关更多详细信息，请参见附录）。
part 1 总结
这是第1部分的内容。我们已经在Go编译器中成功实现了一条新语句。我们没有涵盖编译器的所有部分，因为我们可以通过重写until节点的AST来改用for节点来采取捷径。这是一种完全有效的编译策略，并且Go编译器已经进行了许多类似的转换以规范化AST（将许多形式减少为更少的形式，因此最后的编译阶段要做的工作较少）。也就是说，我们仍然有兴趣探索最后两个编译阶段-转换为SSA 和生成机器代码（也就是前面取巧的部分）。这将在[第2部分]中进行介绍。
附录-构建Go工具链
请先阅读Go贡献指南。这里有一些有关复制修改的Go编译器的快速说明。
有两种方法实验本文：
克隆official Go仓库并应用本文中描述的修改。
克隆Go仓库的我的分支并检出
adduntil分支，该分支已完成上述工作。
克隆的目录是 <src checkout>。
要编译工具链，请进入src/目录并运行./make.bash。构建后，我们也可以运行./all.bash来运行许多测试。运行make.bash会调用构建Go的完整的三步引导过程，但是在我的机器上只需要大约50秒钟。
构建完成后，工具链将与src一起安装在bin中。然后，我们可以通过运行bin/go install cmd/ compile来更快地重建编译器本身。
