當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

（四）Go 语言编译流程简述

發布時間：2025/3/15 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了（四）Go 语言编译流程简述小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

一、概述

Go 語言編譯的最后一個階段是根據 SSA 中間代碼生成機器碼，這里談的機器碼是在目標 CPU 架構上能夠運行的二進制代碼，中間代碼生成一節簡單介紹的從抽象語法樹到 SSA 中間代碼的生成過程，將近 50 個生成中間代碼的步驟中有一些過程嚴格上說是屬于機器碼生成階段的。

機器碼的生成過程其實是對 SSA 中間代碼的降級（lower）過程，在 SSA 中間代碼降級的過程中，編譯器將一些值重寫成了目標 CPU 架構的特定值，降級的過程處理了所有機器特定的重寫規則并對代碼進行了一定程度的優化；在 SSA 中間代碼生成階段的最后，Go 函數體的代碼會被轉換成?cmd/compile/internal/obj.Prog?結構。

指令集架構?#

首先需要介紹的就是指令集架構，雖然我們在第一節編譯過程概述中曾經講解過指令集架構，但是在這里還是需要引入更多的指令集架構知識。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖??計算機軟硬件之間的橋梁

指令集架構是計算機的抽象模型，在很多時候也被稱作架構或者計算機架構，它是計算機軟件和硬件之間的接口和橋梁1；一個為特定指令集架構編寫的應用程序能夠運行在所有支持這種指令集架構的機器上，也就是說如果當前應用程序支持 x86 的指令集，那么就可以運行在所有使用 x86 指令集的機器上，這其實就是抽象層的作用，每一個指令集架構都定義了支持的數據結構、寄存器、管理主內存的硬件支持（例如內存一致、地址模型和虛擬內存）、支持的指令集和 IO 模型，它的引入其實就在軟件和硬件之間引入了一個抽象層，讓同一個二進制文件能夠在不同版本的硬件上運行。

如果一個編程語言想要在所有的機器上運行，它就可以將中間代碼轉換成使用不同指令集架構的機器碼，這可比為不同硬件單獨移植要簡單的太多了。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖? 復雜指令集（CISC）和精簡指令集（RISC）

最常見的指令集架構分類方法是根據指令的復雜度將其分為復雜指令集（CISC）和精簡指令集（RISC），復雜指令集架構包含了很多特定的指令，但是其中的一些指令很少會被程序使用，而精簡指令集只實現了經常被使用的指令，不常用的操作都會通過組合簡單指令來實現。

復雜指令集的特點就是指令數目多并且復雜，每條指令的字節長度并不相等，x86 就是常見的復雜指令集處理器，它的指令長度大小范圍非常廣，從 1 到 15 字節不等，對于長度不固定的指令，計算機必須額外對指令進行判斷，這需要付出額外的性能損失2。

而精簡指令集對指令的數目和尋址方式做了精簡，大大減少指令數量的同時更容易實現，指令集中的每一個指令都使用標準的字節長度、執行時間相比復雜指令集會少很多，處理器在處理指令時也可以流水執行，提高了對并行的支持。作為一種常見的精簡指令集處理器，arm 使用 4 個字節作為指令的固定長度，省略了判斷指令的性能損失3，精簡指令集其實就是利用了我們耳熟能詳的 20/80 原則，用 20% 的基礎指令和它們的組合來解決問題。

最開始的計算機使用復雜指令集是因為當時計算機的性能和內存比較有限，業界需要盡可能地減少機器需要執行的指令，所以更傾向于高度編碼、長度不等以及多操作數的指令。不過隨著計算機性能的提升，出現了精簡指令集這種犧牲代碼密度換取簡單實現的設計；除此之外，硬件的飛速提升還帶來了更多的寄存器和更高的時鐘頻率，軟件開發人員也不再直接接觸匯編代碼，而是通過編譯器和匯編器生成指令，復雜的機器指令對于編譯器來說很難利用，所以精簡指令在這種場景下更適合。

復雜指令集和精簡指令集的使用是設計上的權衡，經過這么多年的發展，兩種指令集也相互借鑒和學習，與最開始剛被設計出來時已經有了較大的差別，對于軟件工程師來講，復雜的硬件設備對于我們來說已經是領域下三層的知識了，其實不太需要掌握太多，但是對指令集架構感興趣的讀者可以找一些資料開拓眼界。

機器碼生成?#

機器碼的生成在 Go 的編譯器中主要由兩部分協同工作，其中一部分是負責 SSA 中間代碼降級和根據目標架構進行特定處理的?cmd/compile/internal/ssa?包，另一部分是負責生成機器碼的?cmd/internal/obj4：

cmd/compile/internal/ssa?主要負責對 SSA 中間代碼進行降級、執行架構特定的優化和重寫并生成?cmd/compile/internal/obj.Prog?指令；
cmd/internal/obj?作為匯編器會將這些指令轉換成機器碼完成這次編譯；

SSA 降級?#

SSA 降級是在中間代碼生成的過程中完成的，其中將近 50 輪處理的過程中，lower?以及后面的階段都屬于 SSA 降級這一過程，這么多輪的處理會將 SSA 轉換成機器特定的操作：

