乐趣区

关于golang:Go编译原理系列5抽象语法树构建

jiezi

前言

在上一篇语法分析中，咱们晓得了 Go 编译器是如何依照 Go 的文法，解析 go 文本文件中的各种申明类型（import、var、const、func 等）。语法分析阶段将整个源文件解析到一个 File 的构造体中，源文件中各种申明类型解析到 File.DeclList 中。最终生成以 File 构造体为根节点，importDecl、constDecl、typeDecl、varDecl、FuncDecl 等为子节点的语法树

首先咱们须要明确的就是，形象语法树的作用其实就是为了后边进行类型查看、代码格调查看等等。总之，有了形象语法树，编译器就能够精准的定位到代码的任何中央，对其进行一些列的操作及验证等

本文为形象语法树的构建，咱们晓得，在编译器前端必须将源程序构建成一种两头示意模式，以便在编译器的后端进行应用，形象语法树就是一种常见的树状的两头示意模式。所以本文次要是介绍 Go 编译器将语法树构建成形象语法树都做了哪些事件？

形象语法树构建概览

以下先从整体上意识形象语法树构建过程，可能跨度比拟大，具体实现细节在下一部分介绍

在上一篇的语法解析阶段咱们晓得，Go 编译器会起多个协程，将每一个源文件都解析成一棵语法树。具体代码的地位是：src/cmd/compile/internal/gc/noder.go → parseFiles

func parseFiles(filenames []string) uint {noders := make([]*noder, 0, len(filenames))
    // Limit the number of simultaneously open files.
    sem := make(chan struct{}, runtime.GOMAXPROCS(0)+10)

    for _, filename := range filenames {
        p := &noder{basemap: make(map[*syntax.PosBase]*src.PosBase),
            err:     make(chan syntax.Error),
        }
        noders = append(noders, p)
        // 起多个协程对源文件进行语法解析
        go func(filename string) {sem <- struct{}{}
            defer func() { <-sem}()
            defer close(p.err)
            base := syntax.NewFileBase(filename)

            f, err := os.Open(filename)
            if err != nil {p.error(syntax.Error{Msg: err.Error()})
                return
            }
            defer f.Close()

            p.file, _ = syntax.Parse(base, f, p.error, p.pragma, syntax.CheckBranches) // errors are tracked via p.error
        }(filename)
    }

  // 开始将每一棵语法树构建成形象语法树
    var lines uint
    for _, p := range noders {
        for e := range p.err {p.yyerrorpos(e.Pos, "%s", e.Msg)
        }

        p.node() // 构建形象语法树的外围实现
        lines += p.file.Lines
        p.file = nil // release memory

        ......
    }

    localpkg.Height = myheight

    return lines
}

在将源文件解析成一棵语法树之后，Go 编译器会将每一棵语法树（源文件）构建成形象语法树。其外围代码就在 p.node()这个办法中：

func (p *noder) node() {
    ......

    xtop = append(xtop, p.decls(p.file.DeclList)...)

    ......
    clearImports()}

p.node()这个办法的外围局部是 p.decls(p.file.DeclList) 办法，该办法实现了 将源文件中的各种申明类型转换成一个一个的形象语法树 ，即 import、var、type、const、func 申明都会成为一个 根节点，根节点下边蕴含以后申明的子节点

p.decls(p.file.DeclList)的实现如下：

func (p *noder) decls(decls []syntax.Decl) (l []*Node) {
    var cs constState

    for _, decl := range decls {p.setlineno(decl)
        switch decl := decl.(type) {
        case *syntax.ImportDecl:
            p.importDecl(decl)

        case *syntax.VarDecl:
            l = append(l, p.varDecl(decl)...)

        case *syntax.ConstDecl:
            l = append(l, p.constDecl(decl, &cs)...)

        case *syntax.TypeDecl:
            l = append(l, p.typeDecl(decl))

        case *syntax.FuncDecl:
            l = append(l, p.funcDecl(decl))

        default:
            panic("unhandled Decl")
        }
    }

    return
}

