Golang编译器源码分析(1)
1、Go 的编译器在逻辑上可以被分成四个阶段:词法与语法分析、类型检查和 AST 转换、通用 SSA 生成和最后的机器代码生成
<pre><code>编译前端 编译后端 ---------- | ---------- | | 词法分析 | 中间码生成 | |---------------------- | | 语法分析 | 代码优化 | |---------------------- | | 语义分析 | 机器码生成 | |--------- | ---------- | </code></pre><ol><li>词法分析生成token [scanner.next()];</li><li>语法分析生成抽象语法树AST,每一个 AST 都对应着一个单独的 Go 语言文件 [parse.decls()];</li><li>语义分析进行类型检查,优化改写ast [checktype1()];</li><li>中间码生成将抽象语法树会经过多轮处理转变成最后的拥有 静态单赋值(SSA)特性的中间码,分析出代码中的无用变量和片段并对代码进行优化;</li><li>高效代码替换低效的代码,力所能及的进行优化;</li><li>生成汇编代码(Plan9),进而生成机器码。</li></ol><h3>词法与语法分析</h3>词法分析是计算机科学中将字符序列转换为标记(token)序列的过程,词法分析就是解析源代码文件,它将文件中的字符串序列转换成Token序列,方便后面的处理和解析。
语法分析的输入就是词法分析器输出的 Token 序列,这些序列会按照顺序被语法分析器进行解析,语法分析过程就是将词法分析生成的 Token 按照语言定义好的文法(Grammar)自下而上或者自上而下的进行规约,每一个 Go 的源代码文件最终会被归纳成一个SourceFile结构。
词法分析会返回一个不包含空格、换行等字符的 Token 序列,例如:<code>package</code>, <code>import</code>, <code>(</code>, <code>io</code>, <code>)</code>, …,而语法分析会把 Token 序列转换成有意义的结构体,也就是抽象语法树(AST)。
每一个 AST 都对应着一个单独的 Go 语言文件,这个抽象语法树中包括当前文件属于的包名、定义的常量、结构体和函数等。
当拿到一组文件的抽象语法树之后,Go 语言的编译器会对语法树中定义和使用的类型进行检查,类型检查分别会按照以下的顺序对不同类型的节点进行验证和处理:
<ol><li>常量、类型和函数名及类型;</li><li>变量的赋值和初始化;</li><li>函数和闭包的主体;</li><li>哈希键值对的类型;</li><li>导入函数体;</li><li>外部的声明;</li></ol>通过对整棵抽象语法树的遍历,我们在每一个节点上都会对当前子树的类型进行验证,以保证当前节点上不会出现类型错误的问题,所有的类型错误和不匹配都会在这一个阶段被发现和暴露出来,结构体是否实现了某些接口也会在这一阶段被检查出来。
<h3>中间代码生成</h3>当我们将源文件转换成了抽象语法树、对整棵树的语法进行解析并进行类型检查之后,就可以认为当前文件中的代码不存在语法错误和类型错误的问题了,Go 语言的编译器就会将输入的抽象语法树转换成中间代码。
在类型检查之后,就会通过一个名为 <code>compileFunctions</code> 的函数开始对整个 Go 语言项目中的全部函数进行编译,这些函数会在一个编译队列中等待几个后端工作协程的消费,这些并发执行的 Goroutine 会将所有函数对应的抽象语法树转换成中间代码。
由于 Go 语言编译器的中间代码使用了 SSA 的特性,所以在这一阶段我们就能够分析出代码中的无用变量和片段并对代码进行优化。
Go 语言源代码的 <code>src/cmd/compile/internal</code> 目录中包含了很多机器码生成相关的包,不同类型的 CPU 分别使用了不同的包生成机器码,其中包括 amd64、arm、arm64、mips、mips64、ppc64、s390x、x86 和 wasm。
<h2>二、Golang编译器源码下载及安装</h2><pre><code>官网地址: https://golang.google.cn/dl/ 下载安装包或源码包均可 wget https://golang.google.cn/dl/go1.15.4.src.tar.gz 安装包下载很简单 设置好环境变量。 源码安装 cd go/src ./all.bash 安装报错 # ./all.bash ./make.bash: line 165: /root/go1.4/bin/go: No such file or directory Building Go cmd/dist using /root/go1.4. () ERROR: Cannot find /root/go1.4/bin/go. Set $GOROOT_BOOTSTRAP to a working Go tree >= Go 1.4.</code></pre><code>GOROOT_BOOTSTRAP 设置go1.4版本地址 实现了自举,编译后续版本</code>
我们学习的对象就是Go语言版本的编译器程序源码,源码目录<code>go/src/cmd/compile</code>。
调试编译器执行过程,必须调试<code>go安装目录下的编译器源码</code>,即GOROOT下源码,否则报内部包冲突错误。
编译器目录为go/src/cmd/compile,调试命令如下:
同理 goland调试编译器 <code>调试的源码也必须位于go安装目录</code>
首先需要通过Goland新建项目go 项目目录位于GOROOT,例如/user/local/go
Goland Debug配置方法如下 和dlv类似
<span class="img-wrap"></span>
以上是Goland debug的关键配置,具体使用方法,自行百度,和普通程序debug调试用法一致。
<span class="img-wrap"></span>
通过main函数,不难追踪到文件解析入口函数parseFiles,该函数为每个文件创建了一个noder对象,
<code>noders := make([]*noder, 0, len(filenames))</code>
noder拥有一个词法文件属性存储该源文件对应语法分析的结果。
<code>file *syntax.File //词法分析文件对象指针</code>
单个源文件对应的语法树<code>noder</code>结构体,<code>noder</code>结构体如下
syntax.File词法分析生成结果定义如下:
<pre><code>// package PkgName; DeclList[0], DeclList[1], ... type File struct { PkgName *Name DeclList []Decl Lines uint node }</code></pre><code>main</code>入口通过<code>parseFiles</code>方法开启协程通过<code>syntax.Parse</code>进行文件解析.
Parse函数代码如下:
解析过程中,创建了语法分析器parser,
<code>var p parser //声名语法分析树</code>
其中继承了词法分析器 <code>sanner</code> 的方法和属性,parser定义如下:
词法分析器scanner结构体定义如下:
<pre><code>#词法分析扫描器结构体 type scanner struct { source //持有源文件对象 mode uint nlsemi bool // if set 'n' and EOF translate to ';' // current token, valid after calling next() line, col uint tok token lit string // valid if tok is _Name, _Literal, or _Semi ("semicolon", "newline", or "EOF"); may be malformed if bad is true bad bool // valid if tok is _Literal, true if a syntax error occurred, lit may be malformed kind LitKind // valid if tok is _Literal op Operator // valid if tok is _Operator, _AssignOp, or _IncOp prec int // valid if tok is _Operator, _AssignOp, or _IncOp }</code></pre>源文件对象定义如下:
<pre><code>type source struct { src io.Reader errh func(line, pos uint, msg string) // source buffer buf [4 << 10]byte r0, r, w int // previous/current read and write buf positions, excluding sentinel line0, line uint // previous/current line col0, col uint // previous/current column (byte offsets from line start) ioerr error // pending io error // literal buffer lit []byte // literal prefix suf int // literal suffix; suf >= 0 means we are scanning a literal }</code></pre>词法分析函数(<code>syntax.Parse</code>)的 <code>fileOrNil()</code> 方法返回文件结构体<code>syntax.File</code>,也就是解析完毕的词法分析词法结果树。
<h3>词法分析过程</h3>Go 语言的词法解析是通过src/cmd/compile/internal/syntax/scanner.go文件中的 <code>scanner</code> 结构体实现的,这个结构体(<code>见上文定义</code>)会持有当前扫描的数据源文件、启用的模式和当前被扫描到的Token。
<code>src/cmd/compile/internal/syntax/tokens.go</code> 文件中定义了 Go 语言中支持的全部 Token 类型,所有的 <code>token</code> 类型都是正整数,你可以在这个文件中找到一些常见 Token 的定义,例如:操作符、括号和关键字等:
最右推导加向前查看构成了Go语言词法分析器的最基本原理,主要是由 <code>scanner</code> 这个结构体中的 <code>next</code> 方法驱动来获取下一个词法token,方法代码如下:
<pre><code>func (s *scanner) next() { nlsemi := s.nlsemi s.nlsemi = false redo: // skip white space c := s.getr() //过滤空字符,获取下一个字符 for c == ' ' || c == 't' || c == 'n' && !nlsemi || c == 'r' { c = s.getr() } // token start s.line, s.col = s.source.line0, s.source.col0 if isLetter(c) || c >= utf8.RuneSelf && s.isIdentRune(c, true) { s.ident() return } switch c { case -1: if nlsemi { s.lit = "EOF" s.tok = _Semi break } s.tok = _EOF case 'n': s.lit = "newline" s.tok = _Semi case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9': s.number(c) case '"': s.stdString() case '`': s.rawString() case ''': s.rune() case '(': s.tok = _Lparen case '[': s.tok = _Lbrack case '{': s.tok = _Lbrace case ',': s.tok = _Comma case ';': s.lit = "semicolon" s.tok = _Semi case ')': s.nlsemi = true s.tok = _Rparen case ']': s.nlsemi = true s.tok = _Rbrack case '}': s.nlsemi = true s.tok = _Rbrace case ':': if s.getr() == '=' { s.tok = _Define break } s.ungetr() s.tok = _Colon case '.': c = s.getr() if isDecimal(c) { s.ungetr() s.unread(1) // correct position of '.' (needed by startLit in number) s.number('.') break } if c == '.' { c = s.getr() if c == '.' { s.tok = _DotDotDot break } s.unread(1) } s.ungetr() s.tok = _Dot case ' ': s.op, s.prec = Add, precAdd c = s.getr() if c != ' ' { goto assignop } s.nlsemi = true s.tok = _IncOp case '-': s.op, s.prec = Sub, precAdd c = s.getr() if c != '-' { goto assignop } s.nlsemi = true s.tok = _IncOp case '*': s.op, s.prec = Mul, precMul // don't goto assignop - want _Star token if s.getr() == '=' { s.tok = _AssignOp break } s.ungetr() s.tok = _Star case '/': c = s.getr() if c == '/' { s.lineComment() goto redo } if c == '*' { s.fullComment() if s.source.line > s.line && nlsemi { // A multi-line comment acts like a newline; // it translates to a ';' if nlsemi is set. s.lit = "newline" s.tok = _Semi break } goto redo } s.op, s.prec = Div, precMul goto assignop case '%': s.op, s.prec = Rem, precMul c = s.getr() goto assignop case '&': c = s.getr() if c == '&' { s.op, s.prec = AndAnd, precAndAnd s.tok = _Operator break } s.op, s.prec = And, precMul if c == '^' { s.op = AndNot c = s.getr() } goto assignop case '|': c = s.getr() if c == '|' { s.op, s.prec = OrOr, precOrOr s.tok = _Operator break } s.op, s.prec = Or, precAdd goto assignop case '^': s.op, s.prec = Xor, precAdd c = s.getr() goto assignop case '<': c = s.getr() if c == '=' { s.op, s.prec = Leq, precCmp s.tok = _Operator break } if c == '<' { s.op, s.prec = Shl, precMul c = s.getr() goto assignop } if c == '-' { s.tok = _Arrow break } s.ungetr() s.op, s.prec = Lss, precCmp s.tok = _Operator case '>': c = s.getr() if c == '=' { s.op, s.prec = Geq, precCmp s.tok = _Operator break } if c == '>' { s.op, s.prec = Shr, precMul c = s.getr() goto assignop } s.ungetr() s.op, s.prec = Gtr, precCmp s.tok = _Operator case '=': if s.getr() == '=' { s.op, s.prec = Eql, precCmp s.tok = _Operator break } s.ungetr() s.tok = _Assign case '!': if s.getr() == '=' { s.op, s.prec = Neq, precCmp s.tok = _Operator break } s.ungetr() s.op, s.prec = Not, 0 s.tok = _Operator default: s.tok = 0 s.errorf("invalid character %#U", c) goto redo } return assignop: if c == '=' { s.tok = _AssignOp return } s.ungetr() s.tok = _Operator }</code></pre>通过getr获取下一个字符,通过许多不同的switch/case来识别token。
而通过解析器(parser)的fileOrNil方法来将识别的token加入到语法树:
通过fileOrNil方法,不难看出go语言四种不同的顶级声明token(TopLevelDecl)词法节点:_Const(常量)、_Type(类型)、_Var(变量)、_Func(函数及方法)以及_Package和_Import声明token。
解析器还封装了p.want()和p.got(),进行前驱分析和意图判断。
<code>got</code> 其实只是用于快速判断一些语句中的关键字,如果当前解析器中的 Token 是传入的 Token 就会直接跳过该 Token 并返回 <code>true</code>;而 <code>want</code> 就是对 <code>got</code> 的简单封装了,如果当前的 Token 不是我们期望的,就会立刻返回语法错误并结束这次编译。
<h3>词法分析节点介绍</h3><pre><code>// 顶级声明 type ( Decl interface { Node aDecl() } // Path // LocalPkgName Path ImportDecl struct { LocalPkgName *Name // including "."; nil means no rename present Path *BasicLit Group *Group // nil means not part of a group decl } // NameList // NameList = Values // NameList Type = Values ConstDecl struct { NameList []*Name Type Expr // nil means no type Values Expr // nil means no values Group *Group // nil means not part of a group decl } // Name Type TypeDecl struct { Name *Name Alias bool Type Expr Group *Group // nil means not part of a group Pragma Pragma decl } // NameList Type // NameList Type = Values // NameList = Values VarDecl struct { NameList []*Name Type Expr // nil means no type Values Expr // nil means no values Group *Group // nil means not part of a group decl } // func Name Type { Body } // func Name Type // func Receiver Name Type { Body } // func Receiver Name Type FuncDecl struct { Attr map[string]bool // go:attr map Recv *Field // nil means regular function Name *Name Type *FuncType Body *BlockStmt // nil means no body (forward declaration) Pragma Pragma // TODO(mdempsky): Cleaner solution. decl } )</code></pre>以FuncDecl为例,函数体存储类型为BlockStmt指针,常见statments定义如下:
<pre><code>// Statements type ( Stmt interface { Node aStmt() } SimpleStmt interface { Stmt aSimpleStmt() } EmptyStmt struct { simpleStmt } LabeledStmt struct { Label *Name Stmt Stmt stmt } BlockStmt struct { List []Stmt Rbrace Pos stmt } ExprStmt struct { X Expr simpleStmt } SendStmt struct { Chan, Value Expr // Chan <- Value simpleStmt } DeclStmt struct { DeclList []Decl stmt } AssignStmt struct { Op Operator // 0 means no operation Lhs,Rhs Expr // Rhs == ImplicitOne means Lhs (Op == Add) or Lhs-- (Op == Sub) simpleStmt } BranchStmt struct { Tok token // Break, Continue, Fallthrough, or Goto Label *Name // Target is the continuation of the control flow after executing // the branch; it is computed by the parser if CheckBranches is set. // Target is a *LabeledStmt for gotos, and a *SwitchStmt, *SelectStmt, // or *ForStmt for breaks and continues, depending on the context of // the branch. Target is not set for fallthroughs. Target Stmt stmt } CallStmt struct { Tok token // Go or Defer Call *CallExpr stmt } ReturnStmt struct { Results Expr // nil means no explicit return values stmt } IfStmt struct { Init SimpleStmt Cond Expr Then *BlockStmt Else Stmt // either nil, *IfStmt, or *BlockStmt stmt } ForStmt struct { Init SimpleStmt // incl. *RangeClause Cond Expr Post SimpleStmt Body *BlockStmt stmt } SwitchStmt struct { Init SimpleStmt Tag Expr // incl. *TypeSwitchGuard Body []*CaseClause Rbrace Pos stmt } SelectStmt struct { Body []*CommClause Rbrace Pos stmt } )</code></pre>这些不同类型的 <code>Stmt</code> 构成了全部命令式的 Go 语言代码,从中我们可以看到非常多熟悉的控制结构,例如 <code>if</code>、<code>for</code>、<code>switch</code> 和 <code>select</code>。
<h3>语法分析</h3>因为词法分析器 <code>scanner</code> 作为结构体被嵌入到了 <code>parser</code> 中,所以这个方法中的 <code>p.next()</code> 实际上调用的是 <code>scanner</code> 的 <code>next</code> 方法,它会直接获取文件中的下一个 Token,所以词法分析和语法分析其实是一起进行的。
上面parseFiles方法中词法扫描器和语法解析器(syntax.Parse)生成源文件对应的syntax.File对象后,生成抽象语法树的过程是通过p.decls()方法生成的<code>xtop = append(xtop, p.decls(p.file.DeclList)...)</code>
xtop是go语言抽象语法树数组
<code>var xtop []*Node</code>。
语法树单个树节点定义如下:
<pre><code>// A Node is a single node in the syntax tree. // Actually the syntax tree is a syntax DAG, because there is only one // node with Op=ONAME for a given instance of a variable x. // The same is true for Op=OTYPE and Op=OLITERAL. See Node.mayBeShared. 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 }</code></pre><h4>语法树实例分析</h4>下来我们来通过Goland IDE来debug下golang编译器
golang程序源码如下
断点设置<code>go/src/cmd/compile/internal/gc/noder.go:246</code>行
<span class="img-wrap"></span>
运行至端点后鼠标浮于<code>xtop</code>变量之上,点击 号浮框展示变量内容:
<span class="img-wrap"></span>
展开xtop变量观察语法树数组结构如下:
<span class="img-wrap"></span>
上图展示的是xtop[0]和xtop[2]及部分xtop[8]
了解 Go 语言的词法分析器 <code>scanner</code> 和语法分析器 <code>parser</code> 让我们对解析器处理源代码的过程有着比较清楚的认识,同时我们也在 Go 语言的文法和语法分析器中找到了熟悉的关键字和语法结构,加深了对 Go 语言的理解。
到此这篇关于“Golang编译器源码分析(1)”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持JQ教程网!您可能感兴趣的文章:
Golang编译器源码分析(2)
jQuery源码分析系列
【后端教程】走进Golang之编译器原理
小米技术出品——走进Golang之编译器原理
想系统学习GO语言(Golang
【Golang源码分析】Golang如何实现自举(一)
修改Go语言(golang)编译器源代码让它支持UTF-8 BOM
关于Golang的介绍
龙芯平台构建Go语言环境指南
golang会取代php吗