var passes = [...]pass{...{name: "lower", fn: lower, required: true},{name: "lowered deadcode for cse", fn: deadcode}, // deadcode immediately before CSE avoids CSE making dead values live again{name: "lowered cse", fn: cse},...{name: "trim", fn: trim}, // remove empty blocks }

SSA 降級執行的第一個階段就是?lower，該階段的入口方法是?cmd/compile/internal/ssa.lower?函數，它會將 SSA 的中間代碼轉換成機器特定的指令：

func lower(f *Func) {applyRewrite(f, f.Config.lowerBlock, f.Config.lowerValue) }

向?cmd/compile/internal/ssa.applyRewrite?傳入的兩個函數?lowerBlock?和?lowerValue?是在中間代碼生成階段初始化 SSA 配置時確定的，這兩個函數會分別轉換函數中的代碼塊和代碼塊中的值。

假設目標機器使用 x86 的架構，最終會調用?cmd/compile/internal/ssa.rewriteBlock386?和?cmd/compile/internal/ssa.rewriteValue386?兩個函數，這兩個函數是兩個巨大的 switch 語句，前者總共有 2000 多行，后者將近 700 行，用于處理 x86 架構重寫的函數總共有將近 30000 行代碼，你能在?cmd/compile/internal/ssa/rewrite386.go?這里找到文件的全部內容，我們只節選其中的一段展示一下：

func rewriteValue386(v *Value) bool {switch v.Op {case Op386ADCL:return rewriteValue386_Op386ADCL_0(v)case Op386ADDL:return rewriteValue386_Op386ADDL_0(v) || rewriteValue386_Op386ADDL_10(v) || rewriteValue386_Op386ADDL_20(v)...} }func rewriteValue386_Op386ADCL_0(v *Value) bool {// match: (ADCL x (MOVLconst [c]) f)// cond:// result: (ADCLconst [c] x f)for {_ = v.Args[2]x := v.Args[0]v_1 := v.Args[1]if v_1.Op != Op386MOVLconst {break}c := v_1.AuxIntf := v.Args[2]v.reset(Op386ADCLconst)v.AuxInt = cv.AddArg(x)v.AddArg(f)return true}... }

重寫的過程會將通用的 SSA 中間代碼轉換成目標架構特定的指令，上述的?rewriteValue386_Op386ADCL_0?函數會使用?ADCLconst?替換?ADCL?和?MOVLconst?兩條指令，它能通過對指令的壓縮和優化減少在目標硬件上執行所需要的時間和資源。

我們在上一節中間代碼生成中已經介紹過?cmd/compile/internal/gc.compileSSA?中調用?cmd/compile/internal/gc.buildssa?的執行過程，我們在這里繼續介紹?cmd/compile/internal/gc.buildssa?函數返回后的邏輯：

func compileSSA(fn *Node, worker int) {f := buildssa(fn, worker)pp := newProgs(fn, worker)defer pp.Free()genssa(f, pp)pp.Flush() }

cmd/compile/internal/gc.genssa?函數會創建一個新的?cmd/compile/internal/gc.Progs?結構并將生成的 SSA 中間代碼都存入新建的結構體中，我們在上一節得到的 ssa.html 文件就包含最后生成的中間代碼：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖 genssa 的執行結果

上述輸出結果跟最后生成的匯編代碼已經非常相似了，隨后調用的?cmd/compile/internal/gc.Progs.Flush?會使用?cmd/internal/obj?包中的匯編器將 SSA 轉換成匯編代碼：

func (pp *Progs) Flush() {plist := &obj.Plist{Firstpc: pp.Text, Curfn: pp.curfn}obj.Flushplist(Ctxt, plist, pp.NewProg, myimportpath) }

cmd/compile/internal/gc.buildssa?中的?lower?和隨后的多個階段會對 SSA 進行轉換、檢查和優化，生成機器特定的中間代碼，接下來通過?cmd/compile/internal/gc.genssa?將代碼輸出到?cmd/compile/internal/gc.Progs?對象中，這也是代碼進入匯編器前的最后一個步驟。

匯編器?#

匯編器是將匯編語言翻譯為機器語言的程序，Go 語言的匯編器是基于 Plan 9 匯編器的輸入類型設計的，Go 語言對于匯編語言 Plan 9 和匯編器的資料十分缺乏，網上能夠找到的資料也大多都含糊不清，官方對匯編器在不同處理器架構上的實現細節也沒有明確定義：

The details vary with architecture, and we apologize for the imprecision; the situation is?not well-defined.5

我們在研究匯編器和匯編語言時不應該陷入細節，只需要理解匯編語言的執行邏輯就能夠幫助我們快速讀懂匯編代碼。當我們將如下的代碼編譯成匯編指令時，會得到如下的內容：

$ cat hello.go package hellofunc hello(a int) int {c := a + 2return c } $ GOOS=linux GOARCH=amd64 go tool compile -S hello.go "".hello STEXT nosplit size=15 args=0x10 locals=0x00x0000 00000 (main.go:3) TEXT "".hello(SB), NOSPLIT, $0-160x0000 00000 (main.go:3) FUNCDATA $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)0x0000 00000 (main.go:3) FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)0x0000 00000 (main.go:3) FUNCDATA $3, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)0x0000 00000 (main.go:4) PCDATA $2, $00x0000 00000 (main.go:4) PCDATA $0, $00x0000 00000 (main.go:4) MOVQ "".a+8(SP), AX0x0005 00005 (main.go:4) ADDQ $2, AX0x0009 00009 (main.go:5) MOVQ AX, "".~r1+16(SP)0x000e 00014 (main.go:5) RET0x0000 48 8b 44 24 08 48 83 c0 02 48 89 44 24 10 c3 H.D$.H...H.D$.. ...

