词法分析和语法分析是同一个阶段。
语法分析是根据某种特定的形式文法（Grammar）对 Token 序列构成的输入文本进行分析并确定其语法结构的过程。从上面的定义来看，词法分析器输出的结果 — Token 序列是语法分析器的输入。
语法分析的过程会使用自顶向下或者自底向上的方式进行推导，在介绍 Go 语言语法分析之前，我们会先来介绍语法分析中的文法和分析方法。

文法

上下文无关文法是用来形式化、精确描述某种编程语言的工具，我们能够通过文法定义一种语言的语法，它主要包含一系列用于转换字符串的生产规则（Production rule）。上下文无关文法中的每一个生产规则都会将规则左侧的非终结符转换成右侧的字符串，文法都由以下的四个部分组成：

终结符是文法中无法再被展开的符号，而非终结符与之相反，还可以通过生产规则进行展开，例如 “id”、“123” 等标识或者字面量。
生产规则在计算机科学领域是符号替换的重写规则，S -> aSb 就是可以用右侧的 aSb 将左侧的符号进行展开

• N 有限个非终结符的集合；
• Σ有限个终结符的集合；
• P有限个生产规则的集合；
• S 非终结符集合中唯一的开始符号；
  文法被定义成一个四元组 (N,Σ,P,S)，这个元组中的几部分是上面提到的四个符号，其中最为重要的就是生产规则，每个生产规则都会包含非终结符、终结符或者开始符号，我们在这里可以举个简单的例子：

S→aSb
S→ab
S→ϵ
上述规则构成的文法就能够表示 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 语言更详细的文法可以从 Language Specification中找到，这里不仅包含语言的文法，还包含词法元素、内置函数等信息。
因为每个 Go 源代码文件最终都会被解析成一个独立的抽象语法树，所以语法树最顶层的结构或者开始符号都是 SourceFile：

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

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

type File struct {
    Pragma   Pragma
    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 .

分析方法

语法分析的分析方法一般分为自顶向下和自底向上两种，这两种方式会使用不同的方式对输入的 Token 序列进行推导：

• 自顶向下分析：可以被看作找到当前输入流最左推导的过程，对于任意一个输入流，根据当前的输入符号，确定一个生产规则，使用生产规则右侧的符号替代相应的非终结符向下推导；
• 自底向上分析：语法分析器从输入流开始，每次都尝试重写最右侧的多个符号，这其实是说解析器会从最简单的符号进行推导，在解析的最后合并成开始符号；

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

自顶向下

LL 文法 是一种使用自顶向下分析方法的文法，下面给出了一个常见的 LL 文法：

1. S→aS1
2. S1→bS1
3. S1→ϵ

假设我们存在以上的生产规则和输入流 abb，如果这里使用自顶向下的方式进行语法分析，我们可以理解为每次解析器会通过新加入的字符判断应该使用什么方式展开当前的输入流：

1. S（开始符号）
2. aS1（规则 1)
3. abS1（规则 2)
4. abbS1（规则 2)
5. abb（规则 3)

这种分析方法一定会从开始符号分析，通过下一个即将入栈的符号判断应该如何对当前堆栈中最右侧的非终结符（S 或 S1）进行展开，直到整个字符串中不存在任何的非终结符，整个解析过程才会结束。

自底向上

但是如果我们使用自底向上的方式对输入流进行分析时，处理过程就会完全不同了，常见的四种文法 LR(0)、SLR、LR(1) 和 LALR(1) 使用了自底向上的处理方式，我们可以简单写一个与上一节中效果相同的 LR(0) 文法：

1. S→S1<
2. S1→S1b
3. S1→a
   使用上述等效的文法处理同样地输入流 abb 会使用完全不同的过程对输入流进行展开：
4. a（入栈）
5. S1（规则 3）
6. S1b（入栈）
7. S1（规则 2）
8. S1b（入栈）
9. S1（规则 2）
10. S（规则 1）
    自底向上的分析过程会维护一个栈用于存储未被归约的符号，在整个过程中会执行两种不同的操作，一种叫做入栈（Shift），也就是将下一个符号入栈，另一种叫做归约（Reduce），也就是对最右侧的字符串按照生产规则进行合并。

