go-lexer-词法分析

词法分析一般是编译器的第一部分,而且词法分析很简单,就是一个有限状态机.
开始词法分析的过程就是把源文件转换成一组预先定义好的token的过程.
这一组被统一表现的token之后会被送入语法分析器进行语法解析,这里我们主要关注如何进行词法分析.

做词法分析就几种方法:

直接使用工具比如lex.
使用更低一层的正则表达式.
使用状态动作,构造一个状态机.

而真正实现一个语言的话,使用工具没有什么错,但是问题是,很难获得正确的错误提示.
工具生成的错误处理很弱.而且需要学习另一门规则或特定的语法.生成的代码可能性能不好,难以优化,但是用工具可以非常简单实现词法分析.
早期编译器的设计阶段都会使用lex来做词法分析器,比如gcc和Go都是这么做的,但是到了后期一个真正生产化的语言可能不能依赖生成的代码,而需要做自己特定的修改和优化,所以自己实现一个词法分析器就显得比较重要了.

正则表达被人诟病的一个话题就是效率问题,比如perl拥有功能最强大的正则表达式,但是整个正则表达式引擎的效率却很低,Go在这方面牺牲了一些正则表达式的特性来保证正则表达式的效率不至于过低,但是正则表达式对于大量文本处理体现的弱势却是很明显的.因为可能我们要处理的状态其实不需要一个繁重的正则表达来解决.

其实实现一个词法分析器很简单,而且这种技能是基本不会变的,如果写过一次,以后都是同样的实现方式.

先看一下Go的实现,在Go的源码下面go/token/token.go目录里面是这么定义token的.

1 2	// Token is the set of lexical tokens of the Go programming language. type Token int

其实就是个枚举类型,对于每种类型的字面值都有对应的token.
实际上这个只能算是一个token的类型.


// The list of tokens.
const (
        // Special tokens
        ILLEGAL Token = iota
        EOF
        COMMENT

        literal_beg
        // Identifiers and basic type literals
        // (these tokens stand for classes of literals)
        IDENT  // main
        INT    // 12345
        FLOAT  // 123.45
        IMAG   // 123.45i
        CHAR   // 'a'
        STRING // "abc"
	// 省略
)

枚举所有可以碰到的token类型.

go/token/position.go 当中是关于token位置相关的定义.

// -----------------------------------------------------------------------------
// Positions

// Position describes an arbitrary source position
// including the file, line, and column location.
// A Position is valid if the line number is > 0.
//
type Position struct {
        Filename string // filename, if any
        Offset   int    // offset, starting at 0 
        Line     int    // line number, starting at 1   
        Column   int    // column number, starting at 1 (byte count)
}

这个很简单就是标示在文件中的位置,比较有意思的是Pos的定义type Pos int,这是位置标示的紧凑表示.接下来看看Pos和Position之间是如何转换的.

首先定义了一个FileSet,可以理解为把File的内容字节按顺序存放的一个大数组,而某个文件则属于数组的一个区间[base,base+size]中,base是文件的第一个字节在大数组中的位置,size是这个文件的大小,某个文件中的Pos是在[base,base+size]这个区间里的一个小标.

所以最后Pos能够压缩成一个整数来表示一个文件当中的位置,当需要使用的使用再从FileSet中转换出完整的Position对象.

go/token/serialize.go 是对FileSet序列化,这里就略过了.

所以整个go/token包只是对token的一些定义和转化,词法分析的部分在go/scanner当中.

scan的主流程如下,主体是一个switch case表示的状态机,
比如碰到字符那么扫描到不为字符为止就作为一个标识符,比如碰到数字那么可能按照扫描数字,然后向后看一次小数字再扫描数字,直到没有数字为止.
scan每次会返回一个被扫描的token,压缩表示的位置,和字面值的字符串,这样就能够把一个源文件转化成一个token的记号流,也就是tokenize或者lexical analysis的过程.

func (s *Scanner) Scan() (pos token.Pos, tok token.Token, lit string) {
scanAgain:
        s.skipWhitespace() 
        // current token start
        pos = s.file.Pos(s.offset)
        // determine token value
        insertSemi := false
        switch ch := s.ch; {
    /* 字符开头,开始扫描标识符 */
        case isLetter(ch):
                lit = s.scanIdentifier()
                if len(lit) > 1 {
                        // keywords are longer than one letter - avoid lookup otherwise
                        tok = token.Lookup(lit)
                        switch tok {
                        case token.IDENT, token.BREAK, token.CONTINUE, token.FALLTHROUGH, token.RETURN:
                                insertSemi = true
                        }
                } else {
                        insertSemi = true
                        tok = token.IDENT
                } 
    /* 数字开头,扫描数字 */
        case '0' <= ch && ch <= '9':
                insertSemi = true
                tok, lit = s.scanNumber(false)
        default:

1
2
3

看一下例子的结果.


func ExampleScanner_Scan() {
        // src is the input that we want to tokenize.
    // 需要记号化的源文件
        src := []byte("cos(x) + 1i*sin(x) // Euler")

        // Initialize the scanner.
        var s scanner.Scanner
        fset := token.NewFileSet()                      // positions are relative to fset
    // 添加到文件集合中
        file := fset.AddFile("", fset.Base(), len(src)) // register input "file"
    // 初始化scanner
        s.Init(file, src, nil /* no error handler */, scanner.ScanComments)

        // Repeated calls to Scan yield the token sequence found in the input.
        for {
                pos, tok, lit := s.Scan()
                if tok == token.EOF {
                        break
                }
                fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
        }
    // 不断扫描就能得到如下结果
    // 词法分析就是做这样一件事情.
        // output:
        // 1:1  IDENT   "cos"
        // 1:4  (       ""
        // 1:5  IDENT   "x"
        // 1:6  )       ""
        // 1:8  +       ""
        // 1:10 IMAG    "1i"
        // 1:12 *       ""
        // 1:13 IDENT   "sin"
        // 1:16 (       ""
        // 1:17 IDENT   "x"
        // 1:18 )       ""
        // 1:20 ;       "\n"
        // 1:20 COMMENT "// Euler"
}

```

我在我的数据结构字符画生成工具[1]里面就实现了一个词法分析器,方便我用简单的语法构造一个字符画,然后插入到注释中辅助解释.
唯一的不同的是,我使用了channel读取token记号,来增加并发,而go本身的记号化是串行的,当然,这点区别其实没有多大,而且这个设计
在Go的模板包里面使用了,Rob Pike也有过相关的演讲[2].

1.  https://github.com/ggaaooppeenngg/cpic/blob/master/lex.go
2.  http://cuddle.googlecode.com/hg/talk/lex.html#landing-slide