上述匯編代碼都是由?cmd/internal/obj.Flushplist?這個函數生成的，該函數會調用架構特定的?Preprocess?和?Assemble?方法：

func Flushplist(ctxt *Link, plist *Plist, newprog ProgAlloc, myimportpath string) {...for _, s := range text {mkfwd(s)linkpatch(ctxt, s, newprog)ctxt.Arch.Preprocess(ctxt, s, newprog)ctxt.Arch.Assemble(ctxt, s, newprog)linkpcln(ctxt, s)ctxt.populateDWARF(plist.Curfn, s, myimportpath)} }

Go 編譯器會在最外層的主函數確定調用的?Preprocess?和?Assemble?方法，編譯器在 2.1.4 中提到的?cmd/compile.archInits?中根據目標硬件初始化當前架構使用的配置。

如果目標機器的架構是 x86，那么這兩個函數最終會使用?cmd/internal/obj/x86.preprocess?和?cmd/internal/obj/x86.span6，作者在這里就不展開介紹這兩個特別復雜的底層函數了，有興趣的讀者可以通過鏈接找到目標函數的位置了解預處理和匯編的處理過程，機器碼的生成也都是由這兩個函數組合完成的。

小結?#

機器碼生成作為 Go 語言編譯的最后一步，其實已經到了硬件和機器指令這一層，其中對于內存、寄存器的處理非常復雜并且難以閱讀，想要真正掌握這里的處理的步驟和原理還是需要耗費很多精力。

作為軟件工程師，如果不是 Go 語言編譯器的開發者或者需要經常處理匯編語言和機器指令，掌握這些知識的投資回報率實在太低，我們只需要對這個過程有所了解，補全知識上的盲點，在遇到問題時能夠快速定位即可。

二、詞法和語法分析

當使用通用編程語言1進行編寫代碼時，我們一定要認識到代碼首先是寫給人看的，只是恰好可以被機器編譯和執行，而很難被人理解和維護的代碼是非常糟糕。代碼其實是按照約定格式編寫的字符串，經過訓練的軟件工程師能對本來無意義的字符串進行分組和分析，按照約定的語法來理解源代碼，并在腦內編譯并運行程序。

既然工程師能夠按照一定的方式理解和編譯 Go 語言的源代碼，那么我們如何模擬人理解源代碼的方式構建一個能夠分析編程語言代碼的程序呢。我們在這一節中將介紹詞法分析和語法分析這兩個重要的編譯過程，這兩個過程能將原本機器看來無序意義的源文件轉換成更容易理解、分析并且結構化的抽象語法樹，接下來我們就看一看解析器眼中的 Go 語言是什么樣的。

2.2.1 詞法分析?#

源代碼在計算機『眼中』其實是一團亂麻，一個由字符組成的、無法被理解的字符串，所有的字符在計算器看來并沒有什么區別，為了理解這些字符我們需要做的第一件事情就是將字符串分組，這能夠降低理解字符串的成本，簡化源代碼的分析過程。

make(chan int)

哪怕是不懂編程的人看到上述文本的第一反應也應該會將上述字符串分成幾個部分 -?make、chan、int?和括號，這個憑直覺分解文本的過程就是詞法分析，詞法分析是將字符序列轉換為標記（token）序列的過程2。

lex?#

lex3?是用于生成詞法分析器的工具，lex 生成的代碼能夠將一個文件中的字符分解成 Token 序列，很多語言在設計早期都會使用它快速設計出原型。詞法分析作為具有固定模式的任務，出現這種更抽象的工具必然的，lex 作為一個代碼生成器，使用了類似 C 語言的語法，我們將 lex 理解為正則匹配的生成器，它會使用正則匹配掃描輸入的字符流，下面是一個 lex 文件的示例：

