Go编译原理系列3（词法分析）

在上一篇文章中，介绍了词法分析中的核心技术，有穷自动机（DFA），以及两个常见的词法分析器的使用及工作原理。在这个基础上去看Go的词法分析源码会轻松许多

本文主要包含以下内容：

1. Go编译的入口文件，以及在编译入口文件中做了哪些事情
2. 词法分析处在Go编译的什么位置，以及详细过程是什么样的
3. 写一个测试的go源文件，对这个源文件进行词法分析，并获取到词法分析的结果

Go的编译入口

为了能更清楚的了解Go的编译过程是如何走到词法分析这一步的，这里先介绍Go的编译入口文件在什么地方，以及大致做了哪些事情

Go的编译入口文件在：src/cmd/compile/main.go -> gc.Main(archInit)

进入到gc.Main(archInit)这个函数，这个函数内容比较长，它前边部分做的事情主要是获取命令行传入的参数并更新编译选项和配置。然后你会看到下边这行代码

lines := parseFiles(flag.Args())

这就是词法分析和语法分析的入口，它会对传入的文件进行词法和语法分析，得到的是一棵语法树，后边就会将它构建成抽象语法树，然后对它进行类型检查等操作，会在后边的文章中分享

打开parseFiles(flag.Args())文件，可以看到如下内容（我省略了后边部分的代码，主要看词法分析这块的内容）：

func parseFiles(filenames []string) uint {
    noders := make([]*noder, 0, len(filenames))
    // Limit the number of simultaneously open files.
    sem := make(chan struct{}, runtime.GOMAXPROCS(0)+10)

    for _, filename := range filenames {
        p := &noder{
            basemap: make(map[*syntax.PosBase]*src.PosBase),
            err:     make(chan syntax.Error),
        }
        noders = append(noders, p)

        go func(filename string) {
            sem <- struct{}{}
            defer func() { <-sem }()
            defer close(p.err)
            base := syntax.NewFileBase(filename)

            f, err := os.Open(filename)
            if err != nil {
                p.error(syntax.Error{Msg: err.Error()})
                return
            }
            defer f.Close()

            p.file, _ = syntax.Parse(base, f, p.error, p.pragma, syntax.CheckBranches) // errors are tracked via p.error
        }(filename)
    }
    ......
}

我们知道，在Go的编译过程中，最终每一个源文件，都会被解析成一棵语法树，从上边代码的前几行就能看出来，它首先会创建多个协程去编译源文件，但是每次是有限制打开的源文件数的

sem := make(chan struct{}, runtime.GOMAXPROCS(0)+10)

然后遍历源文件，并起多个协程对文件进行词法和语法分析，主要体现在for循环和go func这块。在go func中可以看到，它会先初始化源文件的信息，主要是记录源文件的名称、行、列的信息，目的是为了在进行词法和语法分析的过程中，如果遇到错误，能够报告出现错误的位置。主要包含以下几个结构体

type PosBase struct {
    pos       Pos
    filename  string
    line, col uint32
}

type Pos struct {
    base      *PosBase
    line, col uint32
}

后边就是打开源文件，开始初始化语法分析器，之所以初始化的是语法分析器的原因是，你会发现，Go的编译过程中，词法分析和语法分析是放在一起的，在进行语法分析器初始化的过程中，其实也初始化了词法分析器，我们可以进入go fun中的syntax.Parse函数

func Parse(base *PosBase, src io.Reader, errh ErrorHandler, pragh PragmaHandler, mode Mode) (_ *File, first error) {
    defer func() {
        if p := recover(); p != nil {
            if err, ok := p.(Error); ok {
                first = err
                return
            }
            panic(p)
        }
    }()

    var p parser
    p.init(base, src, errh, pragh, mode) //初始化操作
    p.next() // 词法解析器对源文件进行解析，转换成全部由token组成的源文件
    return p.fileOrNil(), p.first //语法解析器对上边的token文件进行语法解析
}

可以看到调用了语法分析的初始化操作：

p.init(base, src, errh, pragh, mode)

进入到p.init中去，我们会看见这么一行代码，它就是对词法分析器的初始化

p.scanner.init(...这里是初始化词法分析器的参数)

