序
这是两部分系列中的第一篇文章，该系列采用基于教程的方法来探索Go编译器。编译器很大，可能需要一本书去正确描述，本文章的想法是提供一种“深度优先"的探索思路。作者计划在将来写更多关于编译器特定领域的描述性文章。 我们将更改Go编译器添加一个新的语言特性（仅用来探索编译器的实现），并构建一个修改后的编译器来使用。
原文链接
注：一些编译器专业术语仍然沿用了英文。
任务：添加一个新语句
许多语言都有一个while语句，在Go中使用for表示：
for <some-condition> {
<loop body>
}
在Go中添加while语句是简单的，因为只需要简单的将while翻译为for。所以我们选择了一个更具有挑战性的任务：添加until。until与while相似，只是将判定条件改为了否定，意为“直到……”。例如：
i := 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
与下面代码的意思是相同的：
i := 4
for i != 0 {
i--
fmt.Println("Hello, until!")
}
我们还可以继续增大任务的难度，在until语句中加入初始化功能。
until i := 4; i == 0 {
i--
fmt.Println("Hello, until!")
}
本系列文章将会实现这个功能。
Ps：这只是一个实验性的练习，因为Go的极简主义是绝对正确的设计选择，所以我认为在Go中添加until并不是一个好的想法。
Go编译器的高级结构
Go默认的编译器（gc）有一个相当传统的结构，如果您之前使用过其他编译器，你可以很快熟悉它：
相对于Go存储库根目录，编译器的代码实现位于Go根目录下src/cmd/compile/internal；本文后续内容提到的代码路径都是相对于该目录的相对路径。它全部用Go编写，具有很好的可读性。 在这篇文章中，我们将逐一分析这些阶段，以便添加了支持until语句所需的代码。
查看src/cmd/compile中的README文件，以获得编译步骤的详细分步说明，该文件是这篇文章的好伴侣。
词法分析器
扫描器（也称为词法分析器）将源代码文本分解为编译器的离散实体。例如关键字for转换为常量_For；...字符转换为_DotDotDot；而.自身被转换为_Dot等等。
词法分析器在syntax包中实现，我们需要做的只是使它理解一个新的关键字-until。 文件syntax/tokens.go包含编译器理解的所有词法单元(tokens)，我们将添加一个新的词法单元_Until：
_Fallthrough // fallthrough
_For // for
_Until // until
_Func // func
右侧的注释是很重要的，它用来标识文本中的token。运行在tokens列表的上方的go generate可以自动生成相关代码。
//go:generate stringer -type token -linecomment
添加token后必须手动运行go generate，来生成源码中的syntax/token_string.go。为了重新生成它，在syntax目录运行以下命令:
GOROOT=<src checkout> go generate tokens.go 你可能会遇到running "stringer": exec: "stringer": executable file not found in $PATH，需要执行如下命令后继续：
go get -u golang.org/x/tools/cmd/stringer
从Go 1.12开始，GOROOT设置是必不可少的，并且必须指向我们正在修改编译器代码的源码根路径。
运行go generate重新生成syntax/token_string.go后，我尝试重新编译编译器时遇到了panic: imperfect hash
panic来自syntax/scanner.go中的这段代码：
// 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 must be power of two
func init() {
// populate keywordMap
for tok := _Break; tok <= _Var; tok++ {
h := hash([]byte(tok.String()))
if keywordMap[h] != 0 {
panic("imperfect hash")
}
keywordMap[h] = tok
}
}
编译器试图构建“完美”哈希表去对应关键字和token的关系以便进行查找。“完美”意味着它希望没有碰撞，将每个关键字都映射到一个索引组成一个线性数组。哈希函数是ad-hoc（它只查看字符串标记的第一个字符的内容），并且调试冲突的原因很困难。为了暂时解决这个问题，我将查找表的大小更改为[1<<7]token，从而将查找数组的大小从64更改为128。这给了散列函数更多的空间来分发它的关键字，结果是冲突消失了。
为了解决这个问题，您需要修改syntax/scanner.go中的
var keywordMap [1 << 6]token 修改为：
var keywordMap [1 << 7]token
语法分析器
Go有一个相当标准的递归下降式的语法分析器（Parse），它将词法分析器生成的tokens换为具体的语法树。 我们首先在syntax/nodes.go中为until添加一个新的节点类型（可以添加在ForStmt struct后）：
UntilStmt struct {
Init SimpleStmt
Cond Expr
Body *BlockStmt
stmt
}
我从ForStmt借用了整体结构，用于for循环。 与for类似，我们的until语句有几个可选的子语句：
until <init>; <cond> {
<body>
}
<init>和<cond>都是可选的，但省略<cond>并不常见。 UntilStmt.stmt嵌入字段用于所有语法树语句并包含位置信息。
语法分析器本身在syntax/parser.go中完成。parser.stmtOrNil方法解析当前位置的语句。 它查看当前token并决定要解析哪个语句。 以下是我们添加的代码的摘录（在switch p.tok中添加case _Until:）：
switch p.tok {
case _Lbrace:
return p.blockStmt("")
// ...
case _For:
return p.forStmt()
case _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语句的header。在一般的形式中，它支持三个部分(用分号分隔)。在for语句中，第三部分可以用于“post”语句，但我们不会支持这个，在until中我们只对前两个感兴趣。
请注意，header接受原始的token，以便能够区分它所服务的语句类型；例如，它会拒绝if的“post”语句(在if语句中只可以加入初始化和判断条件语句，没有第三个参数去修改条件变量)。在until中我们也应该明确地拒绝它，但这个现在还没有实现。
这些都是我们需要对解析器进行的所有更改。因为until在结构上与现有语句非常相似，所以我们可以重用大部分功能。
如果我们使用编译器转储语法树(syntax.Fdump)解析并运行下面的代码后:
i = 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
我们将得到until语句的这个片段：
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)
现在已经具有了源代码的语法树表示，编译器构建了一个抽象语法树。我曾经写过关于抽象语法树和具体语法树的文章（Abstract vs. Concrete syntax trees）——如果您不熟悉它们之间的区别，那么有必要查看一下。然而，在Go中这种情况在将来可能会改变。Golang编译器最初是用C语言编写的，后来自动翻译成Golang，所以编译器的部分代码是C时代遗留下来的，另外一部分则是较新的。未来可能会重构只留下一种语法树，但是现在(Go 1.12)，这是我们必须遵循的过程。
AST代码存在于gc包中，节点类型在gc/syntax.go中定义（不要与定义CST的语法包混淆！）
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
// ...
我们首先在gc/syntax.go的const列表中添加一个新的常量来标识until节点
// statements
// ...
OFALL // fallthrough
OFOR // for Ninit; Left; Right { Nbody }
OUNTIL // until Ninit; Left { Nbody }
我们将再次运行go generate，这次是在gc/syntax.go上，为新节点类型生成一个字符串表示：
// from the gc directory
GOROOT=<src checkout> go generate syntax.go
这应该更新gc/op_string.go文件以包含OUNTIL。现在是时候为我们的新节点类型编写实际的CST->AST转换代码了。
转换在gc/noder.go中完成。 我们将在现有的for语句支持之后继续对我们的更改进行建模，从stmtFall开始，stmtFall具有语句类型的switch-case结构，即在gc/noder.go的stmtFall方法中添加case *syntax.UntilStmt：
case *syntax.ForStmt:
return p.forStmt(stmt)
case *syntax.UntilStmt:
return p.untilStmt(stmt)
然后仍然在gc/noder.go中对noder类型添加新的方法untilStmt：
// untilStmt converts the concrete syntax tree node UntilStmt into an AST
// node.
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))
}
if stmt.Cond != nil {
n.Left = p.expr(stmt.Cond)
}
n.Nbody.Set(p.blockStmt(stmt.Body))
p.closeAnotherScope()
return n
}
回想一下上面解释的通用Node字段。这里，我们使用Init字段作为可选初始化器，Left字段作为条件，Nbody字段作为循环体。
这就是我们为until语句构造AST节点所需的全部内容。如果在完成后对AST进行dump操作，我们将会得到：
. . 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
类型检查
编译的下一步是类型检查，它在AST上完成。 除了检测类型错误之外，Go中的类型检查还包括类型推断，它允许我们编写如下语句：
res, err := func(args)
不需要明确声明res和err的类型。Go类型检查器还会执行一些任务，比如将标识符链接到它们的声明中，以及计算编译时的常数。类型检查的相关代码在gc/typecheck.go中，同样，在for语句的引导下，我们将把这个子句添加到typecheck中的switch-case中（gc/typecheck.go中typecheck1的switch n.Op中）：
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--
它为语句的各个部分分配类型，并检查条件在布尔上下文中是否有效。
分析和重写抽象语法树
在类型检查之后，编译器会经历AST分析和重写的几个阶段。 确切的顺序在gc/ main.go中的gc.Main函数中列出。 在编译器命名法中，这些阶段通常称为passes。
大部分的pass不需要修改去支持until，因为它们通常用于所有语句类型（这里gc.Node的通用结构很有用）。然而，还是有些需要修改，例如escape analysis（逃逸分析），它试图找到哪些变量“逃出”了它们的函数范围，因此必须在堆上而不是堆栈上分配。
Escape分析适用于每种语句类型，因此我们必须在Escape.stmt中添加switch-case结构（译者没有找到在哪里添加下面的代码，可能版本不同，可能逃逸分析是另外的工程实现的，不过这个代码不影响我们正常编译和后续的功能验证）：
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语句，我们将其添加到gc/order.go中Order.stmt的switch-case结构中：
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。walk收集了一系列AST转换，这些转换有助于稍后将AST降低到SSA。例如，它将for循环中的range子句重写为具有显式循环变量的简单形式的for循环[1]。 它还重写了对运行时调用的map的访问等等。
要在walk中支持新语句，我们必须在walkstmt函数中添加switch-case子句。顺便说一下，这也是我们可以通过将它重写为编译器已经知道如何处理的AST节点来“实现”我们的until语句的地方。在until的case中是很简单的，如文章开头所示，我们只是将它重写为一个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。
如果我们在walk之后再次对AST进行dump操作，我们将看到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!
大功告成~
你也可以将 i := 4 until i == 0合并为一条语句until i:=4;i == 0
提醒：<src checkout>是我们检出Go的目录，更改并编译它（有关详细信息，请参阅附录）。
结束
这是第一部分。我们已经在Go编译器中成功实现了一个新语句。我们没有覆盖编译器的所有部分，因为我们采取了一个捷径，通过使用for节点去替换until节点的AST。这是一个非常有效的编译策略，Go编译器已经有许多类似的转换来规范化AST（将许多形式减少为更少的形式，因此编译的最后阶段做的工作较少）。但我们仍然有兴趣探索最后两个编译阶段 - 转换为SSA和生成机器代码。这将在第2部分中介绍。
附录-编译Go工具链
请先阅读《Go贡献指南》。 以下是有关复制修改后的Go编译器的一些快速说明，如本文所示。 有两种方式可以尝试本文的修改：
- 克隆Go官方仓库，手动应用本文中描述的修改。
- 克隆作者fork的Go官方仓库，并且检出
adduntil分支，所有这些更改已经与一些调试助手一起应用。 克隆目录是整个帖子中<src checkout>的位置。
要编译工具链，请进入src/目录并运行./make.bash。 我们也可以运行./all.bash来构建它之后运行许多测试。 运行make.bash会调用构建Go的完整3步引导过程，但在我的（老化）机器上只需要大约50秒。
构建完成后，工具链将安装在与src同级的bin中。 然后我们可以通过运行bin /go install cmd/compile来更快地重建编译器本身。
[1]Go has some special "magic" range clauses like a range over a string which splits its up into runes. This is where such transformations are implemented.
