关于golang:Go编译原理系列3词法分析

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

本文次要蕴含以下内容：

Go 编译的入口文件，以及在编译入口文件中做了哪些事件
词法剖析处在 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 次要蕴含关键字、自定义的标识符、运算符、分隔符、正文等，这些都能够在：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 被分为四类：

非凡类型的 Token。比方：_EOF
根底面值对应的 Token。比方：IntLit、FloatLit、ImagLit等
运算符。比方：Add* // +、Sub* // -、*Mul* // *
关键字。比方：_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()
......
}

残缺的形容这两个办法所做的事件就是：

词法分析器每次通过 nextch()函数来获取最新的未解析的字符
依据扫描到的字符，next()函数会去判断以后扫描到的字符属于那种类型，比方以后扫描到了一个 a 字符，那么它就会去尝试匹配一个标识符类型，也就是 next()函数中调用的 s.ident()办法（并且会判断这个标识符是不是一个关键字）
如果扫描到的字符是一个数字字符，那就会去尝试匹配一个根底面值类型（比方IntLit、FloatLit、ImagLit）
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 的对应关系如图所示：

图片起源：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 的词法剖析过程，有个比拟清晰的意识

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

关于golang:Go编译原理系列3词法分析

前言

源码剖析

Go 的编译入口

词法剖析过程

Token

词法剖析实现

测试词法剖析过程

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

通过规范库测试词法分析器

FileSet 和 File

总结