%{ #include <stdio.h> %}%% package printf("PACKAGE "); import printf("IMPORT "); \. printf("DOT "); \{ printf("LBRACE "); \} printf("RBRACE "); $ printf("LPAREN "); $ printf("RPAREN "); \" printf("QUOTE "); \n printf("\n"); [0-9]+ printf("NUMBER "); [a-zA-Z_]+ printf("IDENT "); %%

這個定義好的文件能夠解析?package?和?import?關鍵字、常見的特殊字符、數字以及標識符，雖然這里的規則可能有一些簡陋和不完善，但是用來解析下面的這一段代碼還是比較輕松的：

package mainimport ("fmt" )func main() {fmt.Println("Hello") }

.l?結尾的 lex 代碼并不能直接運行，我們首先需要通過?lex?命令將上面的?simplego.l?展開成 C 語言代碼，這里可以直接執行如下所示的命令編譯并打印文件中的內容：

$ lex simplego.l $ cat lex.yy.c ... int yylex (void) {...while ( 1 ) {... yy_match:do {register YY_CHAR yy_c = yy_ec[YY_SC_TO_UI(*yy_cp)];if ( yy_accept[yy_current_state] ) {(yy_last_accepting_state) = yy_current_state;(yy_last_accepting_cpos) = yy_cp;}while ( yy_chk[yy_base[yy_current_state] + yy_c] != yy_current_state ) {yy_current_state = (int) yy_def[yy_current_state];if ( yy_current_state >= 30 )yy_c = yy_meta[(unsigned int) yy_c];}yy_current_state = yy_nxt[yy_base[yy_current_state] + (unsigned int) yy_c];++yy_cp;} while ( yy_base[yy_current_state] != 37 );...do_action:switch ( yy_act )case 0:...case 1:YY_RULE_SETUPprintf("PACKAGE ");YY_BREAK... }

lex.yy.c4?的前 600 行基本都是宏和函數的聲明和定義，后面生成的代碼大都是為?yylex?這個函數服務的，這個函數使用有限自動機（Deterministic Finite Automaton、DFA）5的程序結構來分析輸入的字符流，上述代碼中?while?循環就是這個有限自動機的主體，你如果仔細看這個文件生成的代碼會發現當前的文件中并不存在?main?函數，main?函數是在 liblex 庫中定義的，所以在編譯時其實需要添加額外的?-ll?選項：

$ cc lex.yy.c -o simplego -ll $ cat main.go | ./simplego

當我們將 C 語言代碼通過 gcc 編譯成二進制代碼之后，就可以使用管道將上面提到的 Go 語言代碼作為輸入傳遞到生成的詞法分析器中，這個詞法分析器會打印出如下的內容：

PACKAGE IDENTIMPORT LPARENQUOTE IDENT QUOTE RPARENIDENT IDENT LPAREN RPAREN LBRACEIDENT DOT IDENT LPAREN QUOTE IDENT QUOTE RPAREN RBRACE

從上面的輸出我們能夠看到 Go 源代碼的影子，lex 生成的詞法分析器 lexer 通過正則匹配的方式將機器原本很難理解的字符串進行分解成很多的 Token，有利于后面的處理。

圖 ?從 .l 文件到二進制

到這里我們已經為各位讀者展示了從定義?.l?文件、使用 lex 將?.l?文件編譯成 C 語言代碼以及二進制的全過程，而最后生成的詞法分析器也能夠將簡單的 Go 語言代碼進行轉換成 Token 序列。lex 的使用還是比較簡單的，我們可以使用它快速實現詞法分析器，相信各位讀者對它也有了一定的了解。

Go?#

Go 語言的詞法解析是通過?src/cmd/compile/internal/syntax/scanner.go6?文件中的?cmd/compile/internal/syntax.scanner?結構體實現的，這個結構體會持有當前掃描的數據源文件、啟用的模式和當前被掃描到的 Token：

type scanner struct {sourcemode uintnlsemi bool// current token, valid after calling next()line, col uintblank bool // line is blank up to coltok tokenlit string // valid if tok is _Name, _Literal, or _Semi ("semicolon", "newline", or "EOF"); may be malformed if bad is truebad bool // valid if tok is _Literal, true if a syntax error occurred, lit may be malformedkind LitKind // valid if tok is _Literalop Operator // valid if tok is _Operator, _AssignOp, or _IncOpprec int // valid if tok is _Operator, _AssignOp, or _IncOp }

src/cmd/compile/internal/syntax/tokens.go7?文件中定義了 Go 語言中支持的全部 Token 類型，所有的?token?類型都是正整數，你可以在這個文件中找到一些常見 Token 的定義，例如：操作符、括號和關鍵字等：

const (_ token = iota_EOF // EOF// operators and operations_Operator // op...// delimiters_Lparen // (_Lbrack // [...// keywords_Break // break..._Type // type_Var // vartokenCount // )

從 Go 語言中定義的 Token 類型，我們可以將語言中的元素分成幾個不同的類別，分別是名稱和字面量、操作符、分隔符和關鍵字。詞法分析主要是由?cmd/compile/internal/syntax.scanner?這個結構體中的?cmd/compile/internal/syntax.scanner.next?方法驅動，這個 250 行函數的主體是一個 switch/case 結構：

func (s *scanner) next() {...s.stop()startLine, startCol := s.pos()for s.ch == ' ' || s.ch == '\t' || s.ch == '\n' && !nlsemi || s.ch == '\r' {s.nextch()}s.line, s.col = s.pos()s.blank = s.line > startLine || startCol == colbases.start()if isLetter(s.ch) || s.ch >= utf8.RuneSelf && s.atIdentChar(true) {s.nextch()s.ident()return}switch s.ch {case -1:s.tok = _EOFcase '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':s.number(false)...} }

cmd/compile/internal/syntax.scanner?每次都會通過?cmd/compile/internal/syntax.source.nextch?函數獲取文件中最近的未被解析的字符，然后根據當前字符的不同執行不同的 case，如果遇到了空格和換行符這些空白字符會直接跳過，如果當前字符是 0 就會執行?cmd/compile/internal/syntax.scanner.number?方法嘗試匹配一個數字。

func (s *scanner) number(seenPoint bool) {kind := IntLitbase := 10 // number basedigsep := 0invalid := -1 // index of invalid digit in literal, or < 0s.kind = IntLitif !seenPoint {digsep |= s.digits(base, &invalid)}s.setLit(kind, ok) }func (s *scanner) digits(base int, invalid *int) (digsep int) {max := rune('0' + base)for isDecimal(s.ch) || s.ch == '_' {ds := 1if s.ch == '_' {ds = 2} else if s.ch >= max && *invalid < 0 {_, col := s.pos()*invalid = int(col - s.col) // record invalid rune index}digsep |= dss.nextch()}return }

上述的?cmd/compile/internal/syntax.scanner.number?方法省略了很多的代碼，包括如何匹配浮點數、指數和復數，我們只是簡單看一下詞法分析匹配整數的邏輯：在 for 循環中不斷獲取最新的字符，將字符通過?cmd/compile/internal/syntax.source.nextch?方法追加到?cmd/compile/internal/syntax.scanner?持有的緩沖區中；

當前包中的詞法分析器?cmd/compile/internal/syntax.scanner?也只是為上層提供了?cmd/compile/internal/syntax.scanner.next?方法，詞法解析的過程都是惰性的，只有在上層的解析器需要時才會調用?cmd/compile/internal/syntax.scanner.next?獲取最新的 Token。

Go 語言的詞法元素相對來說還是比較簡單，使用這種巨大的 switch/case 進行詞法解析也比較方便和順手，早期的 Go 語言雖然使用 lex 這種工具來生成詞法解析器，但是最后還是使用 Go 來實現詞法分析器，用自己寫的詞法分析器來解析自己8。

?語法分析?#

語法分析是根據某種特定的形式文法（Grammar）對 Token 序列構成的輸入文本進行分析并確定其語法結構的過程9。從上面的定義來看，詞法分析器輸出的結果 — Token 序列是語法分析器的輸入。

語法分析的過程會使用自頂向下或者自底向上的方式進行推導，在介紹 Go 語言語法分析之前，我們會先來介紹語法分析中的文法和分析方法。

文法?#

上下文無關文法是用來形式化、精確描述某種編程語言的工具，我們能夠通過文法定義一種語言的語法，它主要包含一系列用于轉換字符串的生產規則（Production rule）10。上下文無關文法中的每一個生產規則都會將規則左側的非終結符轉換成右側的字符串，文法都由以下的四個部分組成：

終結符是文法中無法再被展開的符號，而非終結符與之相反，還可以通過生產規則進行展開，例如 “id”、“123” 等標識或者字面量11。

𝑁N?有限個非終結符的集合；
ΣΣ?有限個終結符的集合；
𝑃P?有限個生產規則12的集合；
𝑆S?非終結符集合中唯一的開始符號；

文法被定義成一個四元組?(𝑁,Σ,𝑃,𝑆)(N,Σ,P,S)，這個元組中的幾部分是上面提到的四個符號，其中最為重要的就是生產規則，每個生產規則都會包含非終結符、終結符或者開始符號，我們在這里可以舉個簡單的例子：

𝑆→𝑎𝑆𝑏S→aSb

𝑆→𝑎𝑏S→ab

𝑆→𝜖S→?

上述規則構成的文法就能夠表示 ab、aabb 以及 aaa..bbb 等字符串，編程語言的文法就是由這一系列的生產規則表示的，在這里我們可以從?src/cmd/compile/internal/syntax/parser.go13?文件中摘抄一些 Go 語言文法的生產規則：

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } . PackageClause = "package" PackageName . PackageName = identifier .ImportDecl = "import" ( ImportSpec | "(" { ImportSpec ";" } ")" ) . ImportSpec = [ "." | PackageName ] ImportPath . ImportPath = string_lit .TopLevelDecl = Declaration | FunctionDecl | MethodDecl . Declaration = ConstDecl | TypeDecl | VarDecl .

Go 語言更詳細的文法可以從?Language Specification14?中找到，這里不僅包含語言的文法，還包含詞法元素、內置函數等信息。

因為每個 Go 源代碼文件最終都會被解析成一個獨立的抽象語法樹，所以語法樹最頂層的結構或者開始符號都是 SourceFile：

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .

從 SourceFile 相關的生產規則我們可以看出，每一個文件都包含一個?package?的定義以及可選的?import?聲明和其他的頂層聲明（TopLevelDecl），每一個 SourceFile 在編譯器中都對應一個?cmd/compile/internal/syntax.File?結構體，你能從它們的定義中輕松找到兩者的聯系：

type File struct {Pragma PragmaPkgName *NameDeclList []DeclLines uintnode }

頂層聲明有五大類型，分別是常量、類型、變量、函數和方法，你可以在文件?src/cmd/compile/internal/syntax/parser.go?中找到這五大類型的定義。

ConstDecl = "const" ( ConstSpec | "(" { ConstSpec ";" } ")" ) . ConstSpec = IdentifierList [ [ Type ] "=" ExpressionList ] .TypeDecl = "type" ( TypeSpec | "(" { TypeSpec ";" } ")" ) . TypeSpec = AliasDecl | TypeDef . AliasDecl = identifier "=" Type . TypeDef = identifier Type .VarDecl = "var" ( VarSpec | "(" { VarSpec ";" } ")" ) . VarSpec = IdentifierList ( Type [ "=" ExpressionList ] | "=" ExpressionList ) .

上述的文法分別定義了 Go 語言中常量、類型和變量三種常見的結構，從文法中可以看到語言中的很多關鍵字?const、type?和?var，稍微回想一下我們日常接觸的 Go 語言代碼就能驗證這里文法的正確性。

除了三種簡單的語法結構之外，函數和方法的定義就更加復雜，從下面的文法我們可以看到 Statement 總共可以轉換成 15 種不同的語法結構，這些語法結構就包括我們經常使用的 switch/case、if/else、for 循環以及 select 等語句：

FunctionDecl = "func" FunctionName Signature [ FunctionBody ] . FunctionName = identifier . FunctionBody = Block .MethodDecl = "func" Receiver MethodName Signature [ FunctionBody ] . Receiver = Parameters .Block = "{" StatementList "}" . StatementList = { Statement ";" } .Statement =Declaration | LabeledStmt | SimpleStmt |GoStmt | ReturnStmt | BreakStmt | ContinueStmt | GotoStmt |FallthroughStmt | Block | IfStmt | SwitchStmt | SelectStmt | ForStmt |DeferStmt .SimpleStmt = EmptyStmt | ExpressionStmt | SendStmt | IncDecStmt | Assignment | ShortVarDecl .

這些不同的語法結構共同定義了 Go 語言中能夠使用的語法結構和表達式，對于 Statement 展開的更多內容這篇文章就不會詳細介紹了，感興趣的讀者可以直接查看?Go 語言說明書或者直接從?src/cmd/compile/internal/syntax/parser.go?文件中找到想要的答案。

分析方法?#

語法分析的分析方法一般分為自頂向下和自底向上兩種，這兩種方式會使用不同的方式對輸入的 Token 序列進行推導：

自頂向下分析：可以被看作找到當前輸入流最左推導的過程，對于任意一個輸入流，根據當前的輸入符號，確定一個生產規則，使用生產規則右側的符號替代相應的非終結符向下推導15；
自底向上分析：語法分析器從輸入流開始，每次都嘗試重寫最右側的多個符號，這其實是說解析器會從最簡單的符號進行推導，在解析的最后合并成開始符號16；

如果讀者無法理解上述的定義也沒有關系，我們會在這一節的剩余部分介紹兩種不同的分析方法以及它們的具體分析過程。

自頂向下?#

LL 文法17是一種使用自頂向下分析方法的文法，下面給出了一個常見的 LL 文法：

𝑆→𝑎𝑆1S→aS1

𝑆1→𝑏𝑆1S1→bS1

𝑆1→𝜖S1→?

假設我們存在以上的生產規則和輸入流 abb，如果這里使用自頂向下的方式進行語法分析，我們可以理解為每次解析器會通過新加入的字符判斷應該使用什么方式展開當前的輸入流：

𝑆S?（開始符號）

𝑎𝑆1aS1（規則 1)

𝑎𝑏𝑆1abS1（規則 2)

𝑎𝑏𝑏𝑆1abbS1（規則 2)

𝑎𝑏𝑏abb（規則 3)

