go-parser-语法分析

yueyue.gao · · 13308 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

每一种语言都会有一个定义良好的语法结构.函数是由申明和语句构成的,而语句又是由表达式构成的.
经常用来描述语法的是BNF[1].Go使用的是相应的变种,在Go的官方文档中有很详细的spec描述[2].一门语言的设计其实就在这份描述当中,这是一门语言的语法和规则的定义,是表面程序员可以接触到的部分,而运行时却可以改变,这相当于和程序员约定的接口,只要按照这个接口编写源代码,就能产生正常可以编译的二进制文件,但是最后的二进制文件如何运行,对于每条语法转换成了什么,有什么优化都是编译器优化和运行时的工作.所以一门语言必须有一个详尽的描述,这和一个网络协议一样,是非常重要的部分.

语法分析器也是有工具可以自动生成的,比如yacc[3].我在之前提到过使用工具的利弊,就不赘述了.

本文主要看一下Go的语法分析是如何进行.Go的parser接受的输入是源文件,内嵌了一个scanner,最后把scanner生成的token变成一颗抽象语法树(AST).
编译时的错误也是在这个时候报告的,但是大部分编译器编译时的错误系统并不是很完美,有时候报的错误文不对题,这主要是因为写对的方式有几种
但是写错的方式有很多种,编译器只能把一些错误进行归类,并且指出当前认为可疑的地方,并不能完完全全的知道到底是什么语法错误.这个需要结合给出的错误进行判断,clang作为一个C编译器做得好很多,这都是开发者不断地添加错误处理的结果,比gcc的报错完善很多.然而Go的编译时的错误处理也是秉承了gcc的风格,并不明确,但是会指出可疑的地方,在大多数场景下或者对语言标准熟悉的情况下也不是很麻烦.
下面看一下Go是怎么定义这些语法结构.这些结构都在go/ast当中.

// All node types implement the Node interface. type Node interface { Pos() token.Pos // position of first character belonging to the node End() token.Pos // position of first character immediately after the node } // All expression nodes implement the Expr interface. type Expr interface { Node exprNode() } // All statement nodes implement the Stmt interface. type Stmt interface { Node stmtNode() } // All declaration nodes implement the Decl interface. type Decl interface { Node declNode() }

语法有三个主体,表达式(expression),语句(statement),声明(declaration),Node是基类,用于标记该节点的位置的开始和结束.
而三个主体的函数没有实际意义,只是用三个interface来划分不同的语法单位,如果某个语法是Stmt的话,就实现一个空的stmtNode函数即可.
这样的好处是可以对语法单元进行comma,ok来判断类型,并且保证只有这些变量可以赋值给对应的interface.但是实际上这个划分不是很严格,比如

func (*ArrayType) exprNode() {} func (*StructType) exprNode() {} func (*FuncType) exprNode() {} func (*InterfaceType) exprNode() {}

就是类型,但是属于Expr,而真正的表达式比如

func (*BasicLit) exprNode() {} func (*FuncLit) exprNode() {}

是可以赋值给Exprt的.

了解了这个设计,再来看整个内容其实就是定义了源文件中可能出现的语法结构.列表如下,这个列表很长,扫一眼就可以,具体可以再回来看.

普通Node,不是特定语法结构,属于某个语法结构的一部分.
- Comment 表示一行注释 // 或者 / /
- CommentGroup 表示多行注释
- Field 表示结构体中的一个定义或者变量,或者函数签名当中的参数或者返回值
- FieldList 表示以”{}”或者”()”包围的Filed列表
Expression & Types (都划分成Expr接口)
- BadExpr 用来表示错误表达式的占位符
- Ident 比如报名,函数名,变量名
- Ellipsis 省略号表达式,比如参数列表的最后一个可以写成arg...
- BasicLit 基本字面值,数字或者字符串
- FuncLit 函数定义
- CompositeLit 构造类型,比如{1,2,3,4}
- ParenExpr 括号表达式,被括号包裹的表达式
- SelectorExpr 选择结构,类似于a.b的结构
- IndexExpr 下标结构,类似这样的结构 expr[expr]
- SliceExpr 切片表达式,类似这样 expr[low:mid:high]
- TypeAssertExpr 类型断言类似于 X.(type)
- CallExpr 调用类型,类似于 expr()
- StarExpr 表达式,类似于 X
- UnaryExpr 一元表达式
- BinaryExpr 二元表达式
- KeyValueExp 键值表达式 key:value
- ArrayType 数组类型
- StructType 结构体类型
- FuncType 函数类型
- InterfaceType 接口类型
- MapType map类型
- ChanType 管道类型
Statements
- BadStmt 错误的语句
- DeclStmt 在语句列表里的申明
- EmptyStmt 空语句
- LabeledStmt 标签语句类似于 indent:stmt
- ExprStmt 包含单独的表达式语句
- SendStmt chan发送语句
- IncDecStmt 自增或者自减语句
- AssignStmt 赋值语句
- GoStmt Go语句
- DeferStmt 延迟语句
- ReturnStmt return 语句
- BranchStmt 分支语句例如break continue
- BlockStmt 块语句 {} 包裹
- IfStmt If 语句
- CaseClause case 语句
- SwitchStmt switch 语句
- TypeSwitchStmt 类型switch 语句 switch x:=y.(type)
- CommClause 发送或者接受的case语句,类似于 case x <-:
- SelectStmt select 语句
- ForStmt for 语句
- RangeStmt range 语句
Declarations
- Spec type
  - Import Spec
  - Value Spec
  - Type Spec
