Go编译器源代码：语法分析

Bioit   in Hefei

  本文快速阅读需要一点编译原理知识、Go的使用经验

  水平有限、错误请联系更改

上一篇词法分析源码阅读文章 (opens new window)

# 一、语法分析

  语法分析知识很多、这里更像是列出一个列表、供大家去按列表查资料学习

  1. 语法分析的输入即Token序列，即把若干Token组合起来形成一个Node。且Node以树形组合，形成一棵抽象语法树（AST）。经过词法分析和语法分析，每个文件都将形成一棵AST
  2. 规则表示：
  • 文法：维基百科 (opens new window)，不明白的话需要仔细阅读。后面默认是会文法基本知识的
  • 我们知道词法分析规则（词法分析字符串产生式规则）可以用正则文法很好的表示、但是语法分析显然规则更复杂。所以用上下文无关文法来表示语法规则、上下文无关文法可以包含正则文法。即它的能力比正则文法范围广
  • 上下文无关代表的意思是如果一串Token是一样的、那么无论它们处于何种位置，都会用同样的推导规则来解析，如果上下文有关的信息，就要依靠后面的语义分析
  • 书写/表示上下文无关文法：巴科斯范式和拓展巴科斯范式，拓展巴科斯范式能够使用正则。相关维基百科 (opens new window)
  1. 算法：有了规则的表达，就要根据规则写代码来解析Token序列转换成AST，语法分析算法分为2大类：自顶向下、自底向上
  • 自顶向下：代表算法有LL(0)，LL(k)，LL英文为Left-to-right Leftmost，最左推导，含义是从最左边的非终结符展开，一直如此下去。k的含义是向前看多少个Token用于避免无用的分支（一个非终结符可能有很多个推导分支）遍历和回溯，加快解析速度
    • 对于所有分支都是Token开头的话、那么很好处理。提前看一个Token来对比就可以很好判断走哪些分支。但是如果分支的开头都是非终结符的话。我们就需要计算这些分钟的First集合。当预读Token在某个First集合中时，就进入。在这里临时约定：大写字母代表非终结符，小写字母代表终结符
    • First集合：A -> 分支1 | 分支2 | 分支3
      • 分支以Token开头，这个分支First集合为这个Token
      • 分支以非终结符开头，那么这个分支的First集合就是这个非终结符的First集合
      • 对ε的处理：如果分支第一个非终结符可以为ε、则要多往后面看一个元素一起计算。如果某个分支所有元素都可以为ε、则First集合包含ε。此时需要引入Follow集合
      • A的First集合，就是它的各分支First集合的并集
    • Follow集合：对非终结符号A，Follow(A)表示A后面可能出现的Token集合，计算规则如下：
      • 开始符号S, FOLLOW(S)包含$
      • B -> aAC这种情况，Follow(A)要包含First(C) （去掉ε）。当然，如果A后面有终结符，直接加入Follow中
      • B -> aA 或者 B -> aAC C可以为ε，则Follow(A)需要包含Follow(B)
    • 例子：
// 对于以下一些产生式，求2种集合
// A是起始
A -> BC | aB
B -> -C | ε
C -> 12 | c | ε
// First集合
First(A) = First(B)去ε U First(C)去ε U ε U a = {-, 12, c, ε, a}
First(B) = - U ε = {-, ε}
First(C) = {12, c, ε}
// Follow集合
Follow(A) = {$}
Follow(B) =  First(C) U Follow(A) = {12, c, $}
Follow(C) = Follow(A) U Follow(B) = {12, c, $}
// 我们的例子很简单，没有环，如果遇到环要用不动点法多次遍历更新，直到集合稳定

  • 启示：如果我们想利用向前看方法并且配合First、Follow集合加速自顶向下分析过程，我们设计语法规则的时候要注意如果有多个分支尽量避免公共前缀。如果有公共前缀，最好提取出来。新增一条语法，这样可以避免k值很大才能确认走哪个分支

  • 自底向上：代表算法LR(k)、LALR(k)等。比自顶向下算法难实现，但是优点更多，它天生能够避免左递归（见下文）。由于Go使用的是自顶向下算法，所以这里也不过多阐述，读者这里可以去阅读拓展自底向上算法

  1. 实现自顶向下的一般步骤：自顶向下实现简单、这是它的一大优点
  • 代码看起来就像为文法中每个左侧结点（非终结结点）定义一个函数。看起来就是一条函数递归调用链，and逻辑就会有先后的调用。or逻辑就会有if-else或者switch-case代码块处理
  • 当然，我们可以利用First/Follow配合向前看减少回溯次数，加速解析
  • 比如实现如下语法规则：BC和C是or关系，第一个分支B、C是and关系
