Golang之抽象语法树(ast)

AST

抽象语法树是将编程语言的源代码进行抽象语法的树状表示。树中每个节点都表示源码中的一个组成结构。大多数的编程语言都使用了AST作为源码的表示方式。

那么源码是怎么转换成AST的呢？

graph LR
  A[Source Code] --Lexer--> B[Tokens]
  B --Parser--> C[AST]

首先,词法分析器(Lexer)对源码(Source Code)进行词法分析，生成中间结果Token。然后由解释器(Parser)对Token进行检索生成AST。

其中词法分析器(Lexer)会对源码进行逐行扫描，识别出代码中的关键字，从而确定出单词的类型。然后转换成统一的词法单元Token.

Token

Token不仅包含关键字，还包含用户自定义的标识符、运算符、分隔符、和注释等。Token中由三个属性是比较重要的：词法单元的类型、源码中的文本形式、Token出现的位置。

在Go中Token被定义为一个枚举值，以表示不同的类型。Token被分为四种类型：特殊类型Token、基础面值Token、运算符Token、关键字Token。

1. 特殊类型的Token有错误、文件结束、注释三种：

   1
   2
   3
   4
   5
   6
    type Token int
    const (
        ILLEGAL Token = iota
        EOF
        COMMENT
    )
   

2. 基础面值的Token类型有整数、浮点数、复数、字符串、字符。Go规范中布尔类型的true和false并不在基础面值类型中。但是为了词法解析方便，go/token包将true和false等对应的标识符也作为面值Token一类。

   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
    literal_beg
    // Identifiers and basic type literals
    // (these tokens stand for classes of literals)
    IDENT  // main
    INT    // 12345
    FLOAT  // 123.45
    IMAG   // 123.45i
    CHAR   // 'a'
    STRING // "abc"
    literal_end
   

   literal_beg和literal_end之间就是面值类型。

3. 运算符和分隔符的Token类型：

   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
    operator_beg
    // Operators and delimiters
    ADD // +
    SUB // -
    MUL // *
    QUO // /
    REM // %
       
    AND     // &
    OR      // |
    XOR     // ^
    SHL     // <<
    SHR     // >>
    AND_NOT // &^
       
    ADD_ASSIGN // +=
    SUB_ASSIGN // -=
    MUL_ASSIGN // *=
    QUO_ASSIGN // /=
    REM_ASSIGN // %=
       
    AND_ASSIGN     // &=
    OR_ASSIGN      // |=
    XOR_ASSIGN     // ^=
    SHL_ASSIGN     // <<=
    SHR_ASSIGN     // >>=
    AND_NOT_ASSIGN // &^=
       
    LAND  // &&
    LOR   // ||
    ARROW // <-
    INC   // ++
    DEC   // --
       
    EQL    // ==
    LSS    // <
    GTR    // >
    ASSIGN // =
    NOT    // !
       
    NEQ      // !=
    LEQ      // <=
    GEQ      // >=
    DEFINE   // :=
    ELLIPSIS // ...
       
    LPAREN // (
    LBRACK // [
    LBRACE // {
    COMMA  // ,
    PERIOD // .
       
    RPAREN    // )
    RBRACK    // ]
    RBRACE    // }
    SEMICOLON // ;
    COLON     // :
    operator_end
   

   运算符主要有加减乘除等运算符号，还有位运算、比较运算、正负号、取地址符、管道读取等。此外还有括号、逗号、分号、冒号等分隔符。

4. 关键字Token则刚好对应Go语言的25个关键字：

   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
    keyword_beg
    // Keywords
    BREAK
    CASE
    CHAN
    CONST
    CONTINUE
       
    DEFAULT
    DEFER
    ELSE
    FALLTHROUGH
    FOR
       
    FUNC
    GO
    GOTO
    IF
    IMPORT
       
    INTERFACE
    MAP
    PACKAGE
    RANGE
    RETURN
       
    SELECT
    STRUCT
    SWITCH
    TYPE
    VAR
    keyword_end
   

Token是组成更复杂的逻辑代码的基础单元，对于编程语言而言它就像26个字母对于英文一样重要。

解析

利用go/parser 和 go/ast包可以方便的解析并打印出一个表达式的ast结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import (
    "go/ast"
    "go/parser"
)
expr, _ := parser.ParseExpr("1+2")
ast.Print(nil, expr)

0   *ast.BinaryExpr {
1   .  X: *ast.BasicLit {
2   .  .  ValuePos: 1
3   .  .  Kind: INT
4   .  .  Value: "1"
5   .  }
6   .  OpPos: 2
7   .  Op: +
8   .  Y: *ast.BasicLit {
9   .  .  ValuePos: 3
10  .  .  Kind: INT
11  .  .  Value: "2"
12  .  }
13  }

上面输出结果中的ast.BinaryExpr就代表一个二元表达式，操作符Op为 +，操作数X、Y为基本字面量类型ast.BasicLit。

Go语言中的一个包由多个文件组成，然后多个包链接为一个可执行文件，所以包中的一个个文件可以看作是Go语言的基本编译单元。因此go/token包还定义了FileSet和File对象，用于描述文件集和文件。

可以通过go/parser包中的ParseFile方查看一个文件的完整ast树结构:

1
2
3
4
5
6
7
8
src, _ := os.ReadFile("./code/hello.go")
fset := token.NewFileSet()
f, err := parser.ParseFile(fset, "hello.go", src, parser.AllErrors)
if err != nil {
    log.Fatal(err)
    return
}
ast.Print(nil, f)

parser.ParseFile方法得到的是ast.File类型的指针:

1
2
3
4
5
6
7
8
9
10
type File struct {
    Doc        *CommentGroup   // associated documentation; or nil
    Package    token.Pos       // position of "package" keyword
    Name       *Ident          // package name
    Decls      []Decl          // top-level declarations; or nil
    Scope      *Scope          // package scope (this file only)
    Imports    []*ImportSpec   // imports in this file
    Unresolved []*Ident        // unresolved identifiers in this file
    Comments   []*CommentGroup // list of all comments in the source file
}

• Name 表示文件对应包的名称
• Imports 为当前文件导入包的信息
• Comments 包含文件中的注释信息
• Decls 包含当前文件所有包级别的声明信息, 由ast.GenDecl和ast.FunDecl两种类型表示。其中ast.FuncDecl表示func定义，而ast.GenDecl则包含了import(导入的包)、type(类型定义)、const(常量)、var(变量)。

下面是ast.File的部分结构图：

graph TB
  File[ast.File] --> FileImports["Imports (ast.ImportSpec)"]
  File --> FileDecls["Decls (ast.Decls)"]
  FileImports --> import((import))
  FileDecls --> GenDecl[ast.GenDecl]
  GenDecl --> ImportSpec[ast.ImportSpec] & ValueSpec[ast.ValueSpec] & TypeSpec[ast.TypeSpec]
  FileDecls --> FuncDecl[ast.FuncDecl] --> func((func))
  ImportSpec --> import
  ValueSpec --> const((const)) & var((var)) & type((type))

用途

既然通过AST可以得到代码的组成结构，那么可以开发一些lint工具对代码进行语法、风格检查，错误提示等。除此之外还可以通过解析代码中的注释生成API文档。比如我最近在编写的一个小工具https://github.com/alovn/apidocgen 就是基于AST解析出源码中对api的注释，生成markdown格式的文档和mock数据。

此外基于AST也可以自己定制一套语法解析，自创一门编程语言。

• Previous
  Golang并发编程之singleflight
• Next
  P2P NAT类型