- BadDecl 错误申明
- GenDecl 一般申明(和Spec相关,比如 import “a”,var a,type a)
- FuncDecl 函数申明
Files and Packages
- File 代表一个源文件节点,包含了顶级元素.
- Package 代表一个包,包含了很多文件.

上面就是整个源代码的所有组成元素,接下来就来看一下语法分析是如何进行的,也就是最后的AST是如何构建出来的.

先看一下parser结构体的定义,parser是以file为单位的.

// The parser structure holds the parser's internal state. type parser struct { file *token.File errors scanner.ErrorList // 解析过程中遇到的错误列表 scanner scanner.Scanner // 词法分析器. // Tracing/debugging mode Mode // parsing mode // 解析模式 trace bool // == (mode & Trace != 0) indent int // indentation used for tracing output // Comments 列表 comments []*ast.CommentGroup leadComment *ast.CommentGroup // last lead comment lineComment *ast.CommentGroup // last line comment // Next token pos token.Pos // token position tok token.Token // one token look-ahead lit string // token literal // Error recovery // (used to limit the number of calls to syncXXX functions // w/o making scanning progress - avoids potential endless // loops across multiple parser functions during error recovery) syncPos token.Pos // last synchronization position 解析错误的同步点. syncCnt int // number of calls to syncXXX without progress // Non-syntactic parser control // 非语法性的控制 // <0 在控制语句中, >= 在表达式中. exprLev int // < 0: in control clause, >= 0: in expression // 正在解析右值表达式 inRhs bool // if set, the parser is parsing a rhs expression // Ordinary identifier scopes pkgScope *ast.Scope // pkgScope.Outer == nil topScope *ast.Scope // top-most scope; may be pkgScope unresolved []*ast.Ident // unresolved identifiers imports []*ast.ImportSpec // list of imports // Label scopes // (maintained by open/close LabelScope) labelScope *ast.Scope // label scope for current function targetStack [][]*ast.Ident // stack of unresolved labels }

解析的入口是ParseFile,首先调用init,再调用parseFile进行解析.
整个解析是一个递归向下的过程也就是最low但是最实用的手写实现的方式.像yacc[4]生成的是我们编译里学的LALR[5]文法,牛逼的一逼,但是
gcc和Go都没用自动生成的解析器,也就是手写个几千行代码的事,所以为了更好的掌握编译器的细节,都选择了手写最简单的递归向下的方式.

通过init初始化scanner等.