从整体上来看，该办法其实就是将语法树中的各种申明类型，都转换成了以各种申明为根节点的形象语法树（Node 构造），最终语法树就变成了一个节点数组（Node）

下边能够看一下这个 Node 构造体长什么样

type Node struct {
    // Tree structure.
    // Generic recursive walks should follow these fields.
    // 通用的递归遍历，应该遵循这些字段
    Left  *Node // 左子节点
    Right *Node // 右子节点
    Ninit Nodes
    Nbody Nodes
    List  Nodes // 左子树
    Rlist Nodes // 右子树

    // most nodes
    Type *types.Type // 节点类型
    Orig *Node // original form, for printing, and tracking copies of ONAMEs

    // func
    Func *Func // 办法

    // ONAME, OTYPE, OPACK, OLABEL, some OLITERAL
    Name *Name // 变量名、类型明、包名等等

    Sym *types.Sym  // various
    E   interface{} // Opt or Val, see methods below

    // Various. Usually an offset into a struct. For example:
    // - ONAME nodes that refer to local variables use it to identify their stack frame position.
    // - ODOT, ODOTPTR, and ORESULT use it to indicate offset relative to their base address.
    // - OSTRUCTKEY uses it to store the named field's offset.
    // - Named OLITERALs use it to store their ambient iota value.
    // - OINLMARK stores an index into the inlTree data structure.
    // - OCLOSURE uses it to store ambient iota value, if any.
    // Possibly still more uses. If you find any, document them.
    Xoffset int64

    Pos src.XPos

    flags bitset32

    Esc uint16 // EscXXX

    Op  Op // 以后结点的属性
    aux uint8
}

晓得上边正文中的几个字段的含意，根本就够用了。外围是 Op 这个字段，它标识了每个结点的属性。你能够在：src/cmd/compile/internal/gc/syntax.go 中看到所有 Op 的定义，它都是以 O 结尾的，也都是整数，每个 Op 都有本人的语义

const (
    OXXX Op = iota

    // names
    ONAME // var or func name 遍历名或办法名
    // Unnamed arg or return value: f(int, string) (int, error) {etc}
    // Also used for a qualified package identifier that hasn't been resolved yet.
    ONONAME
    OTYPE    // type name 变量类型
    OPACK    // import
    OLITERAL // literal 标识符

    // expressions
    OADD          // Left + Right  加法
    OSUB          // Left - Right  减法
    OOR           // Left | Right  或运算
    OXOR          // Left ^ Right
    OADDSTR       // +{List} (string addition, list elements are strings)
    OADDR         // &Left
    ......
    // Left = Right or (if Colas=true) Left := Right
    // If Colas, then Ninit includes a DCL node for Left.
    OAS
    // List = Rlist (x, y, z = a, b, c) or (if Colas=true) List := Rlist
    // If Colas, then Ninit includes DCL nodes for List
    OAS2
    OAS2DOTTYPE // List = Right (x, ok = I.(int))
    OAS2FUNC    // List = Right (x, y = f())
  ......
)

比方当某一个节点的 Op 为 OAS，该节点代表的语义就是 Left := Right。当节点的 Op 为 OAS2 时，代表的语义就是 x, y, z = a, b, c

假如有这样一个申明语句：a := b + c(6)，构建成形象语法树就长下边这样

最终每种申明语句都会被构建成这样的形象语法树。上边是对形象语法树有个大抵的意识，下边就具体的看各种申明语句是如何一步一步的被构建成形象语法树的

语法分析阶段解析各种申明

为了更直观的看到形象语法树是如何解析各种申明的，咱们能够间接利用 go 提供的规范库中的办法来进行调试。因为在前边并没有直观的看到一个申明被语法解析进去之后长什么样子，所以下边通过规范库中的办法来展现一下

💡 提醒：在前边的 Go 词法剖析这篇文章中提到，Go 提供的规范库中的词法解析、语法解析、形象语法树构建等的实现跟 Go 编译器中的实现或设计不一样，然而整体的思路是一样的

根底面值解析

根底面值有 整数 、 浮点数 、 复数 、 字符、字符串、标识符。从上一篇 Go 的语法解析中晓得，Go 编译器中根底面值的构造体为