// A -> B C | C
// 大概代码逻辑
func A() (aNode ANode) {
	aNode.B = BOrNil()
	aNode.C = C()
	return
}
  1. 算法需要解决的问题：
  • 优先级问题：利用上下级关系，上级文法优先级低于下级文法。下级文法将解析为子节点，将先处理。有高优先级
add -> mul | add + mul
mul -> pri | mul * pri
  • 结合性问题：这不是自顶向下算法单独存在的问题。解决方法为左结合把递归项写在左边，右结合把递归项写在右边，如上面我们把add递归项写在了左边。如果写作add -> mul | mul + add，1 + 2 + 3将会解析为1 + （2 + 3）
  • 左递归问题：因为大部分操作符都是左结合，而把递归项写在左边会导致自顶向下算法写法出现无限递归。解决方法是改写文法、然后优化代码实现
// 如果add -> mul | add + mul不特殊处理将会有左递归
func add() (addNode AddNode) {
	addNode.X = mul()
	// 发现不是mul分支。则走add + mul分支
	if curToken == "+" {
		// 回溯并调用add()，此时此刻。我们会发现无限调用了
		rewind()
		addNode.X = add()
		// 剩余代码....
	}
	return
}
// 改写文法：add -> mul (+ mul)*
// 这样我们可以不断的尝试获取+ mul。同时注意前面的addNode要成为新的addNode的左结点。不然结合性
// 就出问题了，大致代码如下
while curToken == "+" {
	nextToken() // 消费+
	newAddNode = AddNode{}
	newAddNode.X = addNode
	newAddNode.Y = mul()
	addNode = newAddNode
}
  • 以上的几种问题大多出现在语言中表达式结点的分析中、我们手写很不方便、但是工具可以很好的帮助我们
  1. 工具实现：同样的，语法分析算法比较固定，所以也有很多工具可以帮助我们只要写出语法规则，不用代码实现。如词法分析中提到的工具antlr
expr : primaryExpr
	 | expr '*' expr
     | expr '+' expr
  • antlr处理结合问题：左结合操作符无需处理，右集合的操作符特殊指定就行
  • antlr显然也帮我们处理了左递归问题，无需我们特殊处理

# 二、Go语法分析源码解析：

  Go语言语法分析相关代码在src\cmd\compile\internal\syntax包中   阅读源码时，我们可以暂时无视错误处理和Pos（位置的结构化，携带行列等信息）处理、以及debug和trace、特殊注释（//go: // line）处理等相关逻辑。提高阅读速度   阅读语法分析源码时，一定要结合自己的使用经验验证。甚至有的允许语法也是自己从来没写过的

  1. 部分Go语法规则和AST结点的结构化：
  • 只展示部分语法规则：在parse.go文件中每个函数开头都有具体的规则表述，读者可以去查看所有产生式规则。且可以参考上文给出的antlr的Go语法分析规则文件。基本没有多大区别
// AST根结点
SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .
// 包定义
PackageClause = _Package identifier;
// 包引入规则
ImportSpec = [ "." | PackageName ] ImportPath .
ImportPath = string_lit .
// File包含的定义规则: 包括常量、变量、类型、方法、函数定义。可以结合平时写的代码验证
TopLevelDecl  = Declaration | FunctionDecl | MethodDecl .
Declaration   = ConstDecl | TypeDecl | VarDecl .
ConstSpec = IdentifierList [ [ Type ] "=" ExpressionList ] .
FunctionDecl = "func" FunctionName [ TypeParams ] ( Function | Signature ) .
MethodDecl   = "func" Receiver MethodName ( Function | Signature ) .
  • 当语法解析完成后，每个源文件将被解析为以下的结构体，这就是一颗AST，也可以理解为树的根结点
