序
這是兩部分系列中的第一篇文章螃征，該系列采用基于教程的方法來探索Go編譯器潮罪。編譯器很大寒砖，可能需要一本書去正確描述谅猾，本文章的想法是提供一種“深度優(yōu)先"的探索思路柄慰。作者計劃在將來寫更多關于編譯器特定領域的描述性文章。 我們將更改Go編譯器添加一個新的語言特性（僅用來探索編譯器的實現(xiàn)）税娜，并構建一個修改后的編譯器來使用坐搔。
原文鏈接
注：一些編譯器專業(yè)術語仍然沿用了英文。
任務：添加一個新語句
許多語言都有一個while語句敬矩，在Go中使用for表示：
for <some-condition> {
<loop body>
}
在Go中添加while語句是簡單的概行，因為只需要簡單的將while翻譯為for。所以我們選擇了一個更具有挑戰(zhàn)性的任務：添加until谤绳。until與while相似占锯，只是將判定條件改為了否定，意為“直到……”缩筛。例如：
i := 4
until i == 0 {
i--
fmt.Println("Hello, until!")
}
與下面代碼的意思是相同的：
i := 4
for i != 0 {
i--
fmt.Println("Hello, until!")
}
我們還可以繼續(xù)增大任務的難度消略，在until語句中加入初始化功能。
until i := 4; i == 0 {
i--
fmt.Println("Hello, until!")
}
本系列文章將會實現(xiàn)這個功能瞎抛。
Ps：這只是一個實驗性的練習艺演，因為Go的極簡主義是絕對正確的設計選擇，所以我認為在Go中添加until并不是一個好的想法桐臊。
Go編譯器的高級結構
Go默認的編譯器（gc）有一個相當傳統(tǒng)的結構胎撤，如果您之前使用過其他編譯器，你可以很快熟悉它：
相對于Go存儲庫根目錄断凶，編譯器的代碼實現(xiàn)位于Go根目錄下src/cmd/compile/internal伤提；本文后續(xù)內容提到的代碼路徑都是相對于該目錄的相對路徑。它全部用Go編寫认烁，具有很好的可讀性肿男。 在這篇文章中，我們將逐一分析這些階段却嗡，以便添加了支持until語句所需的代碼舶沛。
查看src/cmd/compile中的README文件，以獲得編譯步驟的詳細分步說明窗价，該文件是這篇文章的好伴侶如庭。
詞法分析器
掃描器（也稱為詞法分析器）將源代碼文本分解為編譯器的離散實體。例如關鍵字for轉換為常量_For撼港；...字符轉換為_DotDotDot坪它；而.自身被轉換為_Dot等等。
詞法分析器在syntax包中實現(xiàn)餐胀，我們需要做的只是使它理解一個新的關鍵字-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扣汪，需要執(zhí)行如下命令后繼續(xù)：
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的關系以便進行查找恐锣。“完美”意味著它希望沒有碰撞舞痰，將每個關鍵字都映射到一個索引組成一個線性數(shù)組土榴。哈希函數(shù)是ad-hoc（它只查看字符串標記的第一個字符的內容），并且調試沖突的原因很困難响牛。為了暫時解決這個問題玷禽，我將查找表的大小更改為[1<<7]token，從而將查找數(shù)組的大小從64更改為128呀打。這給了散列函數(shù)更多的空間來分發(fā)它的關鍵字矢赁，結果是沖突消失了。
為了解決這個問題贬丛，您需要修改syntax/scanner.go中的
var keywordMap [1 << 6]token 修改為：
var keywordMap [1 << 7]token
語法分析器
Go有一個相當標準的遞歸下降式的語法分析器（Parse）撩银，它將詞法分析器生成的tokens換為具體的語法樹。 我們首先在syntax/nodes.go中為until添加一個新的節(jié)點類型（可以添加在ForStmt struct后）：
UntilStmt struct {
Init SimpleStmt
Cond Expr
Body *BlockStmt
stmt
}
我從ForStmt借用了整體結構豺憔，用于for循環(huán)蜒蕾。 與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
}
我們重用現(xiàn)有的parser.header方法褒纲，該方法解析if和for語句的header准夷。在一般的形式中，它支持三個部分(用分號分隔)莺掠。在for語句中衫嵌，第三部分可以用于“post”語句，但我們不會支持這個彻秆，在until中我們只對前兩個感興趣楔绞。
請注意，header接受原始的token唇兑，以便能夠區(qū)分它所服務的語句類型酒朵；例如，它會拒絕if的“post”語句(在if語句中只可以加入初始化和判斷條件語句扎附，沒有第三個參數(shù)去修改條件變量)蔫耽。在until中我們也應該明確地拒絕它，但這個現(xiàn)在還沒有實現(xiàn)留夜。
這些都是我們需要對解析器進行的所有更改匙铡。因為until在結構上與現(xiàn)有語句非常相似图甜，所以我們可以重用大部分功能。
如果我們使用編譯器轉儲語法樹(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)
現(xiàn)在已經(jīng)具有了源代碼的語法樹表示鳖眼，編譯器構建了一個抽象語法樹具则。我曾經(jīng)寫過關于抽象語法樹和具體語法樹的文章（Abstract vs. Concrete syntax trees）——如果您不熟悉它們之間的區(qū)別，那么有必要查看一下具帮。然而，在Go中這種情況在將來可能會改變低斋。Golang編譯器最初是用C語言編寫的蜂厅，后來自動翻譯成Golang，所以編譯器的部分代碼是C時代遺留下來的膊畴，另外一部分則是較新的掘猿。未來可能會重構只留下一種語法樹，但是現(xiàn)在(Go 1.12)唇跨，這是我們必須遵循的過程稠通。
AST代碼存在于gc包中，節(jié)點類型在gc/syntax.go中定義（不要與定義CST的語法包混淆Ｂ虿）
Go的AST的結構與CST不同改橘。所有AST節(jié)點都使用syntax.Node類型，而不是每個節(jié)點類型具有其專用的結構類型玉控，這是一種區(qū)分聯(lián)合飞主，它包含許多不同類型的字段。并且某些字段是通用的高诺，可以用于大多數(shù)節(jié)點類型：
// 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節(jié)點
// statements
// ...
OFALL // fallthrough
OFOR // for Ninit; Left; Right { Nbody }
OUNTIL // until Ninit; Left { Nbody }
我們將再次運行go generate碌识，這次是在gc/syntax.go上，為新節(jié)點類型生成一個字符串表示：
// from the gc directory
GOROOT=<src checkout> go generate syntax.go
這應該更新gc/op_string.go文件以包含OUNTIL∈現(xiàn)在是時候為我們的新節(jié)點類型編寫實際的CST->AST轉換代碼了筏餐。
轉換在gc/noder.go中完成。 我們將在現(xiàn)有的for語句支持之后繼續(xù)對我們的更改進行建模牡拇，從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字段作為循環(huán)體趟畏。
這就是我們?yōu)?code>until語句構造AST節(jié)點所需的全部內容。如果在完成后對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類型檢查器還會執(zhí)行一些任務，比如將標識符鏈接到它們的聲明中著洼，以及計算編譯時的常數(shù)樟遣。類型檢查的相關代碼在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--
它為語句的各個部分分配類型，并檢查條件在布爾上下文中是否有效液荸。
分析和重寫抽象語法樹
在類型檢查之后瞻佛，編譯器會經(jīng)歷AST分析和重寫的幾個階段。 確切的順序在gc/ main.go中的gc.Main函數(shù)中列出娇钱。 在編譯器命名法中伤柄，這些階段通常稱為passes。
大部分的pass不需要修改去支持until文搂，因為它們通常用于所有語句類型（這里gc.Node的通用結構很有用）适刀。然而，還是有些需要修改煤蹭，例如escape analysis（逃逸分析）蔗彤，它試圖找到哪些變量“逃出”了它們的函數(shù)范圍，因此必須在堆上而不是堆棧上分配疯兼。
Escape分析適用于每種語句類型然遏，因此我們必須在Escape.stmt中添加switch-case結構（譯者沒有找到在哪里添加下面的代碼，可能版本不同吧彪，可能逃逸分析是另外的工程實現(xiàn)的待侵，不過這個代碼不影響我們正常編譯和后續(xù)的功能驗證）：
case OUNTIL:
e.loopDepth++
e.discard(n.Left)
e.stmts(n.Nbody)
e.loopDepth--
最后，gc.Main調用可移植代碼生成器（gc/pgen.go）來編譯分析的代碼姨裸。 代碼生成器首先應用一系列AST轉換秧倾，將AST降低為更容易編譯的形式。 這是在compile函數(shù)中完成的傀缩，它從調用order開始那先。
這種轉換(在gc/order.go中)對語句和表達式重新排序，以強制執(zhí)行求值順序赡艰。例如售淡，它將把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函數(shù)調用gc/walk.go中的walk汤纸。walk收集了一系列AST轉換衩茸，這些轉換有助于稍后將AST降低到SSA。例如贮泞，它將for循環(huán)中的range子句重寫為具有顯式循環(huán)變量的簡單形式的for循環(huán)[1]楞慈。 它還重寫了對運行時調用的map的訪問等等。
要在walk中支持新語句啃擦，我們必須在walkstmt函數(shù)中添加switch-case子句囊蓝。順便說一下，這也是我們可以通過將它重寫為編譯器已經(jīng)知道如何處理的AST節(jié)點來“實現(xiàn)”我們的until語句的地方议惰。在until的case中是很簡單的，如文章開頭所示乡恕，我們只是將它重寫為一個for循環(huán)言询，并使用倒裝條件。下面是轉換的代碼實現(xiàn)：
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類型（表示一元运杭！運算符）的新節(jié)點替換n.Left（條件），并用OFOR替換n.Op函卒。
如果我們在walk之后再次對AST進行dump操作辆憔，我們將看到OUNTIL節(jié)點消失并且新的OFOR節(jié)點取而代之。
看下效果
現(xiàn)在报嵌，我們可以試用修改后的編譯器并運行一個使用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的目錄，更改并編譯它（有關詳細信息，請參閱附錄）萧求。
結束
這是第一部分俊卤。我們已經(jīng)在Go編譯器中成功實現(xiàn)了一個新語句。我們沒有覆蓋編譯器的所有部分血筑，因為我們采取了一個捷徑绘沉，通過使用for節(jié)點去替換until節(jié)點的AST。這是一個非常有效的編譯策略豺总，Go編譯器已經(jīng)有許多類似的轉換來規(guī)范化AST（將許多形式減少為更少的形式车伞，因此編譯的最后階段做的工作較少）。但我們仍然有興趣探索最后兩個編譯階段 - 轉換為SSA和生成機器代碼喻喳。這將在第2部分中介紹另玖。
附錄-編譯Go工具鏈
請先閱讀《Go貢獻指南》。 以下是有關復制修改后的Go編譯器的一些快速說明，如本文所示日矫。 有兩種方式可以嘗試本文的修改：
- 克隆Go官方倉庫赂弓，手動應用本文中描述的修改。
- 克隆作者fork的Go官方倉庫哪轿，并且檢出
adduntil分支盈魁，所有這些更改已經(jīng)與一些調試助手一起應用。 克隆目錄是整個帖子中<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.