可以看到语法分析器是用的p.scanner调用词法分析器的init方法。看一下语法分析器的结构就明白了，在语法分析器的结构体中，嵌入了词法分析器的结构体（本文内容主要是介绍词法分析器，所以在这里先不介绍语法分析器的各个结构体字段的含义，在介绍语法分析的文章中会详细介绍）

//语法分析结构体
type parser struct {
    file  *PosBase 
    errh  ErrorHandler
    mode  Mode
    pragh PragmaHandler
    scanner //嵌入了词法分析器

    base   *PosBase 
    first  error 
    errcnt int  
    pragma Pragma  

    fnest  int
    xnest  int 
    indent []byte
}

搞清楚了语法分析和词法分析的关系，下边就开始看词法分析的具体过程

词法分析过程

词法分析的代码位置在：

src/cmd/compile/internal/syntax/scanner.go

词法分析器是通过一个结构体来实现的，它的结构如下：

type scanner struct {
    source //source也是一个结构体，它主要记录的是要进行词法分析的源文件的信息，比如内容的字节数组，当前扫描到的字符以及位置等（因为我们知道词法分析过程是对源文件进行从左往右的逐字符扫描的）
    mode   uint  //控制是否解析注释
    nlsemi bool // if set '\n' and EOF translate to ';'

    // current token, valid after calling next()
    line, col uint   //当前扫描的字符的位置，初始值都是0
    blank     bool // line is blank up to col（词法分析过程中用不到，语法分析过程会用到）
    tok       token // 当前匹配出来的字符串对应的TOKEN（记录了Go中支持的所有Token类型）
    lit       string   // Token的源代码文本表示，比如从源文件中识别出了if，那它的TOKEN就是_If，它的lit就是if
    bad       bool     // 如果出现了语法错误，获得的lit可能就是不正确的
    kind      LitKind  // 如果匹配到的字符串是一个值类型，这个变量就是标识它属于哪种值类型，比如是INT还是FLOAT还是RUNE类型等
    op        Operator // 跟kind差不多，它是标识识别出的TOKEN如果是操作符的话，是哪种操作符）
    prec      int      // valid if tok is _Operator, _AssignOp, or _IncOp
}

type source struct {
    in   io.Reader
    errh func(line, col uint, msg string)

    buf       []byte // 源文件内容的字节数组
    ioerr     error  // 文件读取的错误信息
    b, r, e   int    // buffer indices (see comment above)
    line, col uint   // 当前扫描到的字符的位置信息
    ch        rune   // 当前扫描到的字符
    chw       int    // width of ch
}

知道了词法解析器的结构体各个字段的含义之后，下边了解一下Go中有哪些类型Token

Token

Token是编程语言中最小的具有独立含义的词法单元，Token主要包含关键字、自定义的标识符、运算符、分隔符、注释等，这些都可以在：src/cmd/compile/internal/syntax/tokens.go中看到，我下边截取了一部分(这些Token都是以常量的形式存在的)

const (
    _    token = iota
    _EOF       // EOF

    // names and literals
    _Name    // name
    _Literal // literal

    // operators and operations
    // _Operator is excluding '*' (_Star)
    _Operator // op
    _AssignOp // op=
    _IncOp    // opop
    _Assign   // =
    ......

    // delimiters
    _Lparen    // (
    _Lbrack    // [
    _Lbrace    // {
    _Rparen    // )
    _Rbrack    // ]
    _Rbrace    // }
    ......

    // keywords
    _Break       // break
    _Case        // case
    _Chan        // chan
    _Const       // const
    _Continue    // continue
    _Default     // default
    _Defer       // defer
    ......

    // empty line comment to exclude it from .String
    tokenCount //
)

每个词法Token对应的词法单元，最重要的三个属性就是：词法单元类型、Token在源代码中的文本形式、Token出现的位置。注释和分号是两种比较特殊的Token，普通的注释一般不影响程序的语义，因此很多时候可以忽略注释（scanner结构体中的mode字段，就是标识是否解析注释）

所有的Token被分为四类：

1. 特殊类型的Token。比如：_EOF
2. 基础面值对应的Token。比如：IntLit、FloatLit、ImagLit等
3. 运算符。比如：Add* // +、Sub* // -、*Mul* // *
4. 关键字。比如：_Break* // break、_Case* // case

词法分析实现

