3.3 完善词法解析器

以最小µGo程序为例，本节讨论如何继续完善词法解析器，为后续的语法解析器提供基础。

3.3.1 Token视角的µGo程序

英语和中文有着极大的区别：英语由少量的26个字母构成，然后由字母再构造成一个个单词，而这些单词和中文的一个个汉字类似，每个单词都有着一定的语义。词法分析的工作和英语中从字母序列分析为单词序列的工作类似（中文应为汉字数量众多，词法解析的比重相对较低）。我们看到的程序其实都是字母序列，因此第一步工作是将字母序列转换为单词序列。

而µGo编译器中每个单词对应属于Token，一个Token可以是一个数字、也可以是一个变量名，或者是一个加法符号。我们现在以Token视角看看之前的µGo程序是什么样子的。

最小µGo程序的字母序列（为了不被语法高亮的特性迷惑，这里刻意关闭了语法高亮特性）：

package main

func main() {
	exit(40+2) // 退出码 42
}

对应的Token序列如下（忽略注释部分）：

import "github.com/wa-lang/ugo/token"

var ugoTokens = []token.Token {
	{Type: token.PACKAGE},              // package
	{Type: token.IDENT, Value: "main"}, // main
	{Type: token.FUNC},                 // func
	{Type: token.IDENT, Value: "main"}, // main
	{Type: token.LPAREN},               // (
	{Type: token.RPAREN},               // )
	{Type: token.LBRACE},               // {
	{Type: token.IDENT, Value: "exit"}, // exit
	{Type: token.LPAREN},               // (
	{Type: token.NUMBER, Value: 40},    // 40
	{Type: token.ADD},                  // +
	{Type: token.NUMBER, Value: 2},     // 2
	{Type: token.RPAREN},               // )
	{Type: token.RBRACE},               // }
}

这种转化也就是此法解析器需要完成的工作：我们需要在能够尽量准确表达原始程序的前提下尽量简化后续解析器的分析工作。目前看，这个词法序列似乎是可以准确表示最小µGo程序的。

3.3.2 分号和注释

我们尝试再从Token序列反向恢复出原始的µGo程序：

package main func main() { exit(40+2) }

实际上这是个错误的Go程序，将会产生以下的语法错误：

syntax error: unexpected func, expecting semicolon or newline

简单说，在package main和func之间至少要有一个换行符号或则是分号。其实语法解析器最终需要的是分号，因为分号才是Go语言中语句的分隔符号（正如空白也是单词之间的分隔符）。而Go语言的词法解析起在解析时如果是特殊的Token遇到换行（标识符、数字或字符串等字面值、break/continue/fallthrough/return等关键字、++/--/)/]/}等运算符，同时)/}之前的分号可以省略，具体请参考 spec 文档），会自动添加分号。

同样，注释是可以以任意的形式混入在Token序列之间的。如果加入注释的干扰，会导致语法的定义和分析变得复杂。常见的做法是词法解析的同时记录每个Token的位置信息，词法解析完成后将注释剥离再进行语法解析，等语法解析器完成AST构造之后再将注释根据位置合并到AST的相应结点中。

3.3.3 完善token包的记号类型

token包的内容和第2章结构类似，增加了部分新的关键字类型：

package token

// 记号类型
type TokenType int

// ch3中 µGo程序用到的记号类型
const (
	EOF TokenType = iota
	ERROR
	COMMENT

	IDENT
	NUMBER

	PACKAGE
	FUNC

	ADD // +
	SUB // -
	MUL // *
	DIV // /

	LPAREN // (
	RPAREN // )
	LBRACE // {
	RBRACE // }

	SEMICOLON // ;
)

增加了IDENT表示标识符、PACKAGE定义包、FUNC针对函数大括弧用于定义函数的Body、并引入了分号。如果是语法位置记号用ERROR表示，EOF表示文件结束。同时增加了COMMENT表示注释。

token.Token对应记号的值（含记号类型、解析后的值、位置和原始面值）：

type Token struct {
	Type    TokenType   // 记号的类型
	Value   interface{} // 记号的值, 目前只有 int
	Pos     int         // 记号所在的位置(从1开始)
	Literal string      // 程序中原始的字符串
}

这样我们就可以用[]token.Token表示的记号序列来等价地表示词法解析后的代码。

3.3.4 重构词法解析器

