前言
在上一篇语法分析中，咱们晓得了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，咱们能够发现在上边的解决办法中，别离调用了三个办法来解决这三个字段
- names := p.declNames(decl.NameList)，该办法就是将所有的变量名都转换成相应的Node构造，Node构造的字段在前边曾经介绍过了，里边外围的字段就是Op，该办法会给每个Name的Op赋值为ONAME。所以该办法最终返回的是一个Node数组，里边是var申明的所有变量名
- p.typeExprOrNil(decl.Type)，该办法是将一个具体的类型转换成相应的Node构造（比方int、string、slice等，var a int ）。该办法次要是调用
expr(expr syntax.Expr)办法来实现的，它的核心作用就是将指定类型转换成相应的Node构造（里边就是一堆switch case） - p.exprList(decl.Values)，该办法就是将值局部转换成相应的Node构造，外围也是依据值的类型去匹配相应的办法进行解析
- 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
发表回复