在词法分析部分，包含两个核心的方法，一个是nextch()，一个是next()

我们知道，词法分析过程是从源文件中逐字符的读取，nextch()函数就是不断的从左往右逐字符读取源文件的内容

以下为nextch()函数的部分代码，它主要是获取下一个未处理的字符，并更新扫描的位置信息

func (s *source) nextch() {
redo:
    s.col += uint(s.chw)
    if s.ch == '\n' {
        s.line++
        s.col = 0
    }

    // fast common case: at least one ASCII character
    if s.ch = rune(s.buf[s.r]); s.ch < sentinel {
        s.r++
        s.chw = 1
        if s.ch == 0 {
            s.error("invalid NUL character")
            goto redo
        }
        return
    }

    // slower general case: add more bytes to buffer if we don't have a full rune
    for s.e-s.r < utf8.UTFMax && !utf8.FullRune(s.buf[s.r:s.e]) && s.ioerr == nil {
        s.fill()
    }

    // EOF
    if s.r == s.e {
        if s.ioerr != io.EOF {
            // ensure we never start with a '/' (e.g., rooted path) in the error message
            s.error("I/O error: " + s.ioerr.Error())
            s.ioerr = nil
        }
        s.ch = -1
        s.chw = 0
        return
    }

......
}

而next()函数，就是根据扫描的字符来通过上一篇中介绍的确定有穷自动机的思想，分割出字符串，并匹配相应的token。next()函数的部分核心代码如下：

