Golang 抽象语法树(AST) Step By Step
【导读】本文介绍了 go 语言的抽象语法树。
一、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
- EOF -
Go 开发大全
参与维护一个非常全面的Go开源技术资源库。日常分享 Go, 云原生、k8s、Docker和微服务方面的技术文章和行业动态。
关注后获取
回复 Go 获取6万star的Go资源库
分享、点赞和在看
支持我们分享更多好文章，谢谢！