Go语言设计与实现 学习笔记 第二章 编译原理

2.1 概述

Go语言是一门需要编译才能运行的编程语言，也就是说代码在运行之前需要通过编译器生成二进制机器码，包含二进制机器码的文件才能在目标机器上运行，如果我们想要了解Go语言的实现原理，理解它的编译过程就是一个没有办法绕过的事情。

这一节会先对Go语言编译的过程进行概述，从顶层介绍编译器执行的几个步骤，随后的几节会分别剖析各个步骤完成的工作和实现原理，同时也会对一些需要预先掌握的知识进行介绍，确保后面的章节能够被更好的理解。

2.1.1 预备知识

想要深入了解Go语言的编译过程，需要提前了解一下编译过程中涉及的一些术语和专业知识。这些知识其实在我们的日常工作和学习中比较难用到，但是对于理解编译的过程和原理还是非常重要的。这一小节会简单挑选几个常见并且重要的概念提前进行介绍，减少后面章节的理解压力。

抽象语法树

抽象语法树（AST），是源代码语法的结构的一种抽象表示，它用树状的方式表示编程语言的语法结构。抽象语法树中的每一个节点都表示源代码中的一个元素，每一颗子树都表示一个语法元素，例如一个if else语句，我们可以从2 * 3 + 7这一表达式中解析出下图所示的抽象语法树。

作为编译器常用的数据结构，抽象语法树抹去了源代码中不重要的一些字符——空格、分号或者括号等等。编译器在执行完语法分析之后会输出一个抽象语法树，这个抽象语法树会辅助编译器进行语义分析，我们可以用它来确定语法正确的程序是否存在一些类型不匹配或不一致的问题。

静态单赋值

静态单赋值（Static Single Assigment, SSA）是中间代码的一个特性，如果一个中间代码具有静态单赋值的特性，那么每个变量就只会被赋值一次。在实践中我们通常会用添加下标的方式实现每个变量只能被赋值一次的特性，这里以下面的代码举个例子：

1. x := 1
2. x := 2
3. y := x

根据分析，我们其实能够发现上述的代码其实并不需要第一个将1赋值给x的表达式，也就是x := 1这一表达式在上述的代码片段中是没有作用的。

1. x1 := 1
2. x2 := 2
3. y1 := x2

当我们使用具有SSA特性的中间代码时，就可以非常清晰地发现变量y1的值和x1是完全没有任何关系的，所以在机器码生成时其实就可以省略第一步，这样就能减少需要执行的指令来优化这一段代码。

在中间代码中使用 SSA 的特性能够为整个程序实现以下的优化：
1.常数传播（constant propagation）

2.值域传播（value range propagation）

3.稀疏有条件的常数传播（sparse conditional constant propagation）

4.消除无用的程式码（dead code elimination）

5.全域数值编号（global value numbering）

6.消除部分的冗余（partial redundancy elimination）

7.强度折减（strength reduction）

8.寄存器分配（register allocation）

因为SSA的主要作用是对代码进行优化，所以它是编译器后端的一部分；当然代码编译领域除了SSA还有很多中间代码的优化方法，编译器生成代码的优化也是一个非常古老并且复杂的领域，这里就不会展开介绍了。

指令集

最后要介绍的一个预备知识就是指令集了，很多开发者都会遇到在生产环境运行的结果和本地不同的问题，导致这种情况的原因其实非常复杂，不同机器使用不同的指令也是可能的原因之一。

我们大多数开发者都会使用x86_64的Macbook作为工作上主要使用的硬件，在命令行中输入uname -m就能够获得当前机器上硬件的信息：

x86是目前比较常见的指令集，除了x86之外，还有很多其他的指令集，不同的处理器使用了不同的架构和机器语言，所以很多编程语言为了在不同的机器上运行需要将源代码根据架构翻译成不同的机器代码。