這種分析方法一定會從開始符號分析，通過下一個即將入棧的符號判斷應該如何對當前堆棧中最右側的非終結符（𝑆S?或?𝑆1S1）進行展開，直到整個字符串中不存在任何的非終結符，整個解析過程才會結束。

自底向上?#

但是如果我們使用自底向上的方式對輸入流進行分析時，處理過程就會完全不同了，常見的四種文法 LR(0)、SLR、LR(1) 和 LALR(1) 使用了自底向上的處理方式18，我們可以簡單寫一個與上一節中效果相同的 LR(0) 文法：

𝑆→𝑆1S→S1

𝑆1→𝑆1𝑏S1→S1b

𝑆1→𝑎S1→a

使用上述等效的文法處理同樣地輸入流 abb 會使用完全不同的過程對輸入流進行展開：

𝑎a（入棧）

𝑆1S1（規則 3）

𝑆1𝑏S1b（入棧）

𝑆1S1（規則 2）

𝑆1𝑏S1b（入棧）

𝑆1S1（規則 2）

𝑆S（規則 1）

自底向上的分析過程會維護一個棧用于存儲未被歸約的符號，在整個過程中會執行兩種不同的操作，一種叫做入棧（Shift），也就是將下一個符號入棧，另一種叫做歸約（Reduce），也就是對最右側的字符串按照生產規則進行合并。