func (p *parser) init(fset *token.FileSet, filename string, src []byte, mode Mode) { p.file = fset.AddFile(filename, -1, len(src)) var m scanner.Mode if mode&ParseComments != 0 { m = scanner.ScanComments } // 错误处理函数是在错误列表中添加错误. eh := func(pos token.Position, msg string) { p.errors.Add(pos, msg) } p.scanner.Init(p.file, src, eh, m) p.mode = mode p.trace = mode&Trace != 0 // for convenience (p.trace is used frequently) p.next() }

parseFile的简化流程:

 // package clause // 获取源文件开头的doc注释,从这里递归向下的解析开始了 doc := p.leadComment // expect 从scanner获取一个token,并且返回位置pos. pos := p.expect(token.PACKAGE) // parseIdent 获取一个token并且转化为indent,如果不是报错. ident := p.parseIdent() if ident.Name == "_" && p.mode&DeclarationErrors != 0 { p.error(p.pos, "invalid package name _") } // 作用域开始,标记解释器当前开始一个新的作用域 p.openScope() // pkgScope 就是现在进入的作用域 p.pkgScope = p.topScope // 解析 import 申明 for p.tok == token.IMPORT { // parseGenDecl解析的是 // import ( // ) // 这样的结构,如果有括号就用parseImportSpec解析列表 // 没有就单独解析. // 而parseImportSpec解析的是 一个可选的indent token和一个字符串token. // 并且加入到imports列表中. decls = append(decls, p.parseGenDecl(token.IMPORT, p.parseImportSpec)) } // 解析全局的申明,包括函数申明 if p.mode&ImportsOnly == 0 { // rest of package body for p.tok != token.EOF { decls = append(decls, p.parseDecl(syncDecl)) } } // 标记从当前作用域离开. p.closeScope() // 最后返回ast.File文件对象. return &ast.File{ Doc: doc, Package: pos, Name: ident, Decls: decls, Scope: p.pkgScope, Imports: p.imports, Unresolved: p.unresolved[0:i], Comments: p.comments, }

看一下parseDecl主要是根据类型的不同调用不同的解析函数,parseValueSpec解析Value类型,parseTypeSpec解析Type类型,parseFuncDecl解析函数.
解析定义和解析类型的都是解析了,类似于var|type ( ident valueSpec|typeSpec)的token结构.因为parseFuncDecl里面也会解析这些内容,所以直接从函数解析来看也可以.
因为外一层的top scope其实就是相当于一个抽象的函数作用域而已,这样是为什么len和new这样的内嵌函数在函数内是可以做变量名的原因,因为可以在子作用域覆盖top作用域.整个解析过程简化过程如下.

 // 解析一个func. pos := p.expect(token.FUNC) // 开一个新的作用域,topScope作为父Scope. scope := ast.NewScope(p.topScope) // function scope // 解析一个ident作为函数名 ident := p.parseIdent() // 解析函数签名,也就是参数和返回值 params, results := p.parseSignature(scope) // 再解析body body = p.parseBody(scope) // 最后返回函数申明. decl := &ast.FuncDecl{ Doc: doc, Recv: recv, Name: ident, Type: &ast.FuncType{ Func: pos, Params: params, Results: results, }, Body: body, }

解析参数和返回值就是解析(filed,filed)这样的格式,每个filed是indent type的token,最后构造成函数签名.然后来到parseBody,这个函数其实就是解析了左右花括号,然后向下开始解析Statement列表,类似于body -> { stmt_list },然后进入stmt_list的解析,不断地解析statement.

 for p.tok != token.CASE && p.tok != token.DEFAULT && p.tok != token.RBRACE && p.tok != token.EOF { list = append(list, p.parseStmt()) }

parseStmt最后会进入到语句的解析,然后根据不同的token选择进入不同的解析流程,比如看到var,type,const就是申明,碰到标识符和数字等等可能就是单独的表达式,
如果碰到go,就知道是一个go语句,如果看到defer和return都能判断出相应的语句并按规则解析,看到break等条件关键字就解析条件语句,看到{就解析块语句.都是可以递归去解析的.

func (p *parser) parseStmt() (s ast.Stmt) { if p.trace { defer un(trace(p, "Statement")) } switch p.tok { case token.CONST, token.TYPE, token.VAR: s = &ast.DeclStmt{Decl: p.parseDecl(syncStmt)} case // tokens that may start an expression token.IDENT, token.INT, token.FLOAT, token.IMAG, token.CHAR, token.STRING, token.FUNC, token.LPAREN, // operands token.LBRACK, token.STRUCT, token.MAP, token.CHAN, token.INTERFACE, // composite types token.ADD, token.SUB, token.MUL, token.AND, token.XOR, token.ARROW, token.NOT: // unary operators s, _ = p.parseSimpleStmt(labelOk) // because of the required look-ahead, labeled statements are // parsed by parseSimpleStmt - don't expect a semicolon after // them if _, isLabeledStmt := s.(*ast.LabeledStmt); !isLabeledStmt { p.expectSemi() } case token.GO: s = p.parseGoStmt() case token.DEFER: s = p.parseDeferStmt() case token.RETURN: s = p.parseReturnStmt() case token.BREAK, token.CONTINUE, token.GOTO, token.FALLTHROUGH: s = p.parseBranchStmt(p.tok) case token.LBRACE: s = p.parseBlockStmt() ...省略

举个例子看一下parseSimpleStmt()的简化流程

 // 解析左列表 一般是 l := r 或者 l1,l2 = r1,r2 或者 l <- r 或者 l++ x := p.parseLhsList() switch p.tok { case token.DEFINE, token.ASSIGN, token.ADD_ASSIGN, token.SUB_ASSIGN, token.MUL_ASSIGN, token.QUO_ASSIGN, token.REM_ASSIGN, token.AND_ASSIGN, token.OR_ASSIGN, token.XOR_ASSIGN, token.SHL_ASSIGN, token.SHR_ASSIGN, token.AND_NOT_ASSIGN: // 如果看到range,range作为一种运算符按照range rhs来解析 // 如果没看到就按正常赋值语句解析 lhs op rhs 来解析op可以是上面那些token中的一种. pos, tok := p.pos, p.tok p.next() var y []ast.Expr isRange := false if mode == rangeOk && p.tok == token.RANGE && (tok == token.DEFINE || tok == token.ASSIGN) { pos := p.pos p.next() y = []ast.Expr{&ast.UnaryExpr{OpPos: pos, Op: token.RANGE, X: p.parseRhs()}} isRange = true } else { y = p.parseRhsList() } as := &ast.AssignStmt{Lhs: x, TokPos: pos, Tok: tok, Rhs: y} // 碰到":"找一个ident, 构成 goto: indent 之类的语句. case token.COLON: colon := p.pos p.next() if label, isIdent := x[0].(*ast.Ident); mode == labelOk && isIdent { // Go spec: The scope of a label is the body of the function // in which it is declared and excludes the body of any nested // function. stmt := &ast.LabeledStmt{Label: label, Colon: colon, Stmt: p.parseStmt()} p.declare(stmt, nil, p.labelScope, ast.Lbl, label) return stmt, false } // 碰到"<-",就构成 <- rhs 这样的语句. case token.ARROW: // send statement arrow := p.pos p.next() y := p.parseRhs() return &ast.SendStmt{Chan: x[0], Arrow: arrow, Value: y}, false // 碰到"++"或者"--"就构成一个单独的自增语句. case token.INC, token.DEC: // increment or decrement s := &ast.IncDecStmt{X: x[0], TokPos: p.pos, Tok: p.tok} p.next() return s, false }

接下来就不一一解释每段代码了,具体情况具体看就可以.这里举个例子.

package main import ( "go/ast" "go/parser" "go/token" ) func main() { fset := token.NewFileSet() f, err := parser.ParseFile(fset, "", ` package main func main(){ // comments x:=1 go println(x) } `, parser.ParseComments) if err != nil { panic(err) } ast.Print(fset, f) }

产生的结果是

 0 *ast.File { 1 . Package: 2:1 |PACKAGE token 2 . Name: *ast.Ident { |IDENT token 3 . . NamePos: 2:9 | 4 . . Name: "main" | 5 . } |整个构成了顶部的 package main 6 . Decls: []ast.Decl (len = 1) { |最上层的申明列表 7 . . 0: *ast.FuncDecl { |func main的函数申明 8 . . . Name: *ast.Ident { |IDENT token 9 . . . . NamePos: 3:6 | 10 . . . . Name: "main" | 11 . . . . Obj: *ast.Object { |Objec是一个用于表达语法对象的结构 12 . . . . . Kind: func |表示之前存在过,Decl指向了7,也就是第7行的FuncDecl. 13 . . . . . Name: "main" | 14 . . . . . Decl: *(obj @ 7) | 15 . . . . } | 16 . . . } | 17 . . . Type: *ast.FuncType { |函数类型,也就是函数签名 18 . . . . Func: 3:1 |参数和返回值都是空的 19 . . . . Params: *ast.FieldList { | 20 . . . . . Opening: 3:10 21 . . . . . Closing: 3:11 22 . . . . } 23 . . . } 24 . . . Body: *ast.BlockStmt { |块语句,也就是main的body 25 . . . . Lbrace: 3:12 26 . . . . List: []ast.Stmt (len = 2) { |语句列表 27 . . . . . 0: *ast.AssignStmt { |赋值语句 28 . . . . . . Lhs: []ast.Expr (len = 1) { |左值是x 29 . . . . . . . 0: *ast.Ident { 30 . . . . . . . . NamePos: 5:2 | 31 . . . . . . . . Name: "x" 32 . . . . . . . . Obj: *ast.Object { | 33 . . . . . . . . . Kind: var 34 . . . . . . . . . Name: "x" | 35 . . . . . . . . . Decl: *(obj @ 27) 36 . . . . . . . . } 37 . . . . . . . } | 38 . . . . . . } 39 . . . . . . TokPos: 5:3 |:=和它的位置 40 . . . . . . Tok: := 41 . . . . . . Rhs: []ast.Expr (len = 1) { |右边是一个数字类型的token 42 . . . . . . . 0: *ast.BasicLit { 43 . . . . . . . . ValuePos: 5:5 44 . . . . . . . . Kind: INT 45 . . . . . . . . Value: "1" 46 . . . . . . . } 47 . . . . . . } 48 . . . . . } 49 . . . . . 1: *ast.GoStmt { |接下来是go语句 50 . . . . . . Go: 6:2 51 . . . . . . Call: *ast.CallExpr { |一个调用表达式 52 . . . . . . . Fun: *ast.Ident { |IDENT token是println 53 . . . . . . . . NamePos: 6:5 54 . . . . . . . . Name: "println" 55 . . . . . . . } 56 . . . . . . . Lparen: 6:12 |左括号的位置 57 . . . . . . . Args: []ast.Expr (len = 1) { |参数列表 58 . . . . . . . . 0: *ast.Ident { |是一个符号INDENT,并且指向的是32行的x 59 . . . . . . . . . NamePos: 6:13 60 . . . . . . . . . Name: "x" 61 . . . . . . . . . Obj: *(obj @ 32) 62 . . . . . . . . } 63 . . . . . . . } 64 . . . . . . . Ellipsis: - 65 . . . . . . . Rparen: 6:14 |右括号的位置 66 . . . . . . } 67 . . . . . } 68 . . . . } 69 . . . . Rbrace: 8:1 70 . . . } 71 . . } 72 . } 73 . Scope: *ast.Scope { |最顶级的作用域 74 . . Objects: map[string]*ast.Object (len = 1) { 75 . . . "main": *(obj @ 11) 76 . . } 77 . } 78 . Unresolved: []*ast.Ident (len = 1) { |这里有个没有定义的符号println,是因为是内置符号,会另外处理 79 . . 0: *(obj @ 52) |从源文件上是表现不出来的. 80 . } 81 . Comments: []*ast.CommentGroup (len = 1) { |评论列表,以及位置和内容. 82 . . 0: *ast.CommentGroup { 83 . . . List: []*ast.Comment (len = 1) { 84 . . . . 0: *ast.Comment { 85 . . . . . Slash: 4:2 86 . . . . . Text: "// comments" 87 . . . . } 88 . . . } 89 . . } 90 . } 91 }

这就是Go的整个语法分析和最后产生的语法树的结构.

废话说了这么多其实实现很简单,问题是如何把一个语言的spec定义好,很重要,早期语言设计不是很固定的.都是慢慢尝试不断改进的过程.最早的一次spec文档[6]其实和现在差了很多很多.就是把TOKEN记号流从左至右匹配规则(可能会向前看几个token),然后递归解析语法树,最后得到AST.
我在我的字符画转换器里用的也是类似的方式[7],做了自顶向下递归解析语法的方式,但是错误处理都是速错,不会做错误恢复找到一个可以同步的节点继续分析.
所以这里补充一点,Go是如何进行错误处理的同步问题,寄希望于能够向使用者提供更多的错误.主要是parser当中的两个结构

 syncPos token.Pos // last synchronization position syncCnt int // number of calls to syncXXX without progress

syncPos错误的同步位置,也就类似于游戏的存档点,如果发生错误那就从这个地方开始跳过(BadStmt|BadExpr)继续解析,在每次完成语句,申明或者表达式的解析之后就会保存一个同步点.虽然这种继续解析的行为不一定能够给出很精确的错误提示,但的确够用了.当然如果错误实在太多了,从同步点恢复也没有太大意义,就会主动放弃,所以记录了没有成功解析而同步的次数.

因为之前造过轮子了,所以我发现其实编译器的前端用手写是一个很繁琐并且需要花很多时间去做的一件事情,如果语言有设计良好,那么也至少需要花实现的时间,如果设计不好,实现也要跟着修修补补,那就更麻烦,虽然整个编译器的前端也就不到万行代码,但是的确是很考验耐心的一件事情,而且用递归向下的方式解析也没什么效率问题,编译器编译慢一点也不是很要紧,所以有轮子还是用轮子吧,这只是一件苦力活,的确没什么高科技.

最后附带一个用Go实现的Go语法的子集的动态语言版本,只有几十行.

https://gist.github.com/ggaaooppeenngg/dff0fff8f0c9194d93c70550d50edbfa

参考:

有疑问加站长微信联系（非本文作者）