上述的分析过程和自顶向下的分析方法完全不同，这两种不同的分析方法其实也代表了计算机科学中两种不同的思想 — 从抽象到具体和从具体到抽象。

Lookahead

在语法分析中除了 LL 和 LR 这两种不同类型的语法分析方法之外，还存在另一个非常重要的概念，就是向前查看（Lookahead），在不同生产规则发生冲突时，当前解析器需要通过预读一些 Token 判断当前应该用什么生产规则对输入流进行展开或者归约，例如在 LALR(1) 文法中，需要预读一个 Token 保证出现冲突的生产规则能够被正确处理。

Go

Go 语言的解析器使用了 LALR(1) 的文法来解析词法分析过程中输出的 Token 序列，最右推导加向前查看构成了 Go 语言解析器的最基本原理，也是大多数编程语言的选择。

我们在概述中已经介绍了编译器的主函数，该函数调用的 cmd/compile/internal/gc.parseFiles会使用多个 Goroutine 来解析源文件，解析的过程会调用 cmd/compile/internal/syntax.Parse，该函数初始化了一个新的 cmd/compile/internal/syntax.parser(结构体并通过 cmd/compile/internal/syntax.parser.fileOrNil方法开启对当前文件的词法和语法解析：

func Parse(base *PosBase, src io.Reader, errh ErrorHandler, pragh PragmaHandler, mode Mode) (_ *File, first error) {
    var p parser
    p.init(base, src, errh, pragh, mode)
    p.next()
    return p.fileOrNil(), p.first
}

cmd/compile/internal/syntax.parser.fileOrNil(方法其实是对上面介绍的 Go 语言文法的实现，该方法首先会解析文件开头的 package 定义：

// SourceFile = PackageClause ";" { ImportDecl ";" } { TopLevelDecl ";" } .
func (p *parser) fileOrNil() *File {
    f := new(File)
    f.pos = p.pos()

    if !p.got(_Package) {
        p.syntaxError("package statement must be first")
        return nil
    }
    f.PkgName = p.name()
    p.want(_Semi)

从上面的这一段方法中我们可以看出，当前方法会通过 cmd/compile/internal/syntax.parser.got来判断下一个 Token 是不是 package 关键字，如果是 package 关键字，就会执行 cmd/compile/internal/syntax.parser.name 来匹配一个包名并将结果保存到返回的文件结构体中。

for p.got(_Import) {
        f.DeclList = p.appendGroup(f.DeclList, p.importDecl)
        p.want(_Semi)
    }

确定了当前文件的包名之后，就开始解析可选的 import 声明，每一个 import 在解析器看来都是一个声明语句，这些声明语句都会被加入到文件的 DeclList 中。

在这之后会根据编译器获取的关键字进入 switch 的不同分支，这些分支调用 cmd/compile/internal/syntax.parser.appendGroup方法并在方法中传入用于处理对应类型语句的 cmd/compile/internal/syntax.parser.constDecl、cmd/compile/internal/syntax.parser.typeDecl函数。

    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:
            ...
        }
    }

    f.Lines = p.source.line

    return f
}

cmd/compile/internal/syntax.parser.fileOrNil 使用了非常多的子方法对输入的文件进行语法分析，并在最后会返回文件开始创建的 cmd/compile/internal/syntax.File结构体。