复杂指令集计算机（CISC）和精简指令集计算机（RISC）是目前的两种CPU区别，它们在设计理念上会有一些不同，从名字我们就能看出来这两种不同的设计有什么区别：
1.复杂指令集通过增加指令的数量减少需要执行的指令数（我认为不是通过增加指令的数量，而是通过增加指令的复杂度，使得一个指令可以完成多个操作，从而减少需要执行的指令数；而复杂指令集的指令数量确实更多，因为复杂指令集通过提供丰富多样的指令来尽可能地减少程序的指令数）；

2.精简指令集能使用更少的指令完成目标的计算任务（我认为是使用更小的指令集，而非更少的指令来完成计算任务，精简指令集的指令更加简单和基本，对比复杂指令集，通常需要更多的指令来完成相同的任务）；

早期的CPU为了减少机器语言指令的数量使用复杂指令集完成计算任务，这两者其实并没有绝对的好坏，它们只是在一些设计上的选择不同以达到不同的目的，我们会在后面的机器码生成一节中详细介绍指令集架构，不过各位读者也可以主动了解相关的内容。

2.1.2 编译原理

Go语言编译器的源代码在src/cmd/compile目录中，目录下的文件共同组成了Go语言的编译器，学过编译原理
的人可能听说过编译器的前端和后端，编译器的前端一般承担着词法分析、语法分析、类型检查和中间代码生成几部
分工作，而编译器后端主要负责目标代码的生成和优化，也就是将中间代码翻译成目标机器能够运行的二进制机器
码。

词法分析：
1.词法分析是将源代码文件中的字符序列转换为token序列的过程。

2.它通常是编译过程的第一阶段。

3.源代码会被逐字符扫描，并根据编程语言的规则分组成token。

4.这些令牌代表了程序语法的基本构建块，如关键字、标识符、标点符号和常量。

5.词法分析阶段的输出是一个令牌流，可以被语法分析器更容易地处理。

语法分析：
1.语法分析，也称为解析，是根据形式语法规则分析符号串的过程，无论是在自然语言还是在计算机语言中。

2.它涉及到检查给定的输入是否正确地按照语言的语法进行了结构化。

3.在计算机科学中，语法分析是编译程序过程中的一个重要阶段。它涉及到检查程序的源代码，确保它遵循了编写它的编程语言的正确语法。

4.语法错误，如缺少括号或关键字使用不正确，会在这个阶段被识别和报告，必须在程序成功编译之前进行修正。

词法分析和语法分析的主要区别在于，词法分析读取源代码的每一个字符并将其转换为有意义的词素（token），而语法分析则接收这些token并产生一个解析树作为输出。

Go的编译器在逻辑上可以被分成四个阶段：词法与语法分析、类型检查和AST转换、通用SSA生成和最后的机器代码生成，在这一节我们会使用比较少的篇幅分别介绍这四个阶段做的工作，后面的章节会具体介绍每一个阶段的具
体内容。

词法与语法分析

所有的编译过程其实都是从解析代码的源文件开始的，词法分析的作用就是解析源代码文件，它将文件中的字符串序列转换成Token序列，方便后面的处理和解析，我们一般会把执行词法分析的程序称为词法解析器（lexer）。

而语法分析的输入就是词法分析器输出的Token序列，这些序列会按照顺序被语法分析器进行解析，语法的解析过程就是将词法分析生成的Token按照语言定义好的文法（Grammar）自下而上或者自上而下地进行处理，每一个Go的源代码文件最终会被归纳成一个SourceFile结构：

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" }  

以上使用了巴科斯-诺尔范式（BNF）语法，也称为上下文无关语法，它是一种用于表示上下文无关语法的符号表示方法，广泛用于编程语言和指令集的语法定义。其中：
1.SourceFile是开始符号，表示源文件的结构。

2.=是定义操作符，表示左边的符号被定义为右边的结构。

3.PackageClause ";"表示一个包声明后跟一个分号。

4.{ ImportDecl ";" }表示零个或多个导入声明，每个声明后都跟一个分号。

5.{ TopLevelDecl ";" }表示零个或多个顶级声明，每个声明后都跟一个分号。

6.{}中的内容表示可以重复零次或多次。

7.;是终结符，表示语句结束。

