警告⚠️：这将是一个又臭又长的系列教程，教程结束的时候，你将拥有一个除了性能差劲、扩展性差、标准库不完善之外，其他方面都和官方相差无几的 Lua 语言解释器。说白了，这个系列的教程实现的是一个玩具语言，仅供学习，无实用性。请谨慎 Follow，请谨慎 Follow，请谨慎 Follow。
这是本系列教程的第五篇，如果你没有看过之前的文章，请从头观看。
前言
语法分析算是 SLua 解释器中相对复杂的一个模块了，为了避免篇幅过长，我们将分成多篇来讲解，本文是第一部分。
有了上一节定义的一系列 AST 节点，本节可以开始定义 Parser 类型及其方法了。 Parser 以 Scanner 类型输出的 Token 序列作为输入，将其解析为一棵 AST。
使用方式
在实现之前，先来看一下在 Parser 完成之后，我们应该怎样来使用它：
// slua.go
package main
import (
"fmt"
"strings"
"github.com/ksco/SLua/parser"
"github.com/ksco/slua/scanner"
)
func main() {
defer func() {
if err := recover(); err != nil {
fmt.Println(err)
}
}()
r := strings.NewReader("local さよなら = 'Hello, 世界'")
s := scanner.New(r)
p := parser.New(s)
tree := p.Parse()
// do something with tree next...
}
可以看到，parser 导出了一个 New 函数，用于生成 Parser 实例，它接受一个 Scanner 类型的实例，以便在内部调用它的 Scan 方法来获得 Token 序列。Parser 类型有一个名为 Parse 的公共方法，这个方法所做的工作就是语法分析器的全部，它的返回值即我们需要的语法分析树(AST)。在后续的语义分析、代码生成阶段，我们都是通过遍历 AST 来完成工作的。
具体实现
下面就来看一下 parser 模块的具体实现。
Parser 类型定义
type Parser struct {
s *scanner.Scanner
module string
currentToken *scanner.Token
lookAheadToken *scanner.Token
}
下面我们来详细讲一下每个参数的作用。
- s：用于存储传进来的 Scanner 实例。
- module：与 Scanner 中的 module 模块作用相同，都是保存模块名称，用于报错。
- currentToken：存储当前所在位置的 Token。
- lookAheadToken：因为在解析过程中，有时需要“向前看一步”才能确定如何进行解析，所以我们需要存储当前位置的下一个 Token。
New 函数定义
New 函数的定义非常简单：
func New(s *scanner.Scanner) *Parser {
p := new(Parser)
p.s = s
p.module = "parser"
p.currentToken = scanner.NewToken()
p.lookAheadToken = scanner.NewToken()
return p
}
初始化时，currentToken 和 lookAheadToken 的类型都为 TokenEOF。
Parse 方法初探
在定义 Parse 方法之前，我们需要定义两个辅助性的私有方法来操作 currentToken 和 lookAheadToken 变量。函数定义如下：
func (p *Parser) nextToken() *scanner.Token {
if p.lookAheadToken.Category != scanner.TokenEOF {
p.currentToken = p.lookAheadToken.Clone()
p.lookAheadToken.Category = scanner.TokenEOF
} else {
p.currentToken = p.s.Scan()
}
return p.currentToken
}
func (p *Parser) lookAhead() *scanner.Token {
if p.lookAheadToken.Category == scanner.TokenEOF {
p.lookAheadToken = p.s.Scan()
}
return p.lookAheadToken
}
先来看 lookAhead 方法，它的逻辑是，如果 lookAheadToken 的类型为 TokenEOF，则说明其没有存储有效值，就调用 Scan 函数读取一个新的 Token 存储到 lookAheadToken 中，并将其返回。如果已经存储了有效值了，则直接返回。
而 nextToken 方法则用于读取下一个 Token 作为当前的 Token，将其存储于 currentToken 中，并返回。它的逻辑是，如果 lookAheadToken 的类型不是 TokenEOF，则说明之前调用过 lookAhead 函数，所以我们就直接读取它的值作为 currentToken，否则，就调用 Scan 方法来获取下一个 Token。
有了两个函数，我们就可以正式开始定义 Parse 函数了。上一节我们提到过，AST 的根节点为 Chunk，而 Chunk 的唯一子节点是 Block。所以，Parse 函数的定义其实非常简单：
func (p *Parser) Parse() syntax.SyntaxTree {
return p.parseChunk()
}
在实现 parseChunk 函数之前，我们先要介绍一下 parser 模块的错误处理方式，跟 scanner 模块相同，我们定义了满足 error 接口的 Error 类型来表示错误：
package parser
import (
"fmt"
"github.com/ksco/slua/scanner"
)
type Error struct {
module string
token *scanner.Token
str string
}
func (e *Error) Error() string {
return fmt.Sprintf("%v:%v:%v: '%v' %v", e.module, e.token.Line,
e.token.Column, e.token.String(), e.str)
}
func assert(cond bool, msg string) {
if !cond {
panic("lemon/parser internal error: " + msg)
}
}
此外，我们还定义了一个 assert 函数来表示断言。因为 Go 语言没有提供系统断言函数，所以就只能自己定义一个。
parseChunk 函数定义如下：
func (p *Parser) parseChunk() syntax.SyntaxTree {
block := p.parseBlock()
if p.nextToken().Category != scanner.TokenEOF {
panic(&Error{module: p.module, token: p.currentToken,
str: "expect <eof>"})
}
return &syntax.Chunk{Block: block}
}
因为 Chunk 的唯一子节点是一个 Block，所以我们首先调用 parseBlock 函数去解析它，如果源代码没有语法问题，则在解析完成后，Scanner 应该刚好解析到代码结尾，所以下一个 Token 的类型应该为 TokenEOF，如果不是，则说明代码存在语法错误，所以使用 panic 函数抛出错误。如果代码没有错误，我们将解析完成后得到的 Chunk 返回，这就是我们要得到的 AST 了。
在讨论怎样去解析 Block 之前，我们先看一下 Block 到底是什么。简单来说，Block 是一系列语句的集合。那么都在哪些情况下的语句集合算 Block 呢？首先，我们知道，整个程序是一个 Block。除此之外 ，以下列表中的 <block> 部分都属于 Block：
- do <block> end
- while <exp> do <block> end
- if <exp> then <block> end
- if <exp> then <block> elseif ...
- if <exp> then <block> else ...
根据上面的总结，我们可以得出一个结论：所有的 Block 结尾的下一个 Token 的类型必然是 TokenEOF、TokenEnd、TokenElseif、TokenElse 其中之一，我们可以根据这个信息来判断当前的 Block 是否结束。知道了这个方法，解析 Block 的工作就简单多了。接下来，我们就看一下 parseBlock 函数是如何工作的吧。
func (p *Parser) parseBlock() syntax.SyntaxTree {
block := &syntax.Block{}
for p.lookAhead().Category != scanner.TokenEOF &&
p.lookAhead().Category != scanner.TokenEnd &&
p.lookAhead().Category != scanner.TokenElseif &&
p.lookAhead().Category != scanner.TokenElse {
stmt := p.parseStatement()
if stmt != nil {
block.Stmts = append(block.Stmts, stmt)
}
}
return block
}
很容易理解吧，我们不断地判断下一个 Token 是不是 Block 的结束 Token 之一，如果不是，那就说明接下来碰到的是一个语句，我们就调用 parseStatement 函数来解析它，并将解析结果加入到 Block 节点的 Stmts 列表中，直到结束为止。
在 SLua 中，共有以下几种类型的语句(Statement)：空语句、Do 语句，While 循环语句，If 判断语句、Local 变量声明语句、其他语句。所以 parseStatement 的逻辑也非常简单，我们只需借助 lookhAhead 函数“往前看一步”：
- 如果看到的是分号，则说明是一个空语句，直接跳过，返回 nil。
- 如果看到的是 do，就调用 parseDoStatement 函数。
- 如果看到的是 while，就调用 parseWhileStatement 函数
- 剩下的同理...
parseStatement 函数的定义如下：
func (p *Parser) parseStatement() syntax.SyntaxTree {
switch p.lookAhead().Category {
case ";":
p.nextToken()
case scanner.TokenDo:
p.parseDoStatement()
case scanner.TokenWhile:
p.parseWhileStatement()
case scanner.TokenIf:
p.parseIfStatement()
case scanner.TokenLocal:
p.parseLocalStatement()
default:
p.parseOtherStatement()
}
return nil
}
本节就先说到这里，在下一节中，我们将继续介绍 parseStatement 函数中用到的各个函数的定义。
在第三篇关于词法分析的文章的最后部分，我简单提及了 Go 语言中进行单元测试的方法，但因为对词法分析器进行单元测试比较简单，所以没有详细展开，而是留给了读者自己去探索。但对语法分析器进行单元测试却比较麻烦，所以在语法分析器编写完成之后，我会单独写一篇文章对 parser 模块进行单元测试。
获取源代码
代码已托管到 Github 上：SLua，每一个阶段的代码我都会创建一个 release，你可以直接下载作为参照。虽然提供了源代码，但并不建议直接复制粘贴，因为这样学到的知识会很容易忘记。
如果你觉得这篇教程有帮助，请不要吝啬给文章点个喜欢，我会更加有动力将这个系列写下去。：）
网友评论