读到这里的人可能会有一些疑惑，为什么没有看到词法分析的代码，这是因为词法分析器 cmd/compile/internal/syntax.scanner作为结构体被嵌入到了 cmd/compile/internal/syntax.parser中，所以这个方法中的 p.next() 实际上调用的是 `cmd/compile/internal/syntax.scanner.next 方法，它会直接获取文件中的下一个 Token，所以词法和语法分析一起进行的。

cmd/compile/internal/syntax.parser.fileOrNil 与在这个方法中执行的其他子方法共同构成了一棵树，这棵树根节点是 cmd/compile/internal/syntax.parser.fileOrNil，子节点是 cmd/compile/internal/syntax.parser.importDecl、cmd/compile/internal/syntax.parser.constDecl等方法，它们与 Go 语言文法中的生产规则一一对应。
Go 语言解析器的方法:

image.png

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

我们根据这个规则能很好地理解语法分析器的实现原理 - 将编程语言的所有生产规则映射到对应的方法上，这些方法构成的树形结构最终会返回一个抽象语法树。

因为大多数方法的实现都非常相似，所以这里就仅介绍 cmd/compile/internal/syntax.parser.fileOrNil方法的实现了，想要了解其他方法的实现原理，读者可以自行查看 src/cmd/compile/internal/syntax/parser.go文件，该文件包含了语法分析阶段的全部方法。

辅助方法

虽然这里不会展开介绍其他类似方法的实现，但是解析器运行过程中有几个辅助方法我们还是要简单说明一下，首先就是 cmd/compile/internal/syntax.parser.got和 cmd/compile/internal/syntax.parser.want这两个常见的方法：

func (p *parser) got(tok token) bool {
    if p.tok == tok {
        p.next()
        return true
    }
    return false
}

func (p *parser) want(tok token) {
    if !p.got(tok) {
        p.syntaxError("expecting " + tokstring(tok))
        p.advance()
    }
}

cmd/compile/internal/syntax.parser.got 只是用于快速判断一些语句中的关键字，如果当前解析器中的 Token 是传入的 Token 就会直接跳过该 Token 并返回 true；而 cmd/compile/internal/syntax.parser.want 就是对 cmd/compile/internal/syntax.parser.got的简单封装了，如果当前 Token 不是我们期望的，就会立刻返回语法错误并结束这次编译。

这两个方法的引入能够帮助工程师在上层减少判断关键字的大量重复逻辑，让上层语法分析过程的实现更加清晰。

另一个方法 cmd/compile/internal/synctax.parser.appendGroup的实现就稍微复杂了一点，它的主要作用就是找出批量的定义，我们可以简单举一个例子：

var (
   a int
   b int
)

这两个变量其实属于同一个组（Group），各种顶层定义的结构体 cmd/compile/internal/syntax.parser.constDecl、cmd/compile/internal/syntax.parser.varDecl在进行语法分析时有一个额外的参数 cmd/compile/internal/syntax.Group，这个参数是通过 cmd/compile/internal/syntax.parser.appendGroup方法传递进去的：

func (p *parser) appendGroup(list []Decl, f func(*Group) Decl) []Decl {
    if p.tok == _Lparen {
        g := new(Group)
        p.list(_Lparen, _Semi, _Rparen, func() bool {
            list = append(list, f(g))
            return false
        })
    } else {
        list = append(list, f(nil))
    }

    return list
}

cmd/compile/internal/syntax.parser.appendGroup方法会调用传入的 f 方法对输入流进行匹配并将匹配的结果追加到另一个参数 cmd/compile/internal/syntax.File 结构体中的 DeclList 数组中，import、const、var、type 和 func 声明语句都是调用 cmd/compile/internal/syntax.parser.appendGroup方法解析的。

节点

语法分析器最终会使用不同的结构体来构建抽象语法树中的节点，其中根节点 cmd/compile/internal/syntax.File我们已经在上面介绍过了，其中包含了当前文件的包名、所有声明结构的列表和文件的行数：

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

src/cmd/compile/internal/syntax/nodes.go文件中也定义了其他节点的结构体，其中包含全部声明类型的，这里简单看一下函数声明的结构：

type (
    Decl interface {
        Node
        aDecl()
    }

    FuncDecl struct {
        Attr   map[string]bool
        Recv   *Field
        Name   *Name
        Type   *FuncType
        Body   *BlockStmt
        Pragma Pragma
        decl
    }
}

从函数定义中我们可以看出，函数在语法结构上主要由接受者、函数名、函数类型和函数体几个部分组成，函数体 cmd/compile/internal/syntax.BlockStmt是由一系列的表达式组成的，这些表达式共同组成了函数的主体：
Go 语言函数定义的结构体:

image.png

函数的主体其实是一个 cmd/compile/internal/syntax.Stmt数组，cmd/compile/internal/syntax.Stmt是一个接口，实现该接口的类型其实也非常多，总共有 14 种不同类型的 cmd/compile/internal/syntax.Stmt实现：
Go 语言的 14 种声明：

image.png