在地2章最后的例子中，我们通过包装text/scanner标准库实现了词法解析。这种方式虽然可以用于µGo程序，但是依然有隔山打牛的弊端。本节我们该用纯手工的方式重新实现词法解析，这样不仅仅可以让我们可以了解词法解析的实现细节，而且词法解析的套路依然可以用于后续的AST解析工作。这种问题只要彻底解决一次就一劳永逸了。

3.3.4.1 源文件SourceStream

词法解析的输入是字节流，在解析的过程中常常需要向前多看一个字符，同时也可能要忽略一些字符，为此我们需要先构造一个字节流的SourceStream对象（这个设计同样可以复制到Token流，用于语法解析）。

SourceStream定义的API如下：

type SourceStream struct {}

func NewSourceStream(name, src string) *SourceStream

func (p *SourceStream) Name() string
func (p *SourceStream) Input() string

func (p *SourceStream) Pos() int
func (p *SourceStream) Peek() rune
func (p *SourceStream) Read() rune
func (p *SourceStream) Unread()

func (p *SourceStream) Accept(valid string) bool
func (p *SourceStream) AcceptRun(valid string) (ok bool)

func (p *SourceStream) EmitToken() (lit string, pos int)
func (p *SourceStream) IgnoreToken()

NewSourceStream根据文件名和内容构造一个SourceStream对象。其Name和Input方法分别返回源文件的名字和内容。Pos方法返回当前读的位置，Peek预取下一个字符、Read读取下一个字符、Unread用于一次回退。Accept会尝试消费一个存在于valid中的字符，而AcceptRun则会尝试尽量消费多个存在于valid中的字符。EmitToken方法用于产生当前读取到的记号面值和位置信息，IgnoreToken则忽略当前的记号。

SourceStream中最基础的核心函数Read和Unread实现如下：

type SourceStream struct {
	name  string // 文件名
	input string // 输入的源代码
	start int    // 当前正解析中的记号的开始位置
	pos   int    // 当前读取的位置
	width int    // 最后一次读取utf8字符的字节宽度, 用于回退
}

func (p *SourceStream) Read() rune {
	if p.pos >= len(p.input) {
		p.width = 0
		return 0
	}

	r, size := utf8.DecodeRune([]byte(p.input[p.pos:]))
	p.width = size
	p.pos += p.width
	return r
}
func (p *SourceStream) Unread() {
	p.pos -= p.width
	return
}

Read方法会解码并读一个utf8字符，其中p.width用于记录当前读取字符的utf8编码的字节宽度，如果遇到结尾则返回0。Unread方法则可以用于进行一次回退刚刚读取的Read操作（不能进行多次回退）。

基于Read和Unread可以很容易实现Peek、Accept和AcceptRun等方法：

func (p *SourceStream) Peek() rune {
	x := p.Read()
	p.Unread()
	return x
}
func (p *SourceStream) Accept(valid string) bool {
	if strings.IndexRune(valid, rune(p.Read())) >= 0 {
		return true
	}
	return false
}

func (p *SourceStream) AcceptRun(valid string) (ok bool) {
	for p.Accept(valid) {
		ok = true
	}
	p.Unread()
	return
}

Peek等方法先用Read进行正常读取，如果失败则调用Unread回退最近一次的Read操作。

最后是产生记号面值的实现：

func (p *SourceStream) EmitToken() (lit string, pos int) {
	lit, pos = p.input[p.start:p.pos], p.start
	p.start = p.pos
	return
}

func (p *SourceStream) IgnoreToken() {
	_, _ = p.EmitToken()
}

EmitToken返回的记号面值和位置是构造token.Token的必要数据。

3.3.4.2 基于SourceStream重构词法解析器

词法解析器的API定义如下：

type Lexer struct {}

func NewLexer(name, input string) *Lexer
func (p *Lexer) Comments() []token.Token
func (p *Lexer) Tokens() []token.Token

NewLexer基于源文件名和内容构造解析器，Comments方法返回注释列表，Tokens方法返回非注释列表。

Lexer基于SourceStream对象构建：

type Lexer struct {
	*SourceStream
	tokens   []token.Token
	comments []token.Token
}

func NewLexer(name, input string) *Lexer {
	p := &Lexer{ SourceStream: NewSourceStream(name, input)}
	p.run()
	return p
}

