ugo-lab1-最小uGo程序

最小µGo程序

最小µGo程序代码如下：

package main

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

简易词法分析

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

在管理 token 之前，我们需要创建一个类来管理字节流

• 词法解析的输入是字节流，在解析的过程中常常需要向前多看一个字符，同时也可能要忽略一些字符
• 为此我们需要先构造一个字节流的 SourceStream 对象

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

SourceStream 的基础函数：

func NewSourceStream(name, src string) *SourceStream { // 构造一个SourceStream对象
	return &SourceStream{name: name, input: src}
}

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:])) // 解压缩第一个UTF-8编码并返回字符及其宽度
	p.width = size
	p.pos += p.width
	return r
}

func (p *SourceStream) Unread() {
	p.pos -= p.width
	return
}

• NewSourceStream：根据文件名和内容构造一个 SourceStream 对象
• Read：解码并读一个 utf-8 字符，其中 p.width 用于记录当前读取字符的 utf-8 编码的字节宽度，如果遇到结尾则返回 “0”
• Unread：用于回退一次刚刚读取的 Read 操作（不能进行连续多次回退）

核心函数用于记录 token 的信息：

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

• EmitToken：返回 token 字符串以及其位置
• EmitToken 返回的 token 面值和位置是构造 token.Token 的必要数据

基于 SourceStream 对象构建的 Lexer 对象：

type Lexer struct {
	src      *SourceStream // 字节流对象
	tokens   []token.Token // token列表
	comments []token.Token // 注释列表
}

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

用于生成 token 的两个关键函数如下：

func (p *Lexer) emit(typ token.TokenType) { // 产生token
	lit, pos := p.src.EmitToken()
	if typ == token.IDENT {
		typ = token.Lookup(lit) // 查询是否为关键字类型
	}
	p.tokens = append(p.tokens, token.Token{Type: typ, Literal: lit, Pos: pos})
}

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

• emit：调用 EmitToken 获取 token 的面值和位置，生成 token 后直接 append 到 “token列表” 中
• emitComment：和 emit 类似的操作，只不过最后 append 到 “注释列表” 中

解析 token 的核心函数如下：

func (p *Lexer) run() (tokens []token.Token) {
	defer func() { // 捕获errorf方法抛出的异常
		tokens = p.tokens
		if r := recover(); r != nil {
			if _, ok := r.(token.Token); ok {
				panic(r)
			}
		}
	}()

	for {
		r := p.src.Read()
		if r == rune(token.EOF) {
			p.emit(token.EOF)
			return
		}
		switch {
		case r == '\n':
			p.src.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)
				}
			}
		case isSpace(r): // 空格
			p.src.IgnoreToken()
		case isAlpha(r): // 英文字母
			p.src.Unread()
			for {
				if r := p.src.Read(); !isAlphaNumeric(r) {
					p.src.Unread()
					p.emit(token.IDENT)
					break
				}
			}
		case ('0' <= r && r <= '9'): // 数字
			p.src.Unread()

			digits := "0123456789"
			p.src.AcceptRun(digits)
			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.src.Peek() != '/' { // 除
				p.emit(token.DIV)
			} else { // 单行注释
				for {
					t := p.src.Read()
					if t == '\n' {
						p.src.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
		}
	}
}

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

构造词法解析程序如下：