type File struct {
	Pragma   Pragma
	PkgName  *Name // 包名
	DeclList []Decl // 子节点列表。各种定义
	EOF      Pos
	node
}
  • Go中的statement：这里直接复制别人根据go语法规则总结的antlr格式的statement规则。函数、for等结构的主体中，就是由stmtList组成的
statement:
	declaration // stmt也包含常量、变量等定义
	| labeledStmt // 标签stmt。goto等语句会跳转到对应标签执行
	| simpleStmt
	| goStmt
	| returnStmt
	| breakStmt
	| continueStmt
	| gotoStmt
	| fallthroughStmt
	| block
	| ifStmt
	| switchStmt
	| selectStmt
	| forStmt
	| deferStmt;

simpleStmt:
	sendStmt
	| incDecStmt // ++ --语句。其实其和assignment、shortVarDecl共用一个类型的AST Node。根据其中属性区分
	| assignment
	| expressionStmt // 没有再细分的表达式Stmt
	| shortVarDecl;
  1. 语法分析器结构体：可以看出继承词法分析器，调用词法分析器next函数获取当前token
type parser struct {
	file    *PosBase
	// 错误处理函数，可以看到在词法分析时频繁被调用，errh如果为nil
	// 如果遇到报错 1. errh == nil 。返回第一个错误并且语法树为nil  2. errh != nill  记录第一个错误，每次遇到尝试继续执行解析，即尽最大努力
	errh    ErrorHandler 
	mode    Mode // 是否开启泛型等开关作用
	pragh   PragmaHandler // directives 处理函数，即//go:这些的处理函数
	scanner               // 继承词法分析器
	base   *PosBase // current position base
	first  error    // first error encountered  遇到的第一个错误
	// 错误计数
	errcnt int      // number of errors encountered
	pragma Pragma   // pragmas  pragh处理完后的结果
	fnest  int    // function nesting level (for error handling)
	// 表达式嵌套级别，可以看到在每次调用表达式处理相关函数时++。
	// 读者如果仔细阅读可以发现有一个位置xnest被设为-1（for if switch的头部部分表达式处理）：eg  if  a > 0 {}  这里a>0就是头部表达式
	// 如果小于0。则不允许部分复杂pexpr，如结构体的初始化等
	xnest  int    // expression nesting level (for complit ambiguity resolution)
	indent []byte // tracing support
}
  1. Go语法分析重要文件：
  • syntax.go：语法分析入口、提供了两个函数、分别是提供打开后的文件句柄或者文件名来将文件源代码转变为AST，其中也有初始化语法分析器逻辑。从中我们可以看出语法分析开始函数为fileOrNil()。syntax.go中还包含了一个Mode的type。为uint别名，其主要功能为控制泛型开关
  • pos.go：位置结构化，用于错误处理、AST结点位置信息
  • node.go：AST各类型结点结构化表示，即各个类型结点的数据结构
  • parse.go：语法分析核心文件，实现了Go的语法分析器主要逻辑，Go的语法分析采用的是自顶向下算法，并且使用提前查看Token加快分析。分析开始函数为fileOrNil()
  1. 几个需要了解的频繁使用的函数和概念：
  • got(tok token) bool：判别当前token是否是期望token。其实就是我们所说的向前看
func (p *parser) got(tok token) bool {
	if p.tok == tok {
		p.next()
		return true
	}
	return false
}
  • want(tok token)：当前token不是所期望的就报错