func (p *Lexer) Tokens() []token.Token {
	return p.tokens
}

func (p *Lexer) Comments() []token.Token {
	return p.comments
}

NewLexer在构造Lexer对象后，调用私有的p.run函数将源代码解析为词法列表。

在实现词法解析之前先定义一个emit方法用于产生记号，实现如下：

func (p *Lexer) emit(typ token.TokenType) {
	lit, pos := p.EmitToken()
	if typ == token.IDENT {
		typ = token.Lookup(lit)
	}
	p.tokens = append(p.tokens, token.Token{
		Type:    typ,
		Literal: lit,
		Pos:     pos,
	})
}

手写通过p.EmitToken()调用内部SourceStream对象提供的方法，然后构造新的token.Token对象并添加到p.tokens列表。如果是标识符类型，则通过token.Lookup(lit)查询是否为关键字类型。

我们还需要一个产生注释记号的emitComment方法：

func (p *Lexer) emitComment() {
	lit, pos := p.EmitToken()
	p.comments = append(p.comments, token.Token{
		Type:    token.COMMENT,
		Literal: lit,
		Pos:     pos,
	})
}

注释也是一种token.Token，只是记录到了另一个p.comments成员中。将注释分开的原因是为了屏蔽注释对正常词法流的干扰，例如在遇到换行需要决策是否添加分号时注释会带来噪声。

我们还需要一个错误处理函数记录不能识别的记号：

func (p *Lexer) errorf(format string, args ...interface{}) {
	tok := token.Token{
		Type:    token.ERROR,
		Literal: fmt.Sprintf(format, args...),
		Pos:     p.Pos(),
	}
	p.tokens = append(p.tokens, tok)
	panic(tok)
}

错误也是一种特殊的记号，添加到p.tokens成员，然后调用panic抛出异常快速退出到外层函数。

最后也是最重要的run方法解析记号：

func (p *Lexer) run() (tokens []token.Token) {
	defer func() {
		tokens = p.tokens
		if r := recover(); r != nil {
			if _, ok := r.(token.Token); !ok {
				panic(r)
			}
		}
	}()
	...

首先是在defer函数中捕获errorf方法抛出的异常。词法解析的具体工作在一个for循环进行：

	for {
		r := p.Read()
		if r == rune(token.EOF) {
			p.emit(token.EOF)
			return
		}

		switch {
		case r == '\n':
		case isSpace(r):
		...
		}
	}
}

每次循环开始读取一个字符，判断如果是结束则产生EOF类型的记号并退出。否则通过switch多分枝分别解析不同类型的记号。

比如遇到换行时解析方式如下：

		case r == '\n':
			p.IgnoreToken()
			if len(p.tokens) > 0 {
				switch p.tokens[len(p.tokens)-1].Type {
				case token.RPAREN, token.IDENT, token.NUMBER:
					p.emit(token.SEMICOLON)
				}
			}

首先是通过p.IgnoreToken()忽略换行前读取的内容。然后判断是否已经读取到过记号，如果是并且前一个读取的记号是右小括弧、数字或标识符等类型时插入一个分号记号（类似Go语言可以省略大部分的行尾分号特性）。

如果是空白字符，则直接忽略：

		case isSpace(r):
			p.IgnoreToken()

如果是英文字母则尝试解析为标识符或关键字：

		case isAlpha(r):
			p.Unread()
			for {
				if r := p.Read(); !isAlphaNumeric(r) {
					p.Unread()
					p.emit(token.IDENT)
					break
				}
			}

数字的解析如下：

		case ('0' <= r && r <= '9'): // 123, 1.0
			p.Unread()

			digits := "0123456789"
			p.AcceptRun(digits)
			p.emit(token.NUMBER)

如果是数字开头，则通过p.AcceptRun尽量读取多个数字字符，然后通过p.emit(token.NUMBER)产生数字记号。

四则运算符处理如下：

		case r == '+': // +, +=, ++
			p.emit(token.ADD)
		case r == '-': // -, -=, --
			p.emit(token.SUB)
		case r == '*': // *, *=
			p.emit(token.MUL)
		case r == '/': // /, //, /*, /=
			if p.Peek() != '/' {
				p.emit(token.DIV)
			}

