警告⚠️：这将是一个又臭又长的系列教程，教程结束的时候，你将拥有一个除了性能差劲、扩展性差、标准库不完善之外，其他方面都和官方相差无几的 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，你可以直接下载作为参照。虽然提供了源代码，但并不建议直接复制粘贴，因为这样学到的知识会很容易忘记。

如果你觉得这篇教程有帮助，请不要吝啬给文章点个喜欢，我会更加有动力将这个系列写下去。：）