func main() {
	code, err := readSource("./hello.ugo")
	if err != nil {
		return
	}

	l := lexer.NewLexer("../hello.ugo", code)

	for i, tok := range l.Tokens() {
		fmt.Printf(
			"%02d: %-12v: %-20q // %s\n",
			i, tok.Type, tok.Literal,
			token.PosString("../hello.ugo", code, tok.Pos),
		)
	}
	fmt.Println("----")

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

测试脚本即是最小µGo程序：

package main

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

00: 5           : "package"            // ../hello.ugo:1:1
01: 3           : "main"               // ../hello.ugo:1:9
02: 35          : ""                   // ../hello.ugo:2:1
03: 8           : "func"               // ../hello.ugo:3:1
04: 3           : "main"               // ../hello.ugo:3:6
05: 30          : "("                  // ../hello.ugo:3:10
06: 31          : ")"                  // ../hello.ugo:3:11
07: 32          : "{"                  // ../hello.ugo:3:13
08: 3           : "exit"               // ../hello.ugo:4:5
09: 30          : "("                  // ../hello.ugo:4:9
10: 4           : "40"                 // ../hello.ugo:4:10
11: 17          : "+"                  // ../hello.ugo:4:12
12: 4           : "2"                  // ../hello.ugo:4:13
13: 31          : ")"                  // ../hello.ugo:4:14
14: 35          : ""                   // ../hello.ugo:5:1
15: 33          : "}"                  // ../hello.ugo:5:1
16: 0           : ""                   // ../hello.ugo:5:3
----
00: 2           : "// 退出码 42"          // ../hello.ugo:4:16

简易语法分析

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

管理 token 流使用了同 SourceStream 一样的方法，核心点就是定义了如下的类：

type TokenStream struct {
	filename string        // 文件名
	src      string        // 文件内容
	tokens   []token.Token // token列表
	comments []token.Token // 注释列表
	pos      int           // 当前读取的位置
	width    int           // 最后一次读取token的个数, 用于回退
}

TokenStream 的基础函数：

func NewTokenStream(filename, src string, tokens, comments []token.Token) *TokenStream {
	return &TokenStream{
		filename: filename,
		src:      src,
		tokens:   tokens,
		comments: comments,
	}
}

func (p *TokenStream) ReadToken() token.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() { // 回退一个token
	p.pos -= p.width
}

• NewTokenStream：构造一个 TokenStream 对象（token 列表和注释列表来自于词法分析）
• ReadToken：读取一个 token，其中 p.width 只能为 “1”，如果遇到结尾则返回 “0”
• UnreadToken：用于回退一次刚刚读取的 ReadToken 操作（不能进行连续多次回退）

基于 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 _, t := range expectTypes {
		if tok.Type == t {
			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)
	}
}

基于 TokenStream 对象构建的 Parser 对象：

type Parser struct {
	*TokenStream           // 包装token流对象
	file         *ast.File // 保存解析得到的AST语法树
	err          error     // 记录错误
}

函数 parseFile 的作用是解析文件，同时也是 ast 的根节点：

func (p *Parser) ParseFile() {
	p.file = &ast.File{
		Filename: p.Filename(),
		Source:   p.Source(),
	}

	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 循环中解析全局的对象

最小µGo程序中的全局对象只有函数，函数的 AST 结构如下：

// 全局函数/方法
type FuncDecl struct {
	Recv *FieldList // 传参类型
	Name *Ident     // 函数名
	Type *FuncType  // 返回类型
	Body *BlockStmt // 函数内的语句块
}

• 函数 AST 结构由函数名、传参类型、返回类型、函数内的语句块组成

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

	funcName := &ast.Ident{
		NamePos: tokFuncIdent.Pos,
		Name:    tokFuncIdent.Literal,
	}

	funcType := &ast.FuncType{
		Func: tokFunc.Pos,
	}

	return &ast.FuncDecl{
		Name: funcName,
		Type: funcType,
		Body: p.parseStmt_block(),
	}
}

• 函数 AST 节点的生成，需要先生成其子节点，在生成子节点的过程中又要生成子节点的子节点
• 这种递归生成 AST 的思路就是：递归下降解析法

对于每一个 AST 类型都需要对应的函数来生成子节点，通过子节点组合成自己的 AST 节点后返回

当然对于某个 AST 节点来说，可能会具有不同的类型，例如语句块的 AST 结构如下：

// 块语句
type BlockStmt struct {
	Lbrace int // '{'
	List   []Stmt
	Rbrace int // '}'
}

// 一个语句节点
type Stmt interface {
	Node
	stmt_type()
}

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
}

• 语句有多种类型，不同的类型需要不同的类进行描述：

var (
    ......
	_ Stmt = (*VarSpec)(nil)
	_ Stmt = (*FuncDecl)(nil)
	_ Stmt = (*BlockStmt)(nil)
	_ Stmt = (*ExprStmt)(nil)
	_ Stmt = (*AssignStmt)(nil)
    ......
)

• 使用类型断言为 Node 接口添加了一些实现类型