3B.4 构造语法树

3.4.1 解析入口

当调用 go build a.go b.go 这个命令时，go 最终会调用对应平台的编译器来对源文件进行编译，所传入的参数 a.go b.go 也会最为参数传递给编译器，并最终在编译主函数中作为参数传给语法分析的入口函数 LoadPackage ，该函数会完成语法解析与类型检查，我们在这里只关心语法解析的部分。去掉不重要的部分，其主要代码为：

func LoadPackage(filenames []string) {
    mode := syntax.CheckBranches
    if base.Flag.G != 0 {
        mode |= syntax.AllowGenerics // 如果给编译器传递了 -G 这个参数，则可接受泛型语法。通过 go build -gcflags "-G=3" 来传递
    }

    // Limit the number of simultaneously open files.
    sem := make(chan struct{}, runtime.GOMAXPROCS(0)+10) // 控制解析的并发数量

    noders := make([]*noder, len(filenames))
    for i, filename := range filenames {
        p := noder{
            err:         make(chan syntax.Error),
            trackScopes: base.Flag.Dwarf,
        }
        noders[i] = &p

        filename := filename
        go func() {
            sem <- struct{}{}
            defer func() { <-sem }()
            defer close(p.err) // 关闭 error channel
            fbase := 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(fbase, f, p.error, p.pragma, mode) // 语法解析入口
        }()
    }

    var lines uint
    for _, p := range noders {
        for e := range p.err { // 错误检查，p.err 是 channel, 只有当该文件解析完成后才会关闭，所以这里也实现了对上面异步、并发解析文件的同步
            p.errorAt(e.Pos, "%s", e.Msg)
        }
        if p.file == nil {
            base.ErrorExit()
        }
        lines += p.file.EOF.Line()
    }
    base.Timer.AddEvent(int64(lines), "lines")

    // 忽略后续类型检查的代码
}

该函数是语法分析的主函数，在第一个 for 循环中并发地解析各个源文件，代码 p.file, _ = syntax.Parse(base, f, p.error, p.pragma, syntax.CheckBranches) 便是解析逻辑的入口， syntax.Parse 的返回结果便是对应源文件的语法树。

3.4.2 初始化

在 parser.go 中，解析器 parser 的定义如下：

type parser struct {
    file    *PosBase
    errh    ErrorHandler // 错误处理函数
    mode    Mode
    pragh   PragmaHandler // 负责从注释中提取编译指令
    scanner               // 词法解析器

    base   *PosBase // current position base
    first  error    // first error encountered
    errcnt int      // number of errors encountered
    pragma Pragma   // pragmas

    fnest  int    // function nesting level (for error handling)
    xnest  int    // expression nesting level (for complit ambiguity resolution)
    indent []byte // tracing support
}

我们无需关心每个字段的意义，最重要的是负责词法解析的 scanner 是 parser 的内嵌字段，Go 的词法解析是在语法分析的驱动下完成的，所以词法分析器也是语法解析器的一部分。语法解析器在构建语法树的过程中需要记录每个程序结构的位置信息，以便生成错误信息或者调试信息，所以也有对应的字段。

parser 的初始化在文件 syntax.go 中，其代码如下：

func Parse(base *PosBase, src io.Reader, errh ErrorHandler, pragh PragmaHandler, mode Mode) (_ *File, first error) {
    defer func() {
        if p := recover(); p != nil {
            if err, ok := p.(Error); ok {
                first = err
                return
            }
            panic(p)
        }
    }()

    var p parser
    p.init(base, src, errh, pragh, mode)
    p.next()
    return p.fileOrNil(), p.first
}

忽略其中的 defer 函数，该代码通过 parser 的 init 完成初始化，然后通过函数 fileOrNil 完成语法解析。

3.4.3 解析过程

文件 parser.go 有两千多行代码，我们不需要逐行分析，甚至不需要浏览遍历每个函数，只需要对所有函数大致分类，再梳理一下核心逻辑即可。后续我们会通过一些典型的场景来对解析器进行测试。

parser 的方法主要可以分为如下几类：

词法处理的辅助方法
1. want: 判断下一个 Token 是否是指定的 Token
2. advance: 从当前位置开始，跳过指定 Token 之前的所有 Token
3. list: 解析通过指定分隔符分隔开来的多个相同类型的结构，所以该方法名叫 list, 其实就是解析出某个结构体的 list, 这个 list 通常被括号或者花括号括起来。例如方法 structType:
  // StructType = "struct" "{" { FieldDecl ";" } "}" . func (p *parser) structType() *StructType { if trace { defer p.trace("structType")() } typ := new(StructType) typ.pos = p.pos() p.want(_Struct) p.want(_Lbrace) p.list(_Semi, _Rbrace, func() bool { p.fieldDecl(typ) // 解析 struct 中的每一个 field 声明 return false }) return typ }
  其中调用 list 方法就是依次解析 struct 中的每一个字段. struct 使用花括号来界定代码块，所以结束符号是 _Rbrace. Go 语言在行末会自动插入一个分号，这在词法分析时讨论过，所以此处的分隔符是 _Semi, 可知如果想要在一行定义多个字段，就需要使用分号进行分隔。
程序结构的解析方法在上文“数据结构”中讨论过的每个结构，几乎都有与之对应的解析方法，这些方法是真正的解析逻辑。
错误处理 errorAt, syntaxErrorAt 等，其会详细描述错误原因、错误位置等信息，并最终调用 parser 中的错误处理函数进行处理。

