【翻译】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语句,untilwhile功能大体一致,只是当条件为否时才执行循环。下述一个例子:

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包中。因此我们需要在这里新增一个关键字untilsyntax/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。我们的新untilfor是及其相似的,因此我们的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方法被使用来解析iffor 语句的头部(也就是InitCond),这和 until的头部是一样的,因此我们直接重用该方法。一般的形式下,它支持三个部分(以分号分隔)。在for语句中,第三部分可用于“ post”语句,但是我们不会在until中支持它,因此我们只使用前两部分。注意,header方法参数接受源 Token (判断是解析if还是for),以便能够区分所服务的语句类型。例如,它将拒绝ifpost语句。我们也应该在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)

无需明确声明reserr的类型,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.gogc.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的情况下很容易,因为untilfor语句及其相似,我们只需将其重写为具有相反条件的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.LeftONOT类型该条件代表一元运算符!)的新节点替换了旧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编译器的快速说明。

有两种方法实验本文:

  1. 克隆official Go仓库并应用本文中描述的修改。

  2. 克隆Go仓库的我的分支并检出adduntil分支,该分支已完成上述工作。

克隆的目录是 <src checkout>

要编译工具链,请进入src/目录并运行./make.bash。构建后,我们也可以运行./all.bash来运行许多测试。运行make.bash会调用构建Go的完整的三步引导过程,但是在我的机器上只需要大约50秒钟。

构建完成后,工具链将与src一起安装在bin中。然后,我们可以通过运行bin/go install cmd/ compile来更快地重建编译器本身。

not found!