BasicLit struct {
        Value string   // 值
        Kind  LitKind  // 那种类型的根底面值，范畴（IntLit、FloatLit、ImagLit、RuneLit、StringLit）Bad   bool // true means the literal Value has syntax errors
        expr
}

而在规范库中，根底面值的构造体长下边这样

BasicLit struct {
        ValuePos token.Pos   // literal position
        Kind     token.Token // token.INT, token.FLOAT, token.IMAG, token.CHAR, or token.STRING
        Value    string      // literal string; e.g. 42, 0x7f, 3.14, 1e-9, 2.4i, 'a', '\x7f', "foo" or `\m\n\o`
    }

其实简直是一样的，包含咱们后边会提到的其它的各种面值的构造体或申明的构造体，在 Go 编译器中和 Go 规范库中构造都不一样，然而含意都差不多

晓得了根底面值的构造，如果咱们想构建一个根底面值，就能够这样

func AstBasicLit()  {
    var basicLit = &ast.BasicLit{
        Kind:  token.INT,
        Value: "666",
    }
    ast.Print(nil, basicLit)
}

// 打印后果
*ast.BasicLit {
        ValuePos: 0
    Kind: INT
    Value: "666"
}

上边就是间接构建了一个根底面值，实践上咱们能够依照这种形式结构一个实现的语法树，然而手工的形式毕竟太麻烦。所以规范库中提供了办法来主动的构建语法树。假如我要将整数 666 构建成根底面值的构造

func AstBasicLitCreat()  {expr, _ := parser.ParseExpr(`666`)
    ast.Print(nil, expr)
}

// 打印后果
*ast.BasicLit {
        ValuePos: 1
    Kind: INT
    Value: "666"
}

再比方标识符面值，它的构造体为：

type Ident struct {
    NamePos token.Pos // 地位
    Name    string    // 标识符名字
    Obj     *Object   // 标识符类型或扩大信息
}

通过下边办法能够构建一个标识符类型

func AstInent()  {ast.Print(nil, ast.NewIdent(`a`))
}

// 打印后果
*ast.Ident {
        NamePos: 0
    Name: "a"
}

如果标识符是呈现在一个表达式中，就会通过 Obj 这个字段寄存标识符的额定信息

func AstInent()  {expr, _ := parser.ParseExpr(`a`)
    ast.Print(nil, expr)
}

// 打印后果
*ast.Ident {
   NamePos: 1
   Name: "a"
   Obj: *ast.Object {
      Kind: bad
      Name: ""
   }
}

ast.Object 构造中的 Kind 是形容标识符的类型

const (
    Bad ObjKind = iota // for error handling
    Pkg                // package
    Con                // constant
    Typ                // type
    Var                // variable
    Fun                // function or method
    Lbl                // label
)

表达式解析

在规范库的 go/ast/ast.go 中，你会看到各种类型的表达式的构造，我这里粘一部分看一下

// A SelectorExpr node represents an expression followed by a selector.
    SelectorExpr struct {
        X   Expr   // expression
        Sel *Ident // field selector
    }

    // An IndexExpr node represents an expression followed by an index.
    IndexExpr struct {
        X      Expr      // expression
        Lbrack token.Pos // position of "["
        Index  Expr      // index expression
        Rbrack token.Pos // position of "]"
    }

    // A SliceExpr node represents an expression followed by slice indices.
    SliceExpr struct {
        X      Expr      // expression
        Lbrack token.Pos // position of "["
        Low    Expr      // begin of slice range; or nil
        High   Expr      // end of slice range; or nil
        Max    Expr      // maximum capacity of slice; or nil
        Slice3 bool      // true if 3-index slice (2 colons present)
        Rbrack token.Pos // position of "]"
    }

在 Go 的编译器中，你也能够看到相似的表达式构造，地位在：src/cmd/compile/internal/gc/noder.go