func (s *scanner) next() {
    nlsemi := s.nlsemi
    s.nlsemi = false

redo:
    // skip white space
    s.stop()
    startLine, startCol := s.pos()
    for s.ch == ' ' || s.ch == '\t' || s.ch == '\n' && !nlsemi || s.ch == '\r' {
        s.nextch()
    }

    // token start
    s.line, s.col = s.pos()
    s.blank = s.line > startLine || startCol == colbase
    s.start()
    if isLetter(s.ch) || s.ch >= utf8.RuneSelf && s.atIdentChar(true) {
        s.nextch()
        s.ident()
        return
    }

    switch s.ch {
    case -1:
        if nlsemi {
            s.lit = "EOF"
            s.tok = _Semi
            break
        }
        s.tok = _EOF

    case '\n':
        s.nextch()
        s.lit = "newline"
        s.tok = _Semi

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

    case '"':
        s.stdString()
......
}

完整的描述这两个方法所做的事情就是：

1. 词法分析器每次通过nextch()函数来获取最新的未解析的字符
2. 根据扫描到的字符，next()函数会去判断当前扫描到的字符属于那种类型，比如当前扫描到了一个a字符，那么它就会去尝试匹配一个标识符类型，也就是next()函数中调用的s.ident()方法（并且会判断这个标识符是不是一个关键字）
3. 如果扫描到的字符是一个数字字符，那就会去尝试匹配一个基础面值类型（比如IntLit、FloatLit、ImagLit）
4. next()识别出一个token之后就会传递给语法分析器，然后语法分析器通过调用词法分析器的next()函数，继续获取下一个token（所以你会发现，词法分析器并不是一次性的将整个源文件都翻译成token之后，再提供给语法分析器，而是语法分析器自己需要一个就通过词法分析器的next()函数获取一个）

我们可以在next()函数中看到这么一行代码

for s.ch == ' ' || s.ch == '\t' || s.ch == '\n' && !nlsemi || s.ch == '\r' {
        s.nextch()
    }

它是过滤掉源文件中的空格、制表符、换行符等

关于它是如何识别出的一个字符串是基础面值，还是字符串的，可以看里边的ident()、number()、stdString()这些方法的内部实现，这里就不粘代码了，其实思想就是前一篇文章中介绍的确定有穷自动机

下边我从Go编译器的入口开始，画一下词法分析这一块的流程图，方便把介绍的内容串起来

可能看完源码之后，对词法解析器还是没有一个太清晰的了解。下边就通过Go为我们提供的测试文件或者标准库来实际的用一下词法分析器，看它到底是如何工作的

测试词法分析过程

测试词法分析有两种方式，你可以直接编译执行Go提供的词法分析器测试文件，或者Go提供的标准库

词法分析器测试文件地址：src/cmd/compile/internal/syntax/scanner_test.go
Go提供的词法分析器标准库地址：src/go/scanner/scanner.go

下边我会自己写一个源文件，并将它传递给词法分析器，看它是如何解析的，以及解析的结果是什么样的

通过测试文件测试词法分析器

我们可以直接编译执行src/cmd/compile/internal/syntax/scanner_test.go中的TestScanner方法，该方法的源码如下（代码中有注释）：

func TestScanner(t *testing.T) {
    if testing.Short() {
        t.Skip("skipping test in short mode")
    }

    filename := *src_ // can be changed via -src flag
    //这里你可以选择一个你自己想解析的源文件的绝对路径
    src, err := os.Open("/Users/shulv/studySpace/GolangProject/src/data_structure_algorithm/SourceCode/Token/aa.go")
    if err != nil {
        t.Fatal(err)
    }
    defer src.Close()

    var s scanner
    s.init(src, errh, 0) //初始化词法解析器
    for {
        s.next() //获取token（next函数里边会调用nextch()方法，不断获取下一个字符，直到匹配到一个token）
        if s.tok == _EOF {
            break
        }
        if !testing.Verbose() {
            continue
        }
        switch s.tok { //获取到的token值
        case _Name, _Literal: //标识符或基础面值
            //打印出文件名、行、列、token以及token对应的源文件中的文本
            fmt.Printf("%s:%d:%d: %s => %s\n", filename, s.line, s.col, s.tok, s.lit)
        case _Operator:
            fmt.Printf("%s:%d:%d: %s => %s (prec = %d)\n", filename, s.line, s.col, s.tok, s.op, s.prec)
        default:
            fmt.Printf("%s:%d:%d: %s\n", filename, s.line, s.col, s.tok)
        }
    }
}

该测试函数首先会打开你的源文件，将源文件的内容传递给词法分析器的初始化函数。然后通过一个死循环，不断的去调用next()函数获取token，直到遇到结束符_EOF，则跳出循环

我要给词法解析器解析的文件内容如下：

package Token

import "fmt"

func testScanner()  {
    a := 666
    if a == 666 {
        fmt.Println("Learning Scanner")
    }
}

然后通过以下命令来将测试方法跑起来（你可以打印更多的信息，sacnner结构体的字段，你都可以打印出来看看）：

# cd /usr/local/go/src/cmd/compile/internal/syntax
# go test -v -run="TestScanner"

打印结果：
=== RUN   TestScanner
parser.go:1:1: package
parser.go:1:9: name => Token
parser.go:1:14: ;
parser.go:3:1: import
parser.go:3:8: literal => "fmt"
parser.go:3:13: ;
parser.go:5:1: func
parser.go:5:6: name => testScanner
parser.go:5:17: (
parser.go:5:18: )
parser.go:5:21: {
parser.go:6:2: name => a
parser.go:6:4: :=
parser.go:6:7: literal => 666
parser.go:6:10: ;
parser.go:7:2: if
parser.go:7:5: name => a
parser.go:7:7: op => == (prec = 3)
parser.go:7:10: literal => 666
parser.go:7:14: {
parser.go:8:3: name => fmt
parser.go:8:6: .
parser.go:8:7: name => Println
parser.go:8:14: (
parser.go:8:15: literal => "Learning Scanner"
parser.go:8:33: )
parser.go:8:34: ;
parser.go:9:2: }
parser.go:9:3: ;
parser.go:10:1: }
parser.go:10:2: ;
--- PASS: TestScanner (0.00s)
PASS
ok      cmd/compile/internal/syntax    0.007s

通过标准库测试词法分析器

另一种测试方法就是通过Go提供的标准库，我这里演示一下如何用标准库中的方法来测试词法分析器

你需要写一段代码来调用标准库中的方法，来实现一个词法分析过程，示例如下：

package Token

import (
    "fmt"
    "go/scanner"
    "go/token"
)

func TestScanner1()  {
    src := []byte("cos(x)+2i*sin(x) //Comment") //我要解析的内容（当然你也可以用一个文件内容的字节数组）
    //初始化scanner
    var s scanner.Scanner
    fset := token.NewFileSet() //初始化一个文件集（我在下边会解释这个）
    file := fset.AddFile("", fset.Base(), len(src)) //向字符集中加入一个文件
    s.Init(file, src, nil, scanner.ScanComments) //第三个参数是mode，我传的是ScanComments，表示需要解析注释，一般情况下是可以不解析注释的
    //扫描
    for  {
        pos, tok, lit := s.Scan() //就相当于next()函数
        if tok == token.EOF {
            break
        }
        fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit) //fset.Position(pos)：获取位置信息
    }
}