上述的分析過程和自頂向下的分析方法完全不同，這兩種不同的分析方法其實也代表了計算機科學中兩種不同的思想 — 從抽象到具體和從具體到抽象。

Lookahead?#

在語法分析中除了 LL 和 LR 這兩種不同類型的語法分析方法之外，還存在另一個非常重要的概念，就是向前查看（Lookahead），在不同生產規則發生沖突時，當前解析器需要通過預讀一些 Token 判斷當前應該用什么生產規則對輸入流進行展開或者歸約19，例如在 LALR(1) 文法中，需要預讀一個 Token 保證出現沖突的生產規則能夠被正確處理。

Go?#

Go 語言的解析器使用了 LALR(1) 的文法來解析詞法分析過程中輸出的 Token 序列20，最右推導加向前查看構成了 Go 語言解析器的最基本原理，也是大多數編程語言的選擇。

我們在概述中已經介紹了編譯器的主函數，該函數調用的?cmd/compile/internal/gc.parseFiles?會使用多個 Goroutine 來解析源文件，解析的過程會調用?cmd/compile/internal/syntax.Parse，該函數初始化了一個新的?cmd/compile/internal/syntax.parser?結構體并通過?cmd/compile/internal/syntax.parser.fileOrNil?方法開啟對當前文件的詞法和語法解析：

func Parse(base *PosBase, src io.Reader, errh ErrorHandler, pragh PragmaHandler, mode Mode) (_ *File, first error) {var p parserp.init(base, src, errh, pragh, mode)p.next()return p.fileOrNil(), p.first }

cmd/compile/internal/syntax.parser.fileOrNil?方法其實是對上面介紹的 Go 語言文法的實現，該方法首先會解析文件開頭的?package?定義：

// SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } . func (p *parser) fileOrNil() *File {f := new(File)f.pos = p.pos()if !p.got(_Package) {p.syntaxError("package statement must be first")return nil}f.PkgName = p.name()p.want(_Semi)

從上面的這一段方法中我們可以看出，當前方法會通過?cmd/compile/internal/syntax.parser.got?來判斷下一個 Token 是不是?package?關鍵字，如果是?package?關鍵字，就會執行?cmd/compile/internal/syntax.parser.name?來匹配一個包名并將結果保存到返回的文件結構體中。

for p.got(_Import) {f.DeclList = p.appendGroup(f.DeclList, p.importDecl)p.want(_Semi)}

確定了當前文件的包名之后，就開始解析可選的?import?聲明，每一個?import?在解析器看來都是一個聲明語句，這些聲明語句都會被加入到文件的?DeclList?中。

在這之后會根據編譯器獲取的關鍵字進入 switch 的不同分支，這些分支調用?cmd/compile/internal/syntax.parser.appendGroup?方法并在方法中傳入用于處理對應類型語句的?cmd/compile/internal/syntax.parser.constDecl、cmd/compile/internal/syntax.parser.typeDecl?函數。

for p.tok != _EOF {switch p.tok {case _Const:p.next()f.DeclList = p.appendGroup(f.DeclList, p.constDecl)case _Type:p.next()f.DeclList = p.appendGroup(f.DeclList, p.typeDecl)case _Var:p.next()f.DeclList = p.appendGroup(f.DeclList, p.varDecl)case _Func:p.next()if d := p.funcDeclOrNil(); d != nil {f.DeclList = append(f.DeclList, d)}default:...}}f.Lines = p.source.linereturn f }

cmd/compile/internal/syntax.parser.fileOrNil?使用了非常多的子方法對輸入的文件進行語法分析，并在最后會返回文件開始創建的?cmd/compile/internal/syntax.File?結構體。

讀到這里的人可能會有一些疑惑，為什么沒有看到詞法分析的代碼，這是因為詞法分析器?cmd/compile/internal/syntax.scanner?作為結構體被嵌入到了?cmd/compile/internal/syntax.parser?中，所以這個方法中的?p.next()?實際上調用的是?cmd/compile/internal/syntax.scanner.next?方法，它會直接獲取文件中的下一個 Token，所以詞法和語法分析一起進行的。

cmd/compile/internal/syntax.parser.fileOrNil?與在這個方法中執行的其他子方法共同構成了一棵樹，這棵樹根節點是?cmd/compile/internal/syntax.parser.fileOrNil，子節點是?cmd/compile/internal/syntax.parser.importDecl、cmd/compile/internal/syntax.parser.constDecl?等方法，它們與 Go 語言文法中的生產規則一一對應。

圖 2-8 Go 語言解析器的方法

cmd/compile/internal/syntax.parser.fileOrNil、cmd/compile/internal/syntax.parser.constDecl?等方法對應了 Go 語言中的生產規則，例如?cmd/compile/internal/syntax.parser.fileOrNil?實現的是：

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .

我們根據這個規則能很好地理解語法分析器的實現原理 - 將編程語言的所有生產規則映射到對應的方法上，這些方法構成的樹形結構最終會返回一個抽象語法樹。

因為大多數方法的實現都非常相似，所以這里就僅介紹?cmd/compile/internal/syntax.parser.fileOrNil?方法的實現了，想要了解其他方法的實現原理，讀者可以自行查看?src/cmd/compile/internal/syntax/parser.go?文件，該文件包含了語法分析階段的全部方法。

輔助方法?#

雖然這里不會展開介紹其他類似方法的實現，但是解析器運行過程中有幾個輔助方法我們還是要簡單說明一下，首先就是?cmd/compile/internal/syntax.parser.got?和?cmd/compile/internal/syntax.parser.want?這兩個常見的方法：

func (p *parser) got(tok token) bool {if p.tok == tok {p.next()return true}return false }func (p *parser) want(tok token) {if !p.got(tok) {p.syntaxError("expecting " + tokstring(tok))p.advance()} }

cmd/compile/internal/syntax.parser.got?只是用于快速判斷一些語句中的關鍵字，如果當前解析器中的 Token 是傳入的 Token 就會直接跳過該 Token 并返回?true；而?cmd/compile/internal/syntax.parser.want?就是對?cmd/compile/internal/syntax.parser.got?的簡單封裝了，如果當前 Token 不是我們期望的，就會立刻返回語法錯誤并結束這次編譯。

這兩個方法的引入能夠幫助工程師在上層減少判斷關鍵字的大量重復邏輯，讓上層語法分析過程的實現更加清晰。

另一個方法?cmd/compile/internal/synctax.parser.appendGroup?的實現就稍微復雜了一點，它的主要作用就是找出批量的定義，我們可以簡單舉一個例子：

var (a intb int )

這兩個變量其實屬于同一個組（Group），各種頂層定義的結構體?cmd/compile/internal/syntax.parser.constDecl、cmd/compile/internal/syntax.parser.varDecl?在進行語法分析時有一個額外的參數?cmd/compile/internal/syntax.Group，這個參數是通過?cmd/compile/internal/syntax.parser.appendGroup?方法傳遞進去的：

func (p *parser) appendGroup(list []Decl, f func(*Group) Decl) []Decl {if p.tok == _Lparen {g := new(Group)p.list(_Lparen, _Semi, _Rparen, func() bool {list = append(list, f(g))return false})} else {list = append(list, f(nil))}return list }

