【翻译】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 节点。 (这时因为,until
AST节点最终必须编译成SSA 和机器码,第一种方法,我们可以自己写编译成SSA 和机器码的代码;第二种方法将until
AST节点重写成已支持的节点)在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
来更快地重建编译器本身。