以 Golang 为例详解 AST 抽象语法树

前言

各位同行有没有想过一件事，一个程序文件，比如 hello.go 是如何被编译器理解的，平常在编写程序时，IDE 又是如何提供代码提示的。在这奥妙无穷的背后， AST（Abstract Syntax Tree）抽象语法树功不可没，他站在每一行程序的身后，默默无闻的工作，为繁荣的互联网世界立下了汗马功劳。
AST 抽象语法树

AST 使用树状结构来表达编程语言的结构，树中的每一个节点都表示源码中的一个结构。听到这或许你的心里会咯噔一下，其实说通俗一点，在源代码解析后会得到一串数据，这个数据自然的呈现树状结构，它被称之为 CST（Concrete Syntax Tree） 具体语法树，在 CST 的基础上保留核心结构。忽略一些不重要的结构，比如标点符号，空白符，括号等，就得到了 AST。
如何生成 AST 

生成 AST 大概需要两个步骤，词法分析lexical analysis和语法分析syntactic analysis 。
词法分析 lexical analysis

lexical analysis 简称 lexer ，它表示字符串序列，也就是我们的源代码转化为 token 的过程，进行词法分析的工具叫做词法分析器（lexical analyzer，简称lexer），也叫扫描器（scanner）。Go 语言的 go/scanner 包提供词法分析。 

1. func ScannerDemo() {
2.         // 源代码
3.         src := []byte(`
4. func demo() {
5.         fmt.Println("When you are old and gray and full of sleep")
6. }
7. `)
9.         // 初始化标记
10.         var s scanner.Scanner
11.         fset := token.NewFileSet()
12.         file := fset.AddFile("", fset.Base(), len(src))
13.         s.Init(file, src, nil, scanner.ScanComments)
15.         // Scan 进行扫码并打印出结果
16.         for {
17.                 pos, tok, lit := s.Scan()
18.                 if tok == token.EOF {
19.                         break
20.                 }
21.                 fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
22.         }
23. }

复制代码

打印的结果我们接着往下看。
标记 token

标记(token)  是词法分析后留下的产物，是构成源代码的最小单位，但是这些 token 之间没有任何逻辑关系。以上述代码为例：

1. func demo() {
2.         fmt.Println("When you are old and gray and full of sleep")
3. }

复制代码

经过词法分析后，会得到：

token	literal（字面量，以string表示）
func	"func"
IDENT	"demo"
(	""
)	""
{	""
IDENT	"fmt"
.	""
IDENT	"rintln"
(	""
STRING	"\"When you are old and gray and full of sleep\""
)	""
;	"\n"
}	""
;	"\n"

在 Go 语言中，如果 token 类型就是一个字面量，例如整型，字符串类型等，那么它的值就是相对应的值，比如上表的 STRING；如果 token 是 Go 的关键词，那么它的值就是关键词，比如上表的 fun；对于分号，它的值则是换行符；其他 token 类要么是不合法的，如果是合法的，则值为空字符串，比如上表的 {。
语法分析 syntactic analysis

不具备逻辑关系的 token 经过语法分析（syntactic analysis，也叫 parsing）就可以得到具有逻辑关系的 CST 具体语法树，然后对 CST 进行分析提炼即可得到 AST 抽象语法树。完成语法分析的工具叫做语法分析器（parser）。Go 语言的 go/parser 提供语法分析。

1. func ParserDemo() {
2.         src := `
3. package main
4. `
5.         fset := token.NewFileSet()
6.         // 如果 src 为 nil，则使用第二个参数，它可以是一个 .go 文件地址
7.         f, err := parser.ParseFile(fset, "", src, 0)
8.         if err != nil {
9.                 panic(err)
10.         }
12.         ast.Print(fset, f)
13. }

复制代码

打印出来的 AST：

1. 0  *ast.File {
2. 1  .  Package: 2:1
3. 2  .  Name: *ast.Ident {
4. 3  .  .  NamePos: 2:9
5. 4  .  .  Name: "main"
6. 5  .  }
7. 6  .  FileStart: 1:1
8. 7  .  FileEnd: 2:14
9. 8  .  Scope: *ast.Scope {
10. 9  .  .  Objects: map[string]*ast.Object (len = 0) {}
11. 10  .  }
12. 11  }

复制代码

它包含了源代码的结构信息，看起来像一个 JSON。
总结

源代码经过词法分析后得到 token(标记)，token 经过语法分析得到 CST 具体语法树，在 CST 上创建 AST 抽象语法树。 来个图图或许更直观：

Go 的抽象语法树

这里我们以一个具体的例子来看：从 go 代码中提取所有结构体的名称。

1. // 源码
2. type A struct{}
3. type B struct{}
4. type C struct{}

复制代码

1. func ExampleGetStructName() {
2.         fileSet := token.NewFileSet()
3.         node, err := parser.ParseFile(fileSet, "demo.go", nil, parser.ParseComments)
4.         if err != nil {
5.                 return
6.         }
8.         ast.Inspect(node, func(n ast.Node) bool {
9.                 if v, ok := n.(*ast.TypeSpec); ok {
10.                         fmt.Println(v.Name.Name)
11.                 }
12.                 return true
13.         })
14.         // Output:
15.         // A
16.         // B
17.         // C
18. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！