前言

各位同行有沒有想過一件事，一個程序文件，比如 hello.go 是如何被編譯器理解的，平常在編寫程序時，IDE 又是如何提供代碼提示的。在這奧妙無窮的背后， AST（Abstract Syntax Tree）抽象語法樹功不可沒，他站在每一行程序的身后，默默無聞的工作，為繁榮的互聯(lián)網(wǎng)世界立下了汗馬功勞。

AST 抽象語法樹

AST 使用樹狀結(jié)構(gòu)來表達編程語言的結(jié)構(gòu)，樹中的每一個節(jié)點都表示源碼中的一個結(jié)構(gòu)。聽到這或許你的心里會咯噔一下，其實說通俗一點，在源代碼解析后會得到一串數(shù)據(jù)，這個數(shù)據(jù)自然的呈現(xiàn)樹狀結(jié)構(gòu)，它被稱之為 CST（Concrete Syntax Tree） 具體語法樹，在 CST 的基礎上保留核心結(jié)構(gòu)。忽略一些不重要的結(jié)構(gòu)，比如標點符號，空白符，括號等，就得到了 AST。

如何生成 AST 

生成 AST 大概需要兩個步驟，詞法分析lexical analysis和語法分析syntactic analysis 。

詞法分析 lexical analysis

lexical analysis 簡稱 lexer ，它表示字符串序列，也就是我們的源代碼轉(zhuǎn)化為 token 的過程，進行詞法分析的工具叫做詞法分析器（lexical analyzer，簡稱lexer），也叫掃描器（scanner）。Go 語言的 go/scanner 包提供詞法分析。 

func ScannerDemo() {
	// 源代碼
	src := []byte(`
func demo() {
	fmt.Println("When you are old and gray and full of sleep")
}
`)

	// 初始化標記
	var s scanner.Scanner
	fset := token.NewFileSet()
	file := fset.AddFile("", fset.Base(), len(src))
	s.Init(file, src, nil, scanner.ScanComments)

	// Scan 進行掃碼并打印出結(jié)果
	for {
		pos, tok, lit := s.Scan()
		if tok == token.EOF {
			break
		}
		fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
	}
}

打印的結(jié)果我們接著往下看。

標記 token

標記(token)  是詞法分析后留下的產(chǎn)物，是構(gòu)成源代碼的最小單位，但是這些 token 之間沒有任何邏輯關系。以上述代碼為例：

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

經(jīng)過詞法分析后，會得到：

在 Go 語言中，如果 token 類型就是一個字面量，例如整型，字符串類型等，那么它的值就是相對應的值，比如上表的 STRING；如果 token 是 Go 的關鍵詞，那么它的值就是關鍵詞，比如上表的 fun；對于分號，它的值則是換行符；其他 token 類要么是不合法的，如果是合法的，則值為空字符串，比如上表的 {。

語法分析 syntactic analysis

不具備邏輯關系的 token 經(jīng)過語法分析（syntactic analysis，也叫 parsing）就可以得到具有邏輯關系的 CST 具體語法樹，然后對 CST 進行分析提煉即可得到 AST 抽象語法樹。完成語法分析的工具叫做語法分析器（parser）。Go 語言的 go/parser 提供語法分析。

func ParserDemo() {
	src := `
package main
`
	fset := token.NewFileSet()
	// 如果 src 為 nil，則使用第二個參數(shù)，它可以是一個 .go 文件地址
	f, err := parser.ParseFile(fset, "", src, 0)
	if err != nil {
		panic(err)
	}

	ast.Print(fset, f)
}

打印出來的 AST：

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

它包含了源代碼的結(jié)構(gòu)信息，看起來像一個 JSON。

總結(jié)

源代碼經(jīng)過詞法分析后得到 token(標記)，token 經(jīng)過語法分析得到 CST 具體語法樹，在 CST 上創(chuàng)建 AST 抽象語法樹。 來個圖圖或許更直觀：

Go 的抽象語法樹

這里我們以一個具體的例子來看：從 go 代碼中提取所有結(jié)構(gòu)體的名稱。

// 源碼
type A struct{}
type B struct{}
type C struct{}

func ExampleGetStructName() {
	fileSet := token.NewFileSet()
	node, err := parser.ParseFile(fileSet, "demo.go", nil, parser.ParseComments)
	if err != nil {
		return
	}

	ast.Inspect(node, func(n ast.Node) bool {
		if v, ok := n.(*ast.TypeSpec); ok {
			fmt.Println(v.Name.Name)
		}
		return true
	})
	// Output:
	// A
	// B
	// C
}

到此這篇關于以Golang為例詳解AST抽象語法樹的原理與實現(xiàn)的文章就介紹到這了,更多相關Go AST抽象語法樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論