加、减、乘目前都是单个字符，直接产生记号即可。除法要特殊一点，需要分别处理行注释的问题（多行注释暂不支持）：

		case r == '/': // /, //, /*, /=
			if p.Peek() != '/' {
				p.emit(token.DIV)
			} else {
				// line comment
				for {
					t := p.Read()
					if t == '\n' {
						p.Unread()
						p.emitComment()
						break
					}
					if t == rune(token.EOF) {
						p.emitComment()
						return
					}
				}
			}

如果是行注释直接读取到换行或文件末尾，需要注意的是在行注释结尾要判断是否要产生分号。

其他的特色记号如下：

		case r == '(':
			p.emit(token.LPAREN)
		case r == '{':
			p.emit(token.LBRACE)

		case r == ')':
			p.emit(token.RPAREN)
		case r == '}':
			p.emit(token.RBRACE)

		case r == ';':
			p.emit(token.SEMICOLON)

未知的记号直接抛出错误：

		default:
			p.errorf("unrecognized character: %#U", r)
			return
		}

run方法是词法解析的核心方法，虽然目前的处理相对粗糙，后续可以根据语法的提炼慢慢改进。

3.3.5 格式化位置信息

在词法解析的过程中我们已经记录了每个记号的偏移量信息。如果结合文件名和内容可以转换为更适合阅读的行列号位置信息。

可以定义PosString函数用于将偏移量转位行列信息：

package lexer

import gotoken "go/token"

func PosString(filename string, src string, pos int) string {
	fset := gotoken.NewFileSet()
	fset.AddFile(filename, 1, len(src)).SetLinesForContent([]byte(src))
	return fmt.Sprintf("%v", fset.Position(gotoken.Pos(pos+1)))
}

为了简单，我们直接借助了Go语言自带的token.FileSet实现此功能。需要注意点时，pos是从0开始的，转行列表时pos需要加1.

3.3.6 测试词法解析器

还是本章的最小µGo程序：

package main

func main() {
	exit(40 + 2) // exit code 42
}

词法解析程序如下：

import  "github.com/wa-lang/ugo/lexer"

func main() {
	// 构造词法解析器
	code := loadCode("../hello.ugo")
	lexer := lexpkg.NewLexer("../hello.ugo", code)

	// 遍历正常记号
	for i, tok := range lexer.Tokens() {
		fmt.Printf(
			"%02d: %-12v: %-20q // %s\n",
			i, tok.Type, tok.Literal,
			lexpkg.PosString("../hello.ugo", code, tok.Pos),
		)
	}

	fmt.Println("----")

	// 遍历注释
	for i, tok := range lexer.Comments() {
		fmt.Printf(
			"%02d: %-12v: %-20q // %s\n",
			i, tok.Type, tok.Literal,
			lexpkg.PosString("../hello.ugo", code, tok.Pos),
		)
	}
}

输出的结果如下：

00: PACKAGE     : "package"            // ../hello.ugo:1:1
01: IDENT       : "main"               // ../hello.ugo:1:9
02: SEMICOLON   : ""                   // ../hello.ugo:2:1
03: FUNC        : "func"               // ../hello.ugo:3:1
04: IDENT       : "main"               // ../hello.ugo:3:6
05: LPAREN      : "("                  // ../hello.ugo:3:10
06: RPAREN      : ")"                  // ../hello.ugo:3:11
07: LBRACE      : "{"                  // ../hello.ugo:3:13
08: IDENT       : "exit"               // ../hello.ugo:4:2
09: LPAREN      : "("                  // ../hello.ugo:4:6
10: NUMBER      : "40"                 // ../hello.ugo:4:7
11: ADD         : "+"                  // ../hello.ugo:4:10
12: NUMBER      : "2"                  // ../hello.ugo:4:12
13: RPAREN      : ")"                  // ../hello.ugo:4:13
14: SEMICOLON   : ""                   // ../hello.ugo:5:1
15: RBRACE      : "}"                  // ../hello.ugo:5:1
16: EOF         : ""                   // ../hello.ugo:5:3
----
00: COMMENT     : "// exit code 42\n"  // ../hello.ugo:4:15

输出的记号不仅仅有记号类型、记号面值、还有行列号位置信息（在VSCode环境可通过鼠标点击位置实现跳转），位置信息非常有助于调试定位问题。

至此，我们我们实现了将µGo程序的字符流转化为了正常记号和注释记号的两个词法流。

© 2021-2022 | 柴树杉 保留所有权利