• KusonStack一站式可编程配置技术栈(Go): https://github.com/KusionStack/kusion
• KCL 配置编程语言(Rust): https://github.com/KusionStack/KCLVM
• 凹语言™: https://github.com/wa-lang/wa

3.4 完善语法解析器

本章在前一章最小µGo程序产生的token.Token序列基础之上通过解析语法产生AST语法树。

3.4.1 最小µGo程序的词法序列

最小µGo程序如下：

package main

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

基于前一章的词法解析程序将产生以下的token.Token列表：

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

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

消费这个序列产生AST语法树是本节的目标。

3.4.2 TokenStream

这个token.Token列表和词法解析器要处理的字符列表并没有本质的区别，因此我们同样可以构造和源文件SourceStream类似的TokenStream对象简化语法的解析工作。

TokenStream的API如下：

type TokenStream struct {}

func NewTokenStream(tokens []token.Token) *TokenStream

func (p *TokenStream) PeekToken() token.Token
func (p *TokenStream) ReadToken() token.Token
func (p *TokenStream) UnreadToken()

func (p *TokenStream) AcceptToken(expectTypes ...token.TokenType) (tok token.Token, ok bool)
func (p *TokenStream) AcceptTokenList(expectTypes ...token.TokenType) (toks []token.Token, ok bool)

func (p *TokenStream) MustAcceptToken(expectTypes ...token.TokenType) (tok token.Token)
func (p *TokenStream) MustAcceptTokenList(expectTypes ...token.TokenType) (toks []token.Token)

NewTokenStream主要基于普通记号序列构造TokenStream对象（目前注释记号并不参与复杂的解析工作，暂时忽略）。PeekToken、ReadToken、UnreadToken分别是预取一个记号、读取一个记号和回退一个记号。AcceptToken尝试消费一个存在于expectTypes中的一个记号，而MustAcceptTokenList则会尝试尽量消费多个满足的记号，它们都返回成功获取的记号值。而MustAcceptToken和MustAcceptTokenList则必须至少成功消费一个满足的记号，否则将通过panic抛出错误（语法解析函数会捕获这类异常并转化为错误返回值）。

最基础的ReadToken和UnreadToken实现如下：

type TokenStream struct {
	tokens   []token.Token
	comments []token.Token
	pos      int
	width    int
}

func (p *TokenStream) ReadToken() token.Token {
	if p.pos >= len(p.tokens) {
		p.width = 0
		return token.Token{Type: token.EOF}
	}
	tok := p.tokens[p.pos]
	p.width = 1
	p.pos += p.width
	return tok
}

func (p *TokenStream) UnreadToken() {
	p.pos -= p.width
	return
}

ReadToken方法会解码并读一个记号，其中p.width用于控制UnreadToken回退操作，它们的实现方式和SourceStream的Read、Unread方法类似。

基于ReadToken和UnreadToken就可以很容易实现PeekToken等其他方法：

func (p *TokenStream) PeekToken() token.Token {
	tok := p.ReadToken()
	p.UnreadToken()
	return tok
}

func (p *TokenStream) AcceptToken(expectTypes ...token.TokenType) (tok token.Token, ok bool) {
	tok = p.ReadToken()
	for _, x := range expectTypes {
		if tok.Type == x {
			return tok, true
		}
	}
	p.UnreadToken()
	return tok, false
}

func (p *TokenStream) AcceptTokenList(expectTypes ...token.TokenType) (toks []token.Token, ok bool) {
	for {
		tok, ok := p.AcceptToken(expectTypes...)
		if !ok || tok.Type == token.EOF {
			return toks, len(toks) != 0
		}
		toks = append(toks, tok)
	}
}

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

为了简化错误处理，两个Must方法实现如下：

func (p *TokenStream) MustAcceptToken(expectTypes ...token.TokenType) (tok token.Token) {
	tok, ok := p.AcceptToken(expectTypes...)
	if !ok {
		panic(fmt.Errorf("expect %v, got %v", expectTypes, tok))
	}
	return tok
}