解析的主控方法是 fileOrNil, 其代码如下：

// SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .
func (p *parser) fileOrNil() *File {
    if trace {
        defer p.trace("file")()
    }

    f := new(File)
    f.pos = p.pos()

    // PackageClause
    if !p.got(_Package) {
        p.syntaxError("package statement must be first")
        return nil
    }
    f.Pragma = p.takePragma()
    f.PkgName = p.name()
    p.want(_Semi)

    // don't bother continuing if package clause has errors
    if p.first != nil {
        return nil
    }

    // { ImportDecl ";" }
    for p.got(_Import) {
        f.DeclList = p.appendGroup(f.DeclList, p.importDecl)
        p.want(_Semi)
    }

    // { TopLevelDecl ";" }
    for p.tok != _EOF {
        switch p.tok {
        case _Const:
            p.next()
            f.DeclList = p.appendGroup(f.DeclList, p.constDecl)

        case _Type:
            p.next()
            f.DeclList = p.appendGroup(f.DeclList, p.typeDecl)

        case _Var:
            p.next()
            f.DeclList = p.appendGroup(f.DeclList, p.varDecl)

        case _Func:
            p.next()
            if d := p.funcDeclOrNil(); d != nil {
                f.DeclList = append(f.DeclList, d)
            }

        default:
            if p.tok == _Lbrace && len(f.DeclList) > 0 && isEmptyFuncDecl(f.DeclList[len(f.DeclList)-1]) {
                // opening { of function declaration on next line
                p.syntaxError("unexpected semicolon or newline before {")
            } else {
                p.syntaxError("non-declaration statement outside function body")
            }
            p.advance(_Const, _Type, _Var, _Func)
            continue
        }

        // Reset p.pragma BEFORE advancing to the next token (consuming ';')
        // since comments before may set pragmas for the next function decl.
        p.clearPragma()

        if p.tok != _EOF && !p.got(_Semi) {
            p.syntaxError("after top level declaration")
            p.advance(_Const, _Type, _Var, _Func)
        }
    }
    // p.tok == _EOF

    p.clearPragma()
    f.EOF = p.pos()

    return f
}

该方法的解析逻辑分为三部分：

解析 package
通过一个 for 循环解析 import 声明
通过 for 循环内部解析顶级声明，包括常量、类型、变量、函数，每次循环通过当前 Token 来进行区分具体类型。 appendGroup 函数会对声明做分组处理，即被 () 括起来的一组声明会指向同一个 Group 实例。

每个解析方法内部都会根据当前 Token 来判断接下来应该解析何种结构，我们来看一下如何解析函数声明的：

// FunctionDecl = "func" FunctionName [ TypeParams ] ( Function | Signature ) .
// FunctionName = identifier .
// Function     = Signature FunctionBody .
// MethodDecl   = "func" Receiver MethodName ( Function | Signature ) .
// Receiver     = Parameters .
func (p *parser) funcDeclOrNil() *FuncDecl {
    if trace {
        defer p.trace("funcDecl")()
    }

    f := new(FuncDecl)
    f.pos = p.pos()
    f.Pragma = p.takePragma()

    if p.got(_Lparen) {
        rcvr := p.paramList(nil, _Rparen, false)
        switch len(rcvr) {
        case 0:
            p.error("method has no receiver")
        default:
            p.error("method has multiple receivers")
            fallthrough
        case 1:
            f.Recv = rcvr[0]
        }
    }

    if p.tok != _Name {
        p.syntaxError("expecting name or (")
        p.advance(_Lbrace, _Semi)
        return nil
    }

    f.Name = p.name()
    if p.mode&AllowGenerics != 0 && p.got(_Lbrack) {
        if p.tok == _Rbrack {
            p.syntaxError("empty type parameter list")
            p.next()
        } else {
            f.TParamList = p.paramList(nil, _Rbrack, true)
        }
    }
    f.Type = p.funcType()
    if p.tok == _Lbrace {
        f.Body = p.funcBody()
    }

    return f
}

其解析流程为：

获取编译指令（Pragma）因为编译指令在函数声明之前的注释中，执行到此时已经完成了解析
当前词法解析器在 func 这个 Token 后面，如果当前遇到的是括号，那么说明这是一个方法声明，首先解析方法的 receiver
解析函数名
如果编译器开启了泛型支持（-G），并且下一个 Token 是 [, 则说明该函数包含类型参数，对其进行解析
解析函数类型：参数与返回列表封装到了一个表达式里面，称之为函数类型：
```
    type FuncType struct {
        ParamList  []*Field
        ResultList []*Field
        expr
    }
```
这样可以与形如 type F func(int) int 的类型声明共用数据结构
解析完函数类型之后，如果此时 Token 是 { , 那么说明该函数有函数体，将其解析为 BlockStmt 语句。到此对函数声明的解析结束

在任何一步如果当前 Token 与期望的 Token 不一致，则说明出现了语法错误；否则该函数继续调用对应的解析函数完成解析，这种调用会一直递归下去，直到解析器遇到最基础的语句或者表达式为止。

本章开头处我们提到 Golang 采用的是递归下降的方式来进行语法解析，到此就可以体会到了，递归下降解析的优点是解析代码的结构与程序语法的结构几乎一致，这样的解析逻辑更加便于理解。

如果源文件没有语法错误的话，那么最终 fileOrNil 返回的结果 *File 就是该文件的 AST

上一页3B.3 数据结构下一页3B.5 Unit Test及AST可视化

最后更新于3年前