乐趣区

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

作者：

jiezi

在

前言

在上一篇文章中，介绍了词法剖析中的核心技术，有穷自动机（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的词法剖析过程，有个比拟清晰的意识

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

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章