词法分析会返回一个不包含空格、换行等字符的Token序列，例如：package，json，import，(，io，)等，而语法分析会把Token序列转换成有意义的结构体，也就是语法树：


将Token转换成上述『语法树』就会使用语法解析器，语法解析的结果其实就是上面介绍过的抽象语法树（AST），每一个AST都对应着一个单独的Go语言文件，这个抽象语法树中包括当前文件属于的包名、定义的常量、结构体和函数等。

如果在语法解析的过程中发生了任何语法错误，都会被语法解析器发现并将消息打印到标准输出上，整个编译过程也会随着错误的出现而被中止。词法与语法分析一节会详细介绍Go语言的文法、词法解析和语法解析过程。

类型检查

当拿到一组文件的抽象语法树之后，Go语言的编译器会对语法树中定义和使用的类型进行检查，类型检查分别会按照以下的顺序对不同类型的节点进行验证和处理：
1.常量、类型和函数名及类型；

2.变量的赋值和初始化；

3.函数和闭包的主体；

4.哈希键值对的类型；

5.导入函数体；

6.外部的声明；

通过对整颗抽象语法树的遍历，我们在每一个节点上都会对当前子树的类型进行验证，以保证当前节点上不会出现类型错误的问题，所有的类型错误和不匹配都会在这一个阶段被发现和暴露出来，结构体是否实现了某些接口也会在这一阶段被检查出来。

类型检查阶段不止会对节点的类型进行验证，还会展开和改写一些内建的函数，例如make关键字在这个阶段会根据子树的结构被替换成makeslice或者makechan等函数。


类型检查这一过程在整个编译流程中还是非常重要的，Go语言的很多关键字都依赖类型检查期间的展开和改写，后面的章节类型检查会详细介绍这一步骤。

中间代码生成

当我们将源文件转换成了抽象语法树、对整棵树的语法进行解析并进行类型检查之后，就可以认为当前文件中的代码不存在语法错误和类型错误的问题了，Go语言的编译器就会将输入的抽象语法树转换成中间代码。

在类型检查之后，就会通过一个名为compileFunctions的函数开始对整个Go语言项目中的全部函数进行编译，这些函数会在一个编译队列中等待几个后端工作协程的消费，这些并发执行的Goroutine会将所有函数对应的抽象语法树转换成中间代码。

由于Go语言编译器的中间代码使用了SSA的特性，所以在这一阶段我们就能够分析出代码中的无用变量和片段并对代码进行优化，在中间代码生成这一节会详细介绍中间代码的生成过程并简单介绍Go语言是如何在中间代码中使用SSA特性的。

机器码生成

Go语言源代码的src/cmd/compile/internal目录中包含了很多机器码生成相关的包，不同类型的CPU分别使用了不同的包生成机器码，其中包括amd64、arm、arm64、mips、mips64、ppc64、s390x、x86和wasm，其中比较有趣的就是WebAssembly（Wasm）了。

作为一种在栈虚拟机上使用的二进制指令格式，Wasm的设计的主要目标就是在Web浏览器上提供一种具有高可移植性的目标语言。Go语言的编译器既然能够生成Wasm格式的指令，那么就能够运行在常见的主流浏览器中。

$ GOARCH=wasm GOOS=js go build -o lib.wasm main.go

我们可以使用上述的命令将Go的源代码编译成能够在浏览器上运行的WebAssembly文件，当然除了这种新兴的二进制指令格式之外，Go语言经过编译还可以运行在几乎全部的主流机器上，不过对于除了Linux和Darwin之外的机器上兼容性上可能还是有一些问题，例如：Go Plugin至今仍然不支持Windows 8。

机器码生成一节会详细介绍将中间代码翻译到不同目标机器的过程，在这个章节中也会简单介绍不同的指令集架构的区别。

2.1.3 编译器入口

Go语言的编译器入口在src/cmd/compile/internal/gc/main.go文件中，这个600多行的Main函数就是Go语言编译器的主程序，该函数会先获取命令行传入的参数并更新编译选项和配置，随后就会开始运行parseFiles函数对输入的所有文件进行词法与语法分析得到文件对应的抽象语法树：