cmd/compile/internal/syntax.parser.appendGroup?方法會調用傳入的?f?方法對輸入流進行匹配并將匹配的結果追加到另一個參數?cmd/compile/internal/syntax.File?結構體中的?DeclList?數組中，import、const、var、type?和?func?聲明語句都是調用?cmd/compile/internal/syntax.parser.appendGroup?方法解析的。

節點?#

語法分析器最終會使用不同的結構體來構建抽象語法樹中的節點，其中根節點?cmd/compile/internal/syntax.File?我們已經在上面介紹過了，其中包含了當前文件的包名、所有聲明結構的列表和文件的行數：

type File struct {Pragma PragmaPkgName *NameDeclList []DeclLines uintnode }

src/cmd/compile/internal/syntax/nodes.go?文件中也定義了其他節點的結構體，其中包含全部聲明類型的，這里簡單看一下函數聲明的結構：

type (Decl interface {NodeaDecl()}FuncDecl struct {Attr map[string]boolRecv *FieldName *NameType *FuncTypeBody *BlockStmtPragma Pragmadecl} }

從函數定義中我們可以看出，函數在語法結構上主要由接受者、函數名、函數類型和函數體幾個部分組成，函數體?cmd/compile/internal/syntax.BlockStmt?是由一系列的表達式組成的，這些表達式共同組成了函數的主體：

圖 2-9 Go 語言函數定義的結構體

函數的主體其實是一個?cmd/compile/internal/syntax.Stmt?數組，cmd/compile/internal/syntax.Stmt?是一個接口，實現該接口的類型其實也非常多，總共有 14 種不同類型的?cmd/compile/internal/syntax.Stmt?實現：

圖 2-9 Go 語言的 14 種聲明

這些不同類型的?cmd/compile/internal/syntax.Stmt?構成了全部命令式的 Go 語言代碼，從中我們可以看到很多熟悉的控制結構，例如 if、for、switch 和 select，這些命令式的結構在其他的編程語言中也非常常見。

2.2.3 小結?#

這一節介紹了 Go 語言的詞法分析和語法分析過程，我們不僅從理論的層面介紹了詞法和語法分析的原理，還從源代碼出發詳細分析 Go 語言的編譯器是如何在底層實現詞法和語法解析功能的。

了解 Go 語言的詞法分析器?cmd/compile/internal/syntax.scanner?和語法分析器?cmd/compile/internal/syntax.parser?讓我們對解析器處理源代碼的過程有著比較清楚的認識，同時我們也在 Go 語言的文法和語法分析器中找到了熟悉的關鍵字和語法結構，加深了對 Go 語言的理解。

2.2.4 延伸閱讀?#

Lexical Scanning in Go - Rob Pike

通用編程語言 General-purpose programming language?https://en.wikipedia.org/wiki/General-purpose_programming_language???

詞法分析 Lexical analysis?https://en.wikipedia.org/wiki/Lexical_analysis???

詞法分析生成器?Lex - A Lexical Analyzer Generator???

生成的 simplego.lex.c 文件?https://gist.github.com/draveness/85db6ec4a4088b63ccccf7f09424f474???

有限自動機 DFA?https://en.wikipedia.org/wiki/Deterministic_finite_automaton???

go/scanner.go at master · golang/go · GitHub???

go/tokens.go at master · golang/go · GitHub???

Go 1.5 Bootstrap Plan?https://docs.google.com/document/d/1OaatvGhEAq7VseQ9kkavxKNAfepWy2yhPUBs96FGV28/edit???

語法分析 Syntactic analysis?https://en.wikipedia.org/wiki/Parsing???

https://en.wikipedia.org/wiki/Context-free_grammar???

終結符和非終結符?https://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols???

生產規則在計算機科學領域是符號替換的重寫規則，S -> aSb 就是可以用右側的 aSb 將左側的符號進行展開?https://en.wikipedia.org/wiki/Production_(computer_science)???

go/parser.go at master · golang/go · GitHub???

The Go Programming Language Specification?https://golang.org/ref/spec???

自頂向下解析?https://en.wikipedia.org/wiki/Top-down_parsing???

自底向上解析?https://en.wikipedia.org/wiki/Bottom-up_parsing???

LL 文法是一種上下文無關文法，可以使用 LL 解析器解析?https://en.wikipedia.org/wiki/LL_grammar???

LR 解析器是一種自底向上的解析器，它有很多 SLR、LALR、等變種?https://en.wikipedia.org/wiki/LR_parser???

https://en.wikipedia.org/wiki/Lookahead???

關于 Go 語言文法的討論?https://groups.google.com/forum/#!msg/golang-nuts/jVjbH2-emMQ/UdZlSNhd3DwJ???

關于 GO 語言的類型檢查可參見：Go 語言如何進行類型檢查 | Go 語言設計與實現?

關于 GO 語言的中間代碼生成可參見：詳解 Go 語言中間代碼生成 | Go 語言設計與實現

?關于 GO 語言的機器碼生成可參見：指令集架構、機器碼與 Go 語言 | Go 語言設計與實現

轉載自：?Go 語言編譯過程概述 | Go 語言設計與實現?

總結

以上是生活随笔為你收集整理的（四）Go 语言编译流程简述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：【Java】浅析Math类
下一篇：【数值分析】数值分析的微积分学基础