func (p *TokenStream) MustAcceptTokenList(expectTypes ...token.TokenType) (toks []token.Token) {
	toks, ok := p.AcceptTokenList(expectTypes...)
	if !ok {
		panic(fmt.Errorf("expect %v, got %v", expectTypes, tok))
	}
	return toks
}

通过panic可以轻松从多层递归嵌套的语法解析函数中返回，由外层函数将panic再转换为错误返回。

3.4.3 构造解析器Parser对象

Parser对象用于维护解析器内部状态，同时包装了词法解析器并在此基础上实现语法解析功能。Parser定义如下：

type Parser struct {
	filename string
	src      string

	*TokenStream
	file *ast.File
	err  error
}

Parser对象的filename和src对应文件名和文件内容，TokenStream用于包装记号流对象，file则用于保存解析得到的AST语法树，err用于记录错误。

为了统一产生错误，Parser还提供了一个errorf函数：

func (p *Parser) errorf(pos int, format string, args ...interface{}) {
	p.err = fmt.Errorf("%s: %s",
		lexer.PosString(p.filename, p.src, pos),
		fmt.Sprintf(format, args...),
	)
	panic(p.err)
}

将错误格式化之后保存到p.err，然后panic抛出异常。

解析文件通过ParseFile方法实现：

func (p *Parser) ParseFile() (file *ast.File, err error) {
	defer func() {
		if r := recover(); r != p.err {
			panic(r)
		}
		file, err = p.file, p.err
	}()

	tokens, comments := lexer.Lex(p.filename, p.src)
	for _, tok := range tokens {
		if tok.Type == token.ERROR {
			p.errorf(tok.Pos, "invalid token: %s", tok.Literal)
		}
	}

	p.TokenStream = NewTokenStream(p.filename, p.src, tokens, comments)
	p.parseFile()

	return
}

首先在defer函数捕获p.errorf产生的异常并作为错误返回。然后通过lexer.Lex将源文件解析为记号序列，并过滤其中的错误记号。有了正确的记号序列之后通过NewTokenStream构造TokenStream记号流读取对象。最后通过p.parseFile()进行文件语法树解析。

3.4.3.1 解析文件

解析语法树的过程和写Go代码的过程，根据语法结构对应解析即可：

func (p *Parser) parseFile() {
	p.file = &ast.File{}

	// package xxx
	p.file.Pkg = p.parsePackage()

	for {
		switch tok := p.PeekToken(); tok.Type {
		case token.EOF:
			return
		case token.ERROR:
			panic(tok)
		case token.SEMICOLON:
			p.AcceptTokenList(token.SEMICOLON)

		case token.FUNC:
			p.file.Funcs = append(p.file.Funcs, p.parseFunc())

		default:
			p.errorf(tok.Pos, "unknown token: %v", tok)
		}
	}
}

首先初始化p.file对象，然后通过p.parsePackage()解析package xxx对应的包定义。然后在for循环中解析全局的对象，目前我们只要处理func定义即可。在没一层选择递归入口的时候，首先通过p.PeekToken()预取一个记号，然后根据记号的类型选择不同的递归函数（因为是手写解析器，我们可以很容易向前看多个记号，实现一些更灵活的语法解析）。

目前只处理EOF、ERROR、SEMICOLON和FUNC等类型，其他未知的记号作为错误处理。对于FUNC分号，AcceptTokenList可以消费多个连续的分号。对于FUNC函数，通过p.parseFunc()解析，并将解析得到的函数添加到p.file.Funcs函数列表中。

3.4.3.2 解析包定义

包的解析非常简单：

func (p *Parser) parsePackage() *ast.Package {
	tokPkg := p.MustAcceptToken(token.PACKAGE)
	tokPkgIdent := p.MustAcceptToken(token.IDENT)

	return &ast.Package{
		PkgPos:  tokPkg.Pos,
		NamePos: tokPkgIdent.Pos,
		Name:    tokPkgIdent.Literal,
	}
}

