Golang 抽象語法樹 -AST- Step By Step
一、AST 基礎概念與入門必備
1.1 什麼是 AST（Abstract Syntax Tree）？
根據維基百科的介紹：在計算機科學中，抽象語法樹 (AST)，或者僅僅是語法樹，是用編程語言編寫的源代碼的抽象語法結構的樹狀表示。樹的每個節點都表示源代碼中出現的一個構造。
大多數編譯器和解釋器都使用 AST 作爲源代碼的內部表示，AST 通常會省略語法樹中的分號、換行字符、白空格、大括號、方括號和圓括號等。
1.2 生成 AST 的步驟？
下面我們來看看計算機是如何將一份代碼文件轉換成 AST 的。
首先，計算機先用一個詞法分析器(Lexer)對文本 (Source Code) 進行詞法分析，生成 Token。一般接下來是將它傳給一個解析器，然後檢索生成AST。上圖中有兩個關鍵的工具：lexer和 parser以及中間結果 Token。我們首先來看 Lexer 和 Parser。
Lexer - 又名詞法分析器：詞法分析器用來將字符序列轉換爲單詞 (Token)。詞法分析主要是完成：
-
對源程序的代碼進行從左到右的逐行掃描，識別出各個單詞，從而確定單詞的類型；
-
將識別出的單詞轉換爲統一的機內表示——詞法單元（Token）形式。
token 是一種類型 Map 的 key/value 形式，它由 <種別碼，屬性值> 組成，種別碼就是類型、屬性值就是值。例如下述代碼中：
go package main
const s = "foo"轉換爲 token 之後：
PACKAGE(package)
IDENT(main)
CONST(const)
IDENT(s)
ASSIGN(=)
STRING("foo")
EOF()通過上述的例子我們知道，詞法分析器的主要作用是將代碼按照單詞的維度進行 “分割”，注意該處的單詞可能與傳統意義上的單詞不一樣，例如，語言中的關鍵字是一個單詞、賦值=同樣是一個單詞、甚者換行符\n也是一個單詞，完成詞法分析後，我們可以得到該代碼文件的 token 數組，數組中的每一個元素爲一個 詞法單元(Token)。
Parser - 語法分析器： 語法分析器的作用是進行語法檢查、並構建由輸入的單詞 (Token) 組成的數據結構（一般是語法分析樹、抽象語法樹等層次化的數據結構）。
語法分析的分析方法一般分爲自頂向下和自底向上兩種：
-
自頂向下分析：可以被看作找到當前輸入流最左推導的過程，對於任意一個輸入流，根據當前的輸入符號，確定一個生產規則，使用生產規則右側的符號替代相應的非終結符向下推導；
-
自底向上分析：語法分析器從輸入流開始，每次都嘗試重寫最右側的多個符號，這其實是說解析器會從最簡單的符號進行推導，在解析的最後合併成開始符號；
（這裏的內容相對比較複雜，這裏不做介紹）
通過上述的敘述中，我們知道通過 “詞法分析” 和“語法分析”我們便可以得到 AST，例如：
package main
import (
"fmt"
)
func main() {
fmt.Printf("Hello, Golang\n")
}
上述代碼的 AST 爲：
0 *ast.File {
1 . Doc: nil
2 . Package: foo:1:1
3 . Name: *ast.Ident {
4 . . NamePos: foo:1:9
5 . . Name: "main"
6 . . Obj: nil
7 . }
8 . Decls: []ast.Decl (len = 2) {
9 . . 0: *ast.GenDecl {
10 . . . Doc: nil
11 . . . TokPos: foo:3:1
12 . . . Tok: import
13 . . . Lparen: foo:3:8
14 . . . Specs: []ast.Spec (len = 1) {
15 . . . . 0: *ast.ImportSpec {
16 . . . . . Doc: nil
17 . . . . . Name: nil
18 . . . . . Path: *ast.BasicLit {
19 . . . . . . ValuePos: foo:4:2
20 . . . . . . Kind: STRING
21 . . . . . . Value: "\"fmt\""
22 . . . . . }
23 . . . . . Comment: nil
24 . . . . . EndPos: -
25 . . . . }
26 . . . }
27 . . . Rparen: foo:5:1
28 . . }
29 . . 1: *ast.FuncDecl {
30 . . . Doc: nil
31 . . . Recv: nil
32 . . . Name: *ast.Ident {
33 . . . . NamePos: foo:7:6
34 . . . . Name: "main"
35 . . . . Obj: *ast.Object {
36 . . . . . Kind: func
37 . . . . . Name: "main"
38 . . . . . Decl: *(obj @ 29)
39 . . . . . Data: nil
40 . . . . . Type: nil
41 . . . . }
42 . . . }
43 . . . Type: *ast.FuncType {
44 . . . . Func: foo:7:1
45 . . . . Params: *ast.FieldList {
46 . . . . . Opening: foo:7:10
47 . . . . . List: nil
48 . . . . . Closing: foo:7:11
49 . . . . }
50 . . . . Results: nil
51 . . . }
52 . . . Body: *ast.BlockStmt {
53 . . . . Lbrace: foo:7:13
54 . . . . List: []ast.Stmt (len = 1) {
55 . . . . . 0: *ast.ExprStmt {
56 . . . . . . X: *ast.CallExpr {
57 . . . . . . . Fun: *ast.SelectorExpr {
58 . . . . . . . . X: *ast.Ident {
59 . . . . . . . . . NamePos: foo:8:2
60 . . . . . . . . . Name: "fmt"
61 . . . . . . . . . Obj: nil
62 . . . . . . . . }
63 . . . . . . . . Sel: *ast.Ident {
64 . . . . . . . . . NamePos: foo:8:6
65 . . . . . . . . . Name: "Printf"
66 . . . . . . . . . Obj: nil
67 . . . . . . . . }
68 . . . . . . . }
69 . . . . . . . Lparen: foo:8:12
70 . . . . . . . Args: []ast.Expr (len = 1) {
71 . . . . . . . . 0: *ast.BasicLit {
72 . . . . . . . . . ValuePos: foo:8:13
73 . . . . . . . . . Kind: STRING
74 . . . . . . . . . Value: "\"Hello, Golang\\n\""
75 . . . . . . . . }
76 . . . . . . . }
77 . . . . . . . Ellipsis: -
78 . . . . . . . Rparen: foo:8:30
79 . . . . . . }
80 . . . . . }
81 . . . . }
82 . . . . Rbrace: foo:9:1
83 . . . }
84 . . }
85 . }
86 . Scope: *ast.Scope {
87 . . Outer: nil
88 . . Objects: map[string]*ast.Object (len = 1) {
89 . . . "main": *(obj @ 35)
90 . . }
91 . }
92 . Imports: []*ast.ImportSpec (len = 1) {
93 . . 0: *(obj @ 15)
94 . }
95 . Unresolved: []*ast.Ident (len = 1) {
96 . . 0: *(obj @ 58)
97 . }
98 . Comments: nil
99 }
我們看到，即使非常簡單的代碼生成 AST 也非常複雜。那麼我們得到了抽象語法樹可以做什麼呢？
1.3 AST 的常見的幾個用途
常見的幾種用途：
-
代碼語法的檢查、代碼風格的檢查、代碼的格式化、代碼的高亮、代碼錯誤提示、代碼自動補全等等
-
如使用語言的 Lint 工具對代碼錯誤或風格的檢查，發現一些潛在的錯誤
-
IDE 的錯誤提示、格式化、高亮、自動補全等
-
代碼混淆壓縮
-
UglifyJS2 等
-
優化變更代碼，改變代碼結構使達到想要的結構
-
代碼打包工具 webpack、rollup 等等
-
CommonJS、AMD、CMD、UMD 等代碼規範之間的轉化
-
CoffeeScript、TypeScript、JSX 等轉化爲原生 Javascript
二、Golang 中的 AST
2.1 Golang 中的 AST
golang 官方提供的幾個包，可以幫助我們進行 AST 分析：
-
go/scanner：詞法解析，將源代碼分割成一個個 token
-
go/token：token 類型及相關結構體定義
-
go/ast：ast 的結構定義
-
go/parser：語法分析，讀取 token 流生成 ast
通過上述的四個庫，我們就可以實現 golang 代碼的語法樹分析。
通過前述我們知道，抽象語法樹有節點 (Node) 構成，從源代碼中(go/ast/ast.go) 我們可以看出，Golang 的 AST 主要由三種節點構成：分別是表達式和類型節點(Expressions and type nodes)、語句節點(statement nodes)和聲明節點(declaration nodes)。所有的節點都包含標識其在源代碼中開頭和結尾位置的信息。
// Interfaces
//
// There are 3 main classes of nodes: Expressions and type nodes,
// statement nodes, and declaration nodes. The node names usually
// match the corresponding Go spec production names to which they
// correspond. The node fields correspond to the individual parts
// of the respective productions.
//
// All nodes contain position information marking the beginning of
// the corresponding source text segment; it is accessible via the
// Pos accessor method. Nodes may contain additional position info
// for language constructs where comments may be found between parts
// of the construct (typically any larger, parenthesized subpart).
// That position information is needed to properly position comments
// when printing the construct.
// All node types implement the Node interface.
type Node interface {
Pos() token.Pos // position of first character belonging to the node
End() token.Pos // position of first character immediately after the node
}
// All expression nodes implement the Expr interface.
type Expr interface {
Node
exprNode()
}
// All statement nodes implement the Stmt interface.
type Stmt interface {
Node
stmtNode()
}
// All declaration nodes implement the Decl interface.
type Decl interface {
Node
declNode()
}
從代碼中看到，所有的 AST 節點都實現了ast.Node接口，它只是返回 AST 中的一個位置。
另外，還有 3 個主要接口實現了ast.Node。
-
ast.Expr - 代表表達式和類型的節點
-
ast.Stmt - 代表報表節點
-
ast.Decl - 代表聲明節點
從定義中可以看到，每個 Node 都滿足了ast.Node的接口。
2.2 Golang 的 AST 分析示例
我們將以下面這段代碼爲例子來介紹 Golang 的抽象語法樹。
代碼清單 2-1:
package hello
import "fmt"
func greet() {
var msg = "Hello World!"
fmt.Println(msg)
}
代碼清單 2-2:
package main
import (
"fmt"
"go/ast"
"go/parser"
"go/token"
)
var srcCode = `
package hello
import "fmt"
func greet() {
var msg = "Hello World!"
fmt.Println(msg)
}
`
func main() {
fset := token.NewFileSet()
f, err := parser.ParseFile(fset, "", srcCode, 0)
if err != nil {
fmt.Printf("err = %s", err)
}
ast.Print(fset, f)
}
執行go run main.go我們可以得到：
0 *ast.File {
1 . Package: 2:1
2 . Name: *ast.Ident {
3 . . NamePos: 2:9
4 . . Name: "hello"
5 . }
6 . Decls: []ast.Decl (len = 2) {
7 . . 0: *ast.GenDecl {
8 . . . TokPos: 4:1
9 . . . Tok: import
10 . . . Lparen: -
11 . . . Specs: []ast.Spec (len = 1) {
12 . . . . 0: *ast.ImportSpec {
13 . . . . . Path: *ast.BasicLit {
14 . . . . . . ValuePos: 4:8
15 . . . . . . Kind: STRING
16 . . . . . . Value: "\"fmt\""
17 . . . . . }
18 . . . . . EndPos: -
19 . . . . }
20 . . . }
21 . . . Rparen: -
22 . . }
23 . . 1: *ast.FuncDecl {
24 . . . Name: *ast.Ident {
25 . . . . NamePos: 6:6
26 . . . . Name: "greet"
27 . . . . Obj: *ast.Object {
28 . . . . . Kind: func
29 . . . . . Name: "greet"
30 . . . . . Decl: *(obj @ 23)
31 . . . . }
32 . . . }
33 . . . Type: *ast.FuncType {
34 . . . . Func: 6:1
35 . . . . Params: *ast.FieldList {
36 . . . . . Opening: 6:11
37 . . . . . Closing: 6:12
38 . . . . }
39 . . . }
40 . . . Body: *ast.BlockStmt {
41 . . . . Lbrace: 6:14
42 . . . . List: []ast.Stmt (len = 2) {
43 . . . . . 0: *ast.DeclStmt {
44 . . . . . . Decl: *ast.GenDecl {
45 . . . . . . . TokPos: 7:4
46 . . . . . . . Tok: var
47 . . . . . . . Lparen: -
48 . . . . . . . Specs: []ast.Spec (len = 1) {
49 . . . . . . . . 0: *ast.ValueSpec {
50 . . . . . . . . . Names: []*ast.Ident (len = 1) {
51 . . . . . . . . . . 0: *ast.Ident {
52 . . . . . . . . . . . NamePos: 7:8
53 . . . . . . . . . . . Name: "msg"
54 . . . . . . . . . . . Obj: *ast.Object {
55 . . . . . . . . . . . . Kind: var
56 . . . . . . . . . . . . Name: "msg"
57 . . . . . . . . . . . . Decl: *(obj @ 49)
58 . . . . . . . . . . . . Data: 0
59 . . . . . . . . . . . }
60 . . . . . . . . . . }
61 . . . . . . . . . }
62 . . . . . . . . . Values: []ast.Expr (len = 1) {
63 . . . . . . . . . . 0: *ast.BasicLit {
64 . . . . . . . . . . . ValuePos: 7:14
65 . . . . . . . . . . . Kind: STRING
66 . . . . . . . . . . . Value: "\"Hello World!\""
67 . . . . . . . . . . }
68 . . . . . . . . . }
69 . . . . . . . . }
70 . . . . . . . }
71 . . . . . . . Rparen: -
72 . . . . . . }
73 . . . . . }
74 . . . . . 1: *ast.ExprStmt {
75 . . . . . . X: *ast.CallExpr {
76 . . . . . . . Fun: *ast.SelectorExpr {
77 . . . . . . . . X: *ast.Ident {
78 . . . . . . . . . NamePos: 8:2
79 . . . . . . . . . Name: "fmt"
80 . . . . . . . . }
81 . . . . . . . . Sel: *ast.Ident {
82 . . . . . . . . . NamePos: 8:6
83 . . . . . . . . . Name: "Println"
84 . . . . . . . . }
85 . . . . . . . }
86 . . . . . . . Lparen: 8:13
87 . . . . . . . Args: []ast.Expr (len = 1) {
88 . . . . . . . . 0: *ast.Ident {
89 . . . . . . . . . NamePos: 8:14
90 . . . . . . . . . Name: "msg"
91 . . . . . . . . . Obj: *(obj @ 54)
92 . . . . . . . . }
93 . . . . . . . }
94 . . . . . . . Ellipsis: -
95 . . . . . . . Rparen: 8:17
96 . . . . . . }
97 . . . . . }
98 . . . . }
99 . . . . Rbrace: 9:1
100 . . . }
101 . . }
102 . }
103 . Scope: *ast.Scope {
104 . . Objects: map[string]*ast.Object (len = 1) {
105 . . . "greet": *(obj @ 27)
106 . . }
107 . }
108 . Imports: []*ast.ImportSpec (len = 1) {
109 . . 0: *(obj @ 12)
110 . }
111 . Unresolved: []*ast.Ident (len = 1) {
112 . . 0: *(obj @ 77)
113 . }
114 }
2.2 Golang 的 AST 分析
既然是一棵樹，我們便可以遍歷，體貼的 Golang 官方已經幫我們想好了如何去遍歷這棵樹：
代碼清單 2-3:
// Inspect traverses an AST in depth-first order: It starts by calling
// f(node); node must not be nil. If f returns true, Inspect invokes f
// recursively for each of the non-nil children of node, followed by a
// call of f(nil).
//
func Inspect(node Node, f func(Node) bool) {
Walk(inspector(f), node)
}
上述代碼是 golang 官方提供的代碼go/ast，從註釋中我們知道Inspect函數以深度遍歷的方式遍歷 AST，通過調用 f(node) 開始，節點不能爲零。如果 f 返回 true，Inspect 會爲節點的每個非零子節點遞歸調用 f，然後調用 f(nil)。（翻譯的不好）。使用 Inspect 對代碼清單 2-2 做簡單的修改：
代碼清單 2-4:
package main
import (
"fmt"
"go/ast"
"go/parser"
"go/token"
)
var srcCode = `
package hello
import "fmt"
func greet() {
var msg = "Hello World!"
fmt.Println(msg)
}
`
func main() {
fset := token.NewFileSet()
f, err := parser.ParseFile(fset, "", srcCode, 0)
if err != nil {
fmt.Printf("err = %s", err)
}
ast.Inspect(f, func(n ast.Node) bool {
// Called recursively.
ast.Print(fset, n)
return true
})
}
執行上述代碼我們可以得到 AST 的全部節點，由於原生的 AST 太長，這裏省略，給出 AST 的大體結構圖：
*ast.File
第一個要訪問的節點是*ast.File，它是所有 AST 節點的根。它只實現了ast.Node接口。
ast.File有引用包名、導入聲明和函數聲明作爲子節點。
*ast.Ident - 包名
我們可以看到包名是hello，在第一行聲明。
*ast.GenDecl - 導入聲明
從這我們可以看到，ast.GenDecl代表除函數以外的所有聲明，即import、const、var和type。
Tok代表一個詞性標記 -- 它指定了聲明的內容（import 或 const 或 type 或 var）。
這個 AST 節點告訴我們，import聲明在 foo.go 的第 3 行。
讓我們從上到下深入地看一下ast.GenDecl的下一個節點*ast.ImportSpec。
*ast.FuncDecl - 函數聲明
一個ast.FuncDecl節點代表一個函數聲明，但它只實現了ast.Node接口。上述圖片中我們看到一個ast.FuncDecl下面還有其餘的類型，例如*ast.Ident/*ast.Object等等。
如此多的類型我們不可能全部記住，因爲官方文件已經幫我們全部記住了，我們只需按需查詢即可：
go/ast的全部節點類型：https://pkg.go.dev/go/ast#pkg-types
下面這張表總結了 AST 常見的節點表，和源碼做對比可快速使用。
總結
本文首先介紹了 ast 的一些基礎概念以及生成步驟，以 golang 爲例介紹了 AST 的詳細實踐。利用 AST 我們可以做很多的事情，例如語法檢查、單測框架生成 (gotests 框架就是基於 ast 做的) 等等。
博主在工作中正在使用 ast 對開源的單元測試框架進行修改，以便提供編寫單元測試的效率，有什麼問題歡迎交流~
轉自： https://zhuanlan.zhihu.com/p/380421057
Go 開發大全
參與維護一個非常全面的 Go 開源技術資源庫。日常分享 Go, 雲原生、k8s、Docker 和微服務方面的技術文章和行業動態。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Hsc4f4PNw20k0r_gDmCIMw