func (p *parser) want(tok token) {
	if !p.got(tok) {
		p.syntaxError("expecting " + tokstring(tok))
		p.advance()
	}
}
  • list(sep, close token, f func() bool) Pos：分析出以传入的sep为分割，直到close为止的相似列表。解析每个元素的函数就是传入的f。这个方法其实在写文章之前已经改动了。但是源代码更新频繁。没有大的改动的话其实没有太大关系，没有必要一直追着最新代码读
  • group:组的概念，用一个关键字声明多个元素，这些元素就属于一个组：如下这些import就属于一个组
  • OrNil结尾的函数，代表这里如果解析失败，将会返回nil
import (
	"fmt"
	"io"
	"strconv"
	"strings"
)
  1. 语法分析重要函数简析：其实自顶向下方法实现起来的函数读起来很简单。我们只需要结合语法规则来相互验证着读就可以了，语法分析有2000多行不可能全部列出来，阅读重点可以放在：fileOrNil、类型处理（typeOrNil）、表达式处理（expr）、stmt处理（ stmtOrNil）
  • fileOrNil：把一个源文件解析为一颗AST
func (p *parser) fileOrNil() *File {
	if trace {
		defer p.trace("file")()
	}

	f := new(File) // 创建AST树根
	f.pos = p.pos()

	// 1. PackageClause
	if !p.got(_Package) {
		p.syntaxError("package statement must be first")
		return nil
	}
	f.Pragma = p.takePragma()
	f.PkgName = p.name() // package packageName
	p.want(_Semi)        // 可以看出package packageName后必须有换行或者多行注释
	// 在这里总结一下token 后面的_Semi在何种情况下产生
	// (1) 源代码本身就写了 ;
	// (2) 前一个token需要 ;。紧跟着前一个token后的是跨多行的多行注释 / 换行 / 多行注释且多行注释后没内容
	// don't bother continuing if package clause has errors
	// package部分解析出了问题就没必要继续了
	if p.first != nil {
		return nil
	}

	// 2. { ImportDecl ";" }。里面出错了的话，d.Path.Bad会有记录
	for p.got(_Import) {
		f.DeclList = p.appendGroup(f.DeclList, p.importDecl)
		p.want(_Semi) // 注意语句结尾是要有 ; ps：单条语句就是引入路径后面要有，引入一组就是）后面要有
	}

	// 3. { 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
		}
		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
}
  • 这里再看看expr处理相关函数：注意Go是如何处理结合性问题、左递归问题、优先级问题的

func (p *parser) expr() Expr {
	if trace {
		defer p.trace("expr")()
	}
	// 注意这个0，其让我们可以完成对一个完整表达式的全部读取
	return p.binaryExpr(nil, 0) 
}

// Expression = UnaryExpr | Expression binary_op Expression .
// 可以看出表达式产生式规则为一元表达式或者用二元操作符连接的2个表达式
func (p *parser) binaryExpr(x Expr, prec int) Expr {
	// x != nil时代表是二元操作符的左Expr
	// x为nil时先走一元表达式分支
	if x == nil {
		x = p.unaryExpr()
	}
	// 如果有操作符、则走Expression binary_op Expression分支
	// 可以看到此时、前面解析的UnaryExpr此时就是二元操作符左边的Expression。而不是回溯重新匹配，避免了左递归问题
	// 当紧跟着的token为操作符且优先级大于当前表达式优先级，则当前表达式和后面表达式组成二元表达式，这个操作保证了优先级问题
	for (p.tok == _Operator || p.tok == _Star) && p.prec > prec {
		t := new(Operation)
		t.pos = p.pos()
		t.Op = p.op
		tprec := p.prec
		p.next() // 消费操作符
		t.X = x // 这里解决了结合性问题。如果是同级别操作符的话，之前的结点为新结点子结点
		t.Y = p.binaryExpr(nil, tprec) // 递归调用。注意优先级逻辑
		x = t
	}
	return x
}
  • 剩下的内容读者可以自行阅读，源码注释后的代码在最后有给出链接

各链接：

语法分析源码注释链接 (opens new window) Go 编程语言规范 (opens new window)，从中可以查询到语法相关知识 antlr格式Go语法规则文件在文中已给出

一、语法分析
二、Go语法分析源码解析：