通过MustAcceptToken方法强制匹配package和包名，然后返回。

3.4.3.3 解析函数

目前最小µGo程序只有一个main函数，没有函数参数和返回值，函数的解析也是比较直观的：

func (p *Parser) parseFunc() *ast.Func {
	// func main()
	tokFunc := p.MustAcceptToken(token.FUNC)
	tokFuncIdent := p.MustAcceptToken(token.IDENT)
	p.MustAcceptToken(token.LPAREN) // (
	p.MustAcceptToken(token.RPAREN) // )

	body := p.parseStmt_block()

	return &ast.Func{
		FuncPos: tokFunc.Pos,
		NamePos: tokFuncIdent.Pos,
		Name:    tokFuncIdent.Literal,
		Body:    body, // {}
	}
}

同样用MustAcceptToken方法一次强制匹配func、函数名、(、)，然后通过p.parseStmt_block()解析函数体。

3.4.3.4 解析Block

函数Body对应一个Block块语句，块语句内由N个语句组成（可以递归包含块语句），解析如下：

func (p *Parser) parseStmt_block() *ast.BlockStmt {
	block := &ast.BlockStmt{}

	tokBegin := p.MustAcceptToken(token.LBRACE) // {

Loop:
	for {
		switch tok := p.PeekToken(); tok.Type {
		case token.EOF:
			break Loop
		case token.ERROR:
			p.errorf(tok.Pos, "invalid token: %s", tok.Literal)
		case token.SEMICOLON:
			p.AcceptTokenList(token.SEMICOLON)

		case token.RBRACE: // }
			break Loop

		default:
			block.List = append(block.List, p.parseStmt_expr())
		}
	}

	tokEnd := p.MustAcceptToken(token.RBRACE) // }

	block.Lbrace = tokBegin.Pos
	block.Rbrace = tokEnd.Pos

	return block
}

块语句可能包含多个语句，因此通过for循环内实现解析。块内的子语句在switch的default分支解析：p.parseStmt_expr()解析一个表达式语句，并将结果添加到block.List子语句列表中。

函数返回前记得通过p.MustAcceptToken吃掉结尾的}记号。

3.4.3.5 解析表达式语句

表达式语句基于parseExpr方法实现：

func (p *Parser) parseStmt_expr() *ast.ExprStmt {
	return &ast.ExprStmt{
		X: p.parseExpr(),
	}
}

parseExpr方法用于解析一个表达式，在第2章已经详细讨论过，只要将返回值改造为AST的结构就可以，这里就不展开了。

3.4.3.6 ParseFile

为了方便使用，再包装一个ParseFile函数：

func ParseFile(filename, src string) (*ast.File, error) {
	p := NewParser(filename, src)
	return p.ParseFile()
}

函数风格和Go语言的go/parser包的ParseFile函数类似。

3.4.4 组装编译器

现在我们已经完成了语法树解析器的实现，只要对接上后端的编译代码就可以实现从µGo代码到本地可执行程序的编译工作了。

构造以下代码：

func main() {
	code := loadCode("./hello.ugo")
	f, err := parser.ParseFile("./hello.ugo", code)
	if err != nil {
		panic(err)
	}

	ll := new(compiler.Compiler).Compile(f)
	fmt.Print(ll)
}

func loadCode(filename string) string {
	data, err := os.ReadFile(filename)
	if err != nil {
		panic(err)
	}
	return string(data)
}

该程序将µGo代码输出为LLVM的汇编程序a.out.ll，然后结合clang编译为本地可执行程序并执行：

$ go run main.go > a.out.ll
$ clang -Wno-override-module ./a.out.ll ./builtin/_builtin.ll
$ ./a.out || echo $?
ugo_builtin_exit(42)
42

这样我们就实现了从最小µGo程序到可执行程序的编译工作。