1. func Main(archInit func(*Arch)) {
2.     ...
3.
4.     lines := parseFiles(flag.Args())

接下来就会分九个阶段对抽象语法树进行更新和编译，就像我们在上面介绍的，整个过程会经历类型检查、SSA中间代码生成以及机器码生成三个部分：
1.检查常量、类型和函数的类型；

2.处理变量的赋值；

3.对函数的主体进行类型检查；

4.决定如何捕获变量；

5.检查内联函数的类型；

6.进行逃逸分析；

7.将闭包的主体转换成引用的捕获变量（即将闭包中所捕获的变量从直接嵌入到闭包主体中）；

8.编译顶层函数；

9.检查外部依赖的声明；

对整个编译过程有一个顶层的认识之后，我们重新回到词法和语法分析后的具体流程，在这里编译器会对生成语法树中的节点执行类型检查，除了常量、类型和函数这些顶层声明之外，它还会对变量的赋值语句、函数主体等结构进行检查：

for i := 0; i < len(xtop); i++ {
    n := xtop[i]
    if op := n.Op; op != ODCL && op != OAS && op != OAS2 && (op != ODCLTYPE || !n.Left.Name.Param.Alias) {
        xtop[i] = typecheck(n, ctxStmt)
    }
}

for i := 0; i < len(xtop); i++ {
    n := xtop[i]
    if op := n.Op; op == ODCL || op == OAS || op == OAS2 || op == ODCLTYPE && n.Left.Name.Param.Alias {
        xtop[i] = typecheck(n, ctxStmt)
    }
}
...

类型检查会遍历传入节点的全部子节点，这个过程会对make等关键字进行展开和重写，类型检查会改变语法树中的一些节点，不会生成新的变量或者语法树，这个过程的结束也意味着源代码中已经不存在语法错误和类型错误，中间代码和机器码都可以根据抽象语法树正常生成了。

	initssaconfig()
	
	peekitabs()
	
	for i := 0; i < len(xtop); i++ {
	    n := xtop[i]
	    if n.Op == ODCLFUNC {
	        funccompile(n)
	    }
	}
	
	compileFunctions()
	
	for i, n := range externdcl {
	    if n.Op == ONAME {
	        externdcl[i] = typecheck(externdcl[i], ctxExpr)
	    }
	}
	
	checkMapKeys()
}

在主程序运行的最后，会将顶层的函数编译成中间代码并根据目标的CPU架构生成机器码，不过在这一阶段也有可能会再次对外部依赖进行类型检查以验证正确性。

2.1.4 小结

Go语言的编译过程其实是非常有趣并且值得学习的，通过对Go语言四个编译阶段的分析和对编译器主函数的梳理，我们能够对Go语言的实现有一些基本的理解，掌握编译的过程之后，Go语言对于我们来讲也不再是一个黑盒，所以学习其编译原理的过程还是非常让人着迷的。

2.2 词法和语法分析

当使用通用编程语言进行编写代码时，我们一定要知道代码是写给人看的，只是恰好可以被机器编译和执行，而很难被人理解的代码是非常糟糕并且不容易维护的。代码其实就是按照约定格式编写的一堆字符串，经过训练的软件工程师可以在脑内对语言的源代码进行编译并运行目标程序，我们能对本来无意义的字符串进行分组和分析，按照约定的语法来理解源代码。

既然工程师能够按照一定的方式理解和编译Go语言的源代码，那么我们如何模拟人理解源代码的方式构建一个能够分析编程语言代码的程序呢。我们在这一节中将介绍词法分析和语法分析这两个重要的编译过程，这两个过程能将原本机器看来无意义的源文件转换成更容易理解、分析并且结构化的抽象语法树，接下来我们就看一看解析器眼中的Go语言是什么样的。

2.2.1 词法分析

源代码在编译器眼中其实就是一团乱麻，一个由『无实际意义』字符组成的、无法被理解的字符串，所有的字符在编
译器看来并没有什么区别，为了理解这些字符我们需要做的第一件事情就是将字符串分组，这样能够降低理解字符串
的成本，简化分析源代码的过程。