执行以上代码，得到如下结果：

1:1     IDENT   "cos"
1:4     (       ""
1:5     IDENT   "x"
1:6     )       ""
1:7     +       ""
1:8     IMAG    "2i"
1:10    *       ""
1:11    IDENT   "sin"
1:14    (       ""
1:15    IDENT   "x"
1:16    )       ""
1:18    ;       "\n"
1:18    COMMENT "//Comment"

你会发现标准库中使用的方法和测试文件中的完全不一样。这是因为标准库中是单独的实现了一套词法分析器，而并没有去复用go编译中词法分析器的代码，我理解这是因为go编译器中的代码是不能否作为公用的方法给外部使用的，出于安全考虑，它里边的方法必须保持私有

如果你去看标准库中词法分析器的实现，发现和go编译中的实现不太一样，但是核心思想是一样的（比如字符的扫描、token的识别）。不一样的地方在于要解析的文件的处理，我们知道，在Go语言中，由多个文件组成包，然后多个包链接为一个可执行文件，所以单个包对应的多个文件可以看作是Go语言的基本编译单元。因此Go提供的词法解析器中还定义了FileSet和File对象，用于描述文件集和文件

type FileSet struct {
    mutex sync.RWMutex // protects the file set
    base  int          // base offset for the next file
    files []*File      // list of files in the order added to the set
    last  *File        // cache of last file looked up
}

type File struct {
    set  *FileSet
    name string // file name as provided to AddFile
    base int    // Pos value range for this file is [base...base+size]
    size int    // file size as provided to AddFile

    // lines and infos are protected by mutex
    mutex sync.Mutex
    lines []int // lines contains the offset of the first character for each line (the first entry is always 0)（行包含每行第一个字符的偏移量（第一个条目始终为0））
    infos []lineInfo
}

作用其实就是记录解析的文件的信息的，就和词法解析器scanner结构体中的source结构体作用差不多，区别就是，我们知道go编译器是创建多个协程并发的对多个文件进行编译，而标准库中通过文件集来存放多个待解析的文件，你会发现FileSet的结构体中有一个存放待解析文件的一维数组

下边简单的介绍一下FileSet和File的关系，以及它是如何计算出Token的位置信息的

FileSet和File

FileSet和File的对应关系如图所示：

图片来源：go-ast-book

图中Pos类型表示数组的下标位置。FileSet中的每个File元素对应底层数组的一个区间，不同的File之间没有交集，相邻的File之间可能存在填充空间

每个File主要由文件名、base和size三个信息组成。其中base对应File在FileSet中的Pos索引位置，因此base和base+size定义了File在FileSet数组中的开始和结束位置。在每个File内部可以通过offset定位下标索引，通过offset+File.base可以将File内部的offset转换为Pos位置。因为Pos是FileSet的全局偏移量，反之也可以通过Pos查询对应的File，以及对应File内部的offset

而词法分析的每个Token位置信息就是由Pos定义，通过Pos和对应的FileSet可以轻松查询到对应的File。然后在通过File对应的源文件和offset计算出对应的行号和列号（实现中File只是保存了每行的开始位置，并没有包含原始的源代码数据）。Pos底层是int类型，它和指针的语义类似，因此0也类似空指针被定义为NoPos，表示无效的Pos

来源：go-ast-book

通过FileSet和File的关系能看出来，Go标准库中的词法分析器通过文件集的这种方式，来实现对多个源文件的解析

本文主要是从Go编译的入口文件开始，逐步的介绍了go编译中词法分析的源码部分实现，并且通过测试文件和Go提供的词法分析器标准库，对词法分析器进行了实际的测试和使用。相信看完之后能对Go的词法分析过程，有个比较清晰的认识

词法分析部分比较简单，涉及的核心内容较少，真正难的在后边的语法分析和抽象语法树部分，感兴趣的小伙伴请继续关注