// X.Sel
    SelectorExpr struct {
        X   Expr
        Sel *Name
        expr
    }

    // X[Index]
    IndexExpr struct {
        X     Expr
        Index Expr
        expr
    }

    // X[Index[0] : Index[1] : Index[2]]
    SliceExpr struct {
        X     Expr
        Index [3]Expr
        // Full indicates whether this is a simple or full slice expression.
        // In a valid AST, this is equivalent to Index[2] != nil.
        // TODO(mdempsky): This is only needed to report the "3-index
        // slice of string" error when Index[2] is missing.
        Full bool
        expr
    }

尽管构造体定义的不一样，然而表白的含意是差不多的。在规范库中提供了很多解析各种表达式的办法

type BadExpr struct{...}
type BinaryExpr struct{...}
type CallExpr struct{...}
type Expr interface{...}
type ExprStmt struct{...}
type IndexExpr struct{...}
type KeyValueExpr struct{...}
......

而在 Go 编译器中，解析表达式的外围办法是：src/cmd/compile/internal/gc/noder.go→expr()

func (p *noder) expr(expr syntax.Expr) *Node {p.setlineno(expr)
    switch expr := expr.(type) {
    case nil, *syntax.BadExpr:
        return nil
    case *syntax.Name:
        return p.mkname(expr)
    case *syntax.BasicLit:
        n := nodlit(p.basicLit(expr))
        n.SetDiag(expr.Bad) // avoid follow-on errors if there was a syntax error
        return n
    case *syntax.CompositeLit:
        n := p.nod(expr, OCOMPLIT, nil, nil)
        if expr.Type != nil {n.Right = p.expr(expr.Type)
        }
        l := p.exprs(expr.ElemList)
        for i, e := range l {l[i] = p.wrapname(expr.ElemList[i], e)
        }
        n.List.Set(l)
        lineno = p.makeXPos(expr.Rbrace)
        return n
    case *syntax.KeyValueExpr:
        // use position of expr.Key rather than of expr (which has position of ':')
        return p.nod(expr.Key, OKEY, p.expr(expr.Key), p.wrapname(expr.Value, p.expr(expr.Value)))
    case *syntax.FuncLit:
        return p.funcLit(expr)
    case *syntax.ParenExpr:
        return p.nod(expr, OPAREN, p.expr(expr.X), nil)
    case *syntax.SelectorExpr:
        // parser.new_dotname
        obj := p.expr(expr.X)
        if obj.Op == OPACK {obj.Name.SetUsed(true)
            return importName(obj.Name.Pkg.Lookup(expr.Sel.Value))
        }
        n := nodSym(OXDOT, obj, p.name(expr.Sel))
        n.Pos = p.pos(expr) // lineno may have been changed by p.expr(expr.X)
        return n
    case *syntax.IndexExpr:
        return p.nod(expr, OINDEX, p.expr(expr.X), p.expr(expr.Index))
    
    ......
    }
    panic("unhandled Expr")
}

下边还是用 Go 规范库中提供的办法来看一个二元表达式解析进去之后长啥样

func AstBasicExpr()  {expr, _ := parser.ParseExpr(`6+7*8`)
    ast.Print(nil, expr)
}

首先二元表达式的构造体是BinaryExpr

// A BinaryExpr node represents a binary expression.
    BinaryExpr struct {
        X     Expr        // left operand
        OpPos token.Pos   // position of Op
        Op    token.Token // operator
        Y     Expr        // right operand
    }

当被解析成这样的构造之后，就能够依据 Op 的类型来创立不同的节点。在前边提到，每一个 Op 都有本人的语义

表达式求值

假如要对上边的那个二元表达式进行求值

func AstBasicExpr()  {expr, _ := parser.ParseExpr(`6+7*8`)
    fmt.Println(Eval(expr))
}

func Eval(exp ast.Expr) float64 {switch exp := exp.(type) {
    case *ast.BinaryExpr: // 如果是二元表达式类型，调用 EvalBinaryExpr 进行解析
        return EvalBinaryExpr(exp)
    case *ast.BasicLit: // 如果是根底面值类型
        f, _ := strconv.ParseFloat(exp.Value, 64)
        return f
    }
    return 0
}

func EvalBinaryExpr(exp *ast.BinaryExpr) float64 { // 这里仅实现了 + 和 *
    switch exp.Op {
    case token.ADD:
        return Eval(exp.X) + Eval(exp.Y)
    case token.MUL:
        return Eval(exp.X) * Eval(exp.Y)
    }
    return 0
}

// 打印后果
62

次要的中央加了正文，应该是很容易看明确

Var 申明解析

首先须要阐明的是，在上一篇 Go 语法解析中咱们晓得，对于 Var 类型的申明，会解析到 VarDecl 构造体中。然而在 Go 规范库中，语法解析将 Var、const、type、import 申明都解析到 GenDecl 这个构造体中（叫通用申明）

//    token.IMPORT  *ImportSpec
    //    token.CONST   *ValueSpec
    //    token.TYPE    *TypeSpec
    //    token.VAR     *ValueSpec
    //
    GenDecl struct {
        Doc    *CommentGroup // associated documentation; or nil
        TokPos token.Pos     // position of Tok
        Tok    token.Token   // IMPORT, CONST, TYPE, VAR
        Lparen token.Pos     // position of '(', if any
        Specs  []Spec
        Rparen token.Pos // position of ')', if any
    }

能够通过 Tok 字段来辨别是哪种类型的申明

下边通过一个示例展现 Var 申明被语法解析之后的样子

const srcVar = `package test
var a = 6+7*8
`

func AstVar()  {fset := token.NewFileSet()
    f, err := parser.ParseFile(fset, "hello.go", srcVar, parser.AllErrors)
    if err != nil {log.Fatal(err)
    }
    for _, decl := range f.Decls {if v, ok := decl.(*ast.GenDecl); ok {fmt.Printf("Tok: %v\n", v.Tok)
            for _, spec := range v.Specs {ast.Print(nil, spec)
            }
        }
    }
}

首先能够看到它的 Tok 是 Var，示意他是 Var 类型的申明，而后它的变量名通过 ast.ValueSpec 构造体寄存的，其实就能够了解成 Go 编译器中的 VarDecl 构造体

到这里就应该大抵理解了根底面值、表达式、var 申明，通过语法解析之后是什么样子。前边的概览中提到，形象语法树阶段会将 Go 源文件中的各种申明，转换成一个一个的形象语法树 ，即 import、var、type、const、func 申明都会成为一个 根节点，根节点下边蕴含以后申明的子节点。下边就以 var 申明为例，看一下它是如何进行解决的

形象语法树构建

每种申明的形象语法树构建过程的思路差不多，里边的代码比较复杂，就不一行一行的代码去解释它们在做什么了，大家能够本人去看：src/cmd/compile/internal/gc/noder.go →decls()办法的外部实现

我这里仅以 Var 申明的语句为例，来展现一下在形象语法树构建阶段是如何解决 var 申明的

Var 申明语句的形象语法树构建

在前边曾经提到，形象语法树构建的外围逻辑在：src/cmd/compile/internal/gc/noder.go →decls，当申明类型为 *syntax.VarDecl 时，调用 p.varDecl(decl)办法进行解决

func (p *noder) decls(decls []syntax.Decl) (l []*Node) {
    var cs constState

    for _, decl := range decls {p.setlineno(decl)
        switch decl := decl.(type) {
        ......
        case *syntax.VarDecl:
            l = append(l, p.varDecl(decl)...)
        ......
        default:
            panic("unhandled Decl")
        }
    }

    return
}

下边间接看 p.varDecl(decl) 的外部实现

func (p *noder) varDecl(decl *syntax.VarDecl) []*Node {names := p.declNames(decl.NameList) // 解决变量名
    typ := p.typeExprOrNil(decl.Type) // 解决变量类型

    var exprs []*Node
    if decl.Values != nil {exprs = p.exprList(decl.Values) // 解决值
    }
    ......
    return variter(names, typ, exprs)
}

我将该办法中调用的几个外围办法展现进去了，办法调用的都比拟深，我下边会通过图的形式来展现每个办法里边都做了些什么事件

能够先回顾一下保留 var 申明的构造体长什么样

// NameList Type
    // NameList Type = Values
    // NameList      = Values
    VarDecl struct {
        Group    *Group // nil means not part of a group
        Pragma   Pragma
        NameList []*Name
        Type     Expr // nil means no type
        Values   Expr // nil means no values
        decl
    }

外围字段就是 NameList、Type、Values，咱们能够发现在上边的解决办法中，别离调用了三个办法来解决这三个字段

  1. names := p.declNames(decl.NameList)，该办法就是 将所有的变量名都转换成相应的 Node 构造，Node 构造的字段在前边曾经介绍过了，里边外围的字段就是Op，该办法会给每个 Name 的 Op 赋值为 ONAME。所以该办法最终返回的是一个Node 数组，里边是 var 申明的所有变量名
  2. p.typeExprOrNil(decl.Type)，该办法是 将一个具体的类型转换成相应的 Node 构造 （比方 int、string、slice 等，var a int）。该办法次要是调用expr(expr syntax.Expr) 办法来实现的，它的核心作用就是将指定类型转换成相应的 Node 构造（里边就是一堆 switch case）
  3. p.exprList(decl.Values)，该办法就是 将值局部转换成相应的 Node 构造，外围也是依据值的类型去匹配相应的办法进行解析
  4. variter(names, typ, exprs)，它其实就是将 var 申明的变量名局部、类型局部、值或表达式局部的 Node 或 Node 数组拼接成一颗树

前三个办法，就是将 var 申明的每局部转换成相应的 Node 节点，其实就是设置这个节点的 Op 属性，每一个 Op 就代表一个语义。而后第四个办法就是，依据语义将这些节点拼接成一棵树，使它能非法的表白 var 申明

下边通过一个示例来展现一下 var 申明的形象语法树构建

示例展现 var 申明的形象语法树

假如有下边这样一个 var 申明的表达式，我先通过规范库中提供的语法解析办法，展现它解析后的样子，而后再展现将该后果构建成形象语法树之后的样子

const srcVar = `package test
var a = 666+6
`
func AstVar()  {fset := token.NewFileSet()
    f, err := parser.ParseFile(fset, "hello.go", srcVar, parser.AllErrors)
    if err != nil {log.Fatal(err)
    }
    for _, decl := range f.Decls {if v, ok := decl.(*ast.GenDecl); ok {fmt.Printf("Tok: %v\n", v.Tok)
            for _, spec := range v.Specs {ast.Print(nil, spec)
            }
        }
    }
}

上边是语法分析之后的后果，而后是调用上边提到的那三个办法，将 Names、Type、Values 转换成 Node 构造如下：

Names:
ONAME(a)

Values:
OLITERAL(666)
OADD(+)
OLITERAL(6)

再通过 variter(names, typ, exprs)办法将这些 Node 构建成一棵树如下：

你能够通过下边形式去查看任何代码的语法解析后果：

const src = ` 你的代码 `
func Parser()  {fset := token.NewFileSet() // positions are relative to fset
    f, err := parser.ParseFile(fset, "", src, 0)
    if err != nil {panic(err)
    }

    // Print the AST.
    ast.Print(fset, f)
}

总结

本文先是从整体上意识了一下形象语法树做了什么？以及它的作用是什么？源文件中的申明被构建成形象语法树之后长什么样子？

而后通过规范库中提供的语法解析的办法，展现了根底面值、表达式、Var 申明语句被解析之后的样子，而后以 Var 申明类型为例，展现了形象语法树构建阶段是如何解决 Var 申明语句的

不论是在词法剖析、语法分析、形象语法树构建阶段还是后边要分享的类型查看等等，他们的实现必然有很多的细节，这些细节没法在这里一一出现，本系列文章能够帮忙小伙伴提供一个清晰的轮廓，大家能够依照这个轮廓去看细节。比方哪些 var 申明的应用是正当的、import 有哪些写法，你都能够在 Go 编译的底层实现中看到

参考

  • 《编译原理》
  • 《Go 语言底层原理分析》
  • go-ast-book
退出移动版