make(chan int)

一个不懂编程的人看到上述文本的的第一反应就是将上述字符串分成几个部分——make 、chan、int和括号，这个凭直觉分解文本的过程其实就是词法分析，词法分析是计算机科学中将字符序列转换为标记（token）序列的过程。

lex

lex是用于生成词法分析器的工具，lex生成的代码能够将一个文件中的字符分解成Token序列，很多语言在设计早期都会使用它快速设计出原型。词法分析作为具有固定模式的任务，出现这种更抽象的工具其实是必然的，lex作为一个代码生成器，使用了类似C语言的语法，我们可以理解成lex使用正则匹配对输入的字符流进行扫描，下面是一个lex文件的示例：

%{
#include <stdio.h>
%}

%%

package printf("PACKAGE ");
import printf("IMPORT ");
\\. printf("DOT ");
\{ printf("LBRACE ");
\} printf("RBRACE ");
\( printf("LPAREN ");
\) printf("RPAREN ");
\" printf("QUOTE ");
\n printf("\n");
[0-9]+ printf("NUMBER ");
[a-zA-Z_]+ printf("IDENT ");

%%

这个定义好的文件能够解析package和import关键字、常见的特殊字符、数字以及标识符，虽然这里的规则可能有一些简陋和不完善，但是如果用来解析下面的这一段代码还是比较轻松的：

package main

import (
    "fmt"
)

func main() {
    fmt.Println("Hello")
}

.l结尾的lex代码文件并不能直接运行，首先需要通过lex命令将上面的simplego.l『展开』成C语言代码，这里可以直接执行如下的命令编译并打印当前文件中的内容：


lex.yy.c的前600行基本都是宏和函数的声明和定义，后面生成的代码大都是为yylex这个函数服务的，这个函数使用有限自动机（DFA）的程序结构来分析输入的字符流，上述代码中while循环就是这个有限自动机的主体，你如果仔细看这个文件生成的代码会发现当前的文件中并不存在main函数， main函数其实是在liblex这个库中定义的，所以在编译时其实需要添加额外-ll选项：

$ cc lex.yy.c -o simplego -ll
$ cat main.go | ./simplego

当我们将C语言代码通过gcc编译成二进制代码之后，就可以使用管道将上面提到的Go语言代码作为输入传递到生成的词法分析器中，这个词法分析器会打印出如下的内容：

PACKAGE IDENT

IMPORT LPAREN
    QUOTE IDENT QUOTE
RPAREN

IDENT IDENT LPAREN RPAREN LBRACE
    IDENT DOT IDENT LPAREN QUOTE IDENT QUOTE RPAREN
RBRACE

从上面的输出我们能够看到Go源代码的影子，lex生成的词法分析器lexer通过正则匹配的方式将机器原本很难理解的字符串进行分解成很多的Token，有利于后面的继续处理。

如上图所示，到这里我们已经为各位读者展示了从定义.l文件，使用lex将.l文件编译成C语言代码到编译成二进制的全过程，而最后生成的词法分析器也能够将简单的Go语言代码进行分组， lex的使用还是比较简单的，我们可以使用它快速实现词法分析器，相信各位读者对这个工具也有了一定的了解。

Go

Go语言的词法解析是通过src/cmd/compile/internal/syntax/scanner.go文件中的scanner结构体实现的，这个结构体会持有当前扫描的数据源文件、启用的模式和当前被扫描到的Token：

type scanner struct {
    source
    mode    uint
    nlsemi  bool

    // current token, valid after calling next()
    line, col uint
    tok       token
    lit       string
    kind      LitKind
    op        Operator
    prec      int
}

src/cmd/compile/internal/syntax/tokens.go文件中定义了Go语言中支持的全部Token类型，所有的token类型都是正整数，你可以在这个文件中找到一些常见Token的定义，例如：操作符、括号和关键字等：

const (
    _ token = iota
    _EOF // EOF

    // operators and operations
    _Operator // op
    // ...

    // delimiters
    _Lparen // (
    _Lbrack // [
    // ...

    // keywords
    _Break // break
    // ...
    _Type // type
    _Var  // var

    tokenCount //
)

从Go语言中定义的Token类型，我们可以将语言中的元素分成几个不同的类别，分别是名称和字面量、操作符、分隔符和关键字。词法分析主要是由scanner这个结构体中的next方法驱动，这个250行函数的主体就是一个switch/case结构：

func (s *scanner) next() {
    c := s.getr()
    for c == ' ' || c == '\t' || c == '\n' || c == '\r' {
        c = s.getr()
    }

    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:
        s.tok = _EOF

    case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
        s.number(c)

    // ...
    }
}

scanner每次都会通过getr函数获取文件中最近的未被解析的字符，然后根据当前字符的不同执行不同的case，如果遇到了空格和换行符这些空白字符会直接跳过，如果当前字符是0就会执行number方法尝试匹配一个数字。

func (s *scanner) number(c rune) {
    s.startLit()

    s.kind = IntLit
    for isDigit(c) {
        c = s.getr()
    }

    s.ungetr()
    s.nlsemi = true
    s.lit = string(s.stopLit())
    s.tok = _Literal
}

上述的number方法省略了很多的代码，包括如何匹配浮点数、指数和复数，我们只是简单看一下词法分析匹配的逻辑：
1.在开始具体匹配之前调用startLit记录一下当前Token的开始位置；

2.在for循环中不断获取最新的字符，将字符追加到scanner持有的缓冲区中；

3.方法返回之前会通过ungetr撤销最近获取的错误字符（非数字）并将字面量和Token的类型传递回scanner；

当前包中的词法分析器scanner也只是为上层提供了next方法，词法解析的过程都是惰性的，只有在上层的解析器需要时才会调用next获取最新的Token。

Go语言的词法元素相对来说还是比较简单，使用这种巨大的switch/case进行词法解析也比较方便和顺手，早期的Go语言虽然使用lex这种工具来生成词法解析器，但是最后还是使用Go来实现词法分析器，用自己写的词法分析器来解析自己。

2.2.2 语法分析

说完了编译最开始的词法分析过程，接下来就到了语法分析，语法分析是根据某种特定的形式文法（Grammar）对Token序列构成的输入文本进行分析并确定其语法结构的一种过程。从上面的定义来看，词法分析器输出的结果——Token序列就是语法分析器的输入。

在语法分析的过程会使用自顶向下或者自底向上的方式进行推导，在介绍Go语言的语法分析的实现原理之前，我们会先来介绍语法分析中的文法和分析方法。

文法

上下文无关文法是用来对某种编程语言进行形式化的、精确的描述工具，我们能够通过文法定义一种语言的语法，它主要包含了一系列用于转换字符串的生产规则（production rule）。上下文无关文法中的每一个生产规则都会将规则左侧的非终结符（终结符是文法中无法再被展开的符号，而非终结符与之相反，还可以通过生产规则进行展开，例如“id”、“123”等标识或者字面量）转换成右侧的字符串，文法都由以下的四个部分组成：
1.$N$有限个非终结符的集合；

2.$\Sigma$有限个终结符的集合；

3.$P$有限个生产规则的集合；

4.$S$非终结符集合中唯一的开始符号；

文法被定义成一个四元组$(N, \Sigma, P, S)$，这个元组中的几部分就是上面提到的四个符号，其中最为重要的就是生产规则了，每一个生产规则都会包含非终结符、终结符或者开始符号，我们在这里可以举一个简单的例子：
1.$S \rightarrow aSb $：从S开始推导，生成规则是在S的左右分别加一个a和b。

2.$S \rightarrow ab $：从S开始推导，生成规则直接是ab，即S就是ab。加上文法1，含义是n个a后面跟n个b。

上述规则构成的文法就能够表示ab、aabb以及aaa…bbb等字符串，编程语言的文法就是由这一系列的生产规则表示的，在这里我们可以从src/cmd/compile/internal/syntax/parser.go文件中摘抄一些Go语言文法的生产规则：

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .
PackageClause = "package" PackageName .
PackageName = identifier .

ImportDecl = "import" ( ImportSpec | "(" { ImportSpec ";" } ")" ) .
ImportSpec = [ "." | PackageName ] ImportPath .
ImportPath = string_lit .

TopLevelDecl = Declaration | FunctionDecl | MethodDecl .
Declaration = ConstDecl | TypeDecl | VarDecl .

因为每个Go源代码文件最终都会被解析成一个独立的抽象语法树，所以语法树最顶层的结构或者开始符号其实就是SourceFile：

SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .

从SourceFile相关的生产规则我们可以看出，每一个文件都包含一个package的定义以及可选的import声明和其他的顶层声明（TopLevelDecl），每一个SourceFile在编译器中都对应一个File结构体，你能从它们的定义中轻松找到两者的联系：

type File struct {
    PkgName *Name
    DeclList []Decl
    Lines uint
    node
}

顶层声明有五大类型，分别是常量、类型、变量、函数和方法，你可以在文件src/cmd/compile/internal/syntax/parser.go中找到这五大类型的定义。

ConstDecl = "const" ( ConstSpec | "(" { ConstSpec ";" } ")" ) .
ConstSpec = IdentifierList [ [ Type ] "=" ExpressionList ] .

TypeDecl = "type" ( TypeSpec | "(" { TypeSpec ";" } ")" ) .
TypeSpec = AliasDecl | TypeDef .
AliasDecl = identifier "=" Type .
TypeDef = identifier Type .

VarDecl = "var" ( VarSpec | "(" { VarSpec ";" } ")" ) .
VarSpec = IdentifierList ( Type [ "=" ExpressionList ] | "=" ExpressionList )

上述的文法分别定义了Go语言中常量、类型和变量三种常见的结构，从文法中可以看到语言中的很多关键字const 、 type和var ，稍微回想一下我们日常接触的Go语言代码就能验证这里文法的正确性。

除了三种简单的语法结构之外，函数和方法的定义就更加复杂，从下面的文法我们可以看到Statement总共可以转换成15种不同的语法结构，这些语法结构就包括我们经常使用的switch/case、if/else、for循环以及select等语句：

FunctionDecl = "func" FunctionName Signature [ FunctionBody ] .
FunctionName = identifier .
FunctionBody = Block .

MethodDecl = "func" Receiver MethodName Signature [ FunctionBody ] .
Receiver = Parameters .

Block = "{" StatementList "}" .
StatementList = { Statement ";" } .

Statement =
    Declaration | LabeledStmt | SimpleStmt |
    GoStmt | ReturnStmt | BreakStmt | ContinueStmt | GotoStmt |
    FallthroughStmt | Block | IfStmt | SwitchStmt | SelectStmt | ForStmt |
    DeferStmt .

SimpleStmt = EmptyStmt | ExpressionStmt | SendStmt | IncDecStmt | Assignment | ShortVarDecl .

这些不同的语法结构共同定义了Go语言中能够使用的语法结构和表达式，对于Statement展开的更多内容这篇文章就不会详细介绍了，感兴趣的读者可以直接查看Go语言说明书或者直接从src/cmd/compile/internal/syntax/parser.go文件中找到想要的答案。

分析方法

语法分析的分析方法一般分为自顶向下和自底向上两种，这两种方式会使用不同的方式对输入的Token序列进行推导：
1.自顶向下分析：可以被看作找到当前输入流最左推导的过程，对于任意一个输入流，根据当前的输入符号，确定一个生产规则，使用生产规则右侧的符号替代相应的非终结符向下推导；

2.自底向上分析：语法分析器从输入流开始，每次都尝试重写最右侧的多个符号，这其实就是说解析器会从最简单
的符号进行推导，在解析的最后合并成开始符号；

如果读者无法理解上述的定义也没有关系，我们会在这一节的剩余部分介绍两种不同的分析方法以及它们的具体分析过程。

自顶向下