# 准备冻手

理论讲那么多，想必大家也犯困了，马上就到冻手环节了，本节我们会实现一个支持括号的四则表达式编译器 & AST 解释器，用以验证我们所学习的知识。

# EBNF 文法

这里把本节代码所参考的 EBNF 文法贴上。

1
2
3
4
5
6
7
exp = addexp
addexp = mulexp {oper2 mulexp}
oper2 = '+' | '-'
mulexp = parenexp {oper1 parenexp}
oper1 = '*' | '/'
parenexp = '(' addexp ')' | numexp
numexp = number

我们在上节文法的基础上稍作修改，支持了括号。

# AST

在编写语法分析器之前，我们需要先定义好每个 AST 节点 (符号) 的结构。

\ToyLang\ast\exp.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#ifndef AST_EXP_H_
#define AST_EXP_H_

#include <vector>
#include <memory>

#include "lexer/token.h"

namespace toylang {

enum class ExpType {
    kAdd,
    kMul,
    kNum,
    kParen,
};

// 表达式抽象基类
struct Exp {
public:
    virtual ExpType GetType() const noexcept = 0;
};

// 加法表达式节点
struct MulExp;
struct AddExp : public Exp {
public:
    virtual ExpType GetType() const noexcept;

    AddExp(std::unique_ptr<MulExp> t_leftMulExp, const std::vector<TokenType>& t_operList, std::vector<std::unique_ptr<MulExp>>&& t_mulExpList);

public:
    std::unique_ptr<MulExp> leftMulExp;
    std::vector<TokenType> operList;
    std::vector<std::unique_ptr<MulExp>> mulExpList;
};

// 乘法表达式类
struct ParenExp;
struct MulExp : public Exp {
public:
    virtual ExpType GetType() const noexcept;

    MulExp(std::unique_ptr<ParenExp> t_leftParenExp, const std::vector<TokenType>& t_operList, std::vector<std::unique_ptr<ParenExp>>&& t_parenExpList);

public:
    std::unique_ptr<ParenExp> leftParenExp;
    std::vector<TokenType> operList;
    std::vector<std::unique_ptr<ParenExp>> parenExpList;
};

// 括号表达式类
struct ParenExp : public Exp {
public:
    virtual ExpType GetType() const noexcept;

    ParenExp(std::unique_ptr<Exp> texp);

public:
    std::unique_ptr<Exp> exp;

};

// 数值表达式类
struct NumExp : public Exp {
public:
    virtual ExpType GetType() const noexcept;
    NumExp(int t_num);

public:
    int num;
};

} // namespace ast

#endif // AST_EXP_H_

我们创建了四个类用于描述 AST 节点：
Exp 是抽象基类，只是为了让我们的实现更加优雅，实际描述节点的是下列四个类；
AddExp 、 MulExp 、 ParenExp 、 NumExp 皆继承自 Exp ，各自表示三个终结符节点和一个非终结符节点。

其中，派生类的成员变量存储了节点的连接关系与值。
暂时看不懂也没关系，你可以先拷贝代码，理解的关键在于语法分析器。

接下来是 AST 节点的实现，就是类的构造与析构，并没有什么特别的代码，大致浏览下即可。

\ToyLang\ast\exp.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include "exp.h"

namespace toylang {

using std::unique_ptr;


ExpType AddExp::GetType() const noexcept {
    return ExpType::kAdd;
}

AddExp::AddExp(unique_ptr<MulExp> t_leftMulExp, const std::vector<TokenType>& t_operList, std::vector<unique_ptr<MulExp>>&& t_mulExpList) :
    leftMulExp(std::move(t_leftMulExp)), operList(t_operList), mulExpList(std::move(t_mulExpList)) {

}


ExpType MulExp::GetType() const noexcept {
    return ExpType::kMul;
}

MulExp::MulExp(unique_ptr<ParenExp> t_leftParenExp, const std::vector<TokenType>& t_operList, std::vector<unique_ptr<ParenExp>>&& t_parenExoList) :
    leftParenExp(std::move(t_leftParenExp)), operList(t_operList), parenExpList(std::move(t_parenExoList)) {

}


ExpType ParenExp::GetType() const noexcept {
    return ExpType::kParen;
}

ParenExp::ParenExp(unique_ptr<Exp> t_exp) : exp(std::move(t_exp)) {

}


ExpType NumExp::GetType() const noexcept {
    return ExpType::kNum;
}

NumExp::NumExp(int t_num) : num(t_num) {

}

} // namespace ast

# Parser

我们在第 2 节已经实现了一个词法分析器，接下来我们继续完成语法分析器。

以下是头文件，接下来我们把重心放到实现上。

\ToyLang\parser\parser.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#ifndef PARSER_PARSER_H_
#define PARSER_PARSER_H_

#include <memory>

#include "lexer/lexer.h"
#include "ast/exp.h"

namespace toylang {

// 语法分析时发生的异常
class ParserException : public std::exception {
public:
    ParserException(const char* t_msg);
};

class Parser {
public:
    Parser(Lexer* t_lexer);

public:
    std::unique_ptr<Exp> ParseExp();
    std::unique_ptr<AddExp> ParseAddExp();
    std::unique_ptr<MulExp> ParseMulExp();
    std::unique_ptr<ParenExp> ParseParenExp();
    std::unique_ptr<NumExp> ParseNumExp();

private:
    Lexer* m_lexer;
};

} // namespace parser
#endif // PARSER_PARSER_H_

# 解析 exp

首先我们知道，我们所编写的是四则表达式运算器，那么接收到的用户输入就是一个表达式，即非终结符 exp ，因此，解析就是从 exp 开始层层下降的。

\ToyLang\parser\parser.cpp 
1
2
3
4
5
6
7
unique_ptr<Exp> Parser::ParseExp() {
    auto exp = ParseAddExp();
    if (!m_lexer->LookAHead().Is(TokenType::kEof)) {
        throw ParserException("Incomplete parsing");
    }
    return exp;
}

代码非常简单，根据 EBNF 描述的文法来看， exp 由一个 addexp 组成；
因此我们调用 ParseAddExp 去解析 addexp ，返回一个 AddExp 类对象，返回就表示解析完成了。

接下来我们前瞻一个 token，看看是不是已经将所有 token 都吃完了，还有可用 token 就表示输入串有错误，抛出一个异常即可。

最后直接返回 AddExp 对象，到这里你可能有些疑惑，我们解析的不是 exp 吗？为什么不是返回一个 Exp 对象，而是返回一个 AddExp 对象？
因为实际上 EBNF 文法描述上， exp 就只由 addexp 组成，它们基本上可以看作是等价的，为了省事，我就直接让 AddExp 对象成为 AST 的根节点。

而我们实际上没有实现描述非终结符 exp 的类， Exp 并不是描述 exp 的类，只是看起来很像。
Exp 是我们另外定义的基类，基类指针自然可以指向派生类对象。

# 解析 addexp

接下来我们需要解析 addexp ，对应的类自然就是 AddExp ，返回它的实例化对象。

\ToyLang\parser\parser.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
unique_ptr<AddExp> Parser::ParseAddExp() {
    auto leftMulExp = ParseMulExp();    // 解析左边的mulexp，保存解析的结果

    std::vector<TokenType> operList;
    std::vector<unique_ptr<MulExp>> mulExpList;

  // 循环解析右边的mulexp
    do {
    // 前瞻一下，如果后面已经不是加法符号或者减法符号了，就可以返回了。
        auto token = m_lexer->LookAHead();
        if (!token.Is(TokenType::kOpAdd) && !token.Is(TokenType::kOpSub)) {
            break;
        }
    // 吃掉刚刚前瞻的运算符号
        m_lexer->NextToken();
        operList.push_back(token.type);   // 保存符号，因为连接两个mulexp的符号可能是加法，也可能是减法，保存起来供解释时使用
        mulExpList.push_back(ParseMulExp());    // 解析并保存右侧mulexp
    } while (true);

  // 构造AddExp对象并返回
    return std::make_unique<AddExp>(std::move(leftMulExp), operList, std::move(mulExpList));
}

依旧是按照 EBNF 文法来解析。

我们先解析最左边的一个 mulexp 非终结符，接下来就可能是多对 oper2 和 mulexp 了，因此用一个循环来解析，分别保存到 vector 容器中。

# 解析 mulexp

接下来解析 mulexp ，对应的类是 MulExp ，返回它的实例化对象。

\ToyLang\parser\parser.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
auto leftParenExp = ParseParenExp();

std::vector<TokenType> operList;
std::vector<unique_ptr<ParenExp>> parenExpList;

do {
    auto token = m_lexer->LookAHead();
    if (!token.Is(TokenType::kOpMul) && !token.Is(TokenType::kOpDiv)) {
        break;
    }

    m_lexer->NextToken();
    operList.push_back(token.type);
    parenExpList.push_back(ParseParenExp());

} while (true);

return std::make_unique<MulExp>(std::move(leftParenExp), operList, std::move(parenExpList));

由于 addexp 和 mulexp 的结构基本相同，他们的解析过程也一般无二。

# 解析 parenexp

\ToyLang\parser\parser.cpp 
1
2
3
4
5
6
7
8
9
10
unique_ptr<ParenExp> Parser::ParseParenExp() {
    auto token = m_lexer->LookAHead();
    if (!token.Is(TokenType::kSepLParen)) {        // (
        return std::make_unique<ParenExp>(ParseNumExp());   // 不是以`(`开头的子表达式，直接当成numexp解析。
    }
    m_lexer->NextToken();
    auto exp = ParseAddExp();   // 解析一个addexp
    m_lexer->MatchToken(TokenType::kSepRParen);        // )
    return std::make_unique<ParenExp>(std::move(exp));
}

解析 parenexp 的代码也比较简单，根据 EBNF 所描述的文法，要么就是以 ( 开始的子表达式，要么就是数值表达式。

# 解析 numexp

\ToyLang\parser\parser.cpp 
1
2
3
4
5
unique_ptr<NumExp> Parser::ParseNumExp() {
    auto token = m_lexer->MatchToken(TokenType::kNumber);   // 直接匹配一个NumberToken
    int num = atoi(token.str.c_str());    // 字符串转整数
    return std::make_unique<NumExp>(num);
}

numexp 的解析是最简单的，直接从词法分析器那边匹配一个 Number 类型的 token，就能拿到其字符串。

至此，语法分析告一段落。

# Interpreter

经过语法分析阶段，如果一切顺利，我们就将输入串转换成了 AST，接下来我们编写一个解释器，解释这颗树，得到结果。

\ToyLang\interpreter\interpreter.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#ifndef INTERPRETER_INTERPRETER_H_
#define INTERPRETER_INTERPRETER_H_

#include "ast/exp.h"

namespace interpreter {

class Interpreter{
public:
    int InterpretExp(Exp* exp) const noexcept;
    int InterpretAddExp(AddExp* exp) const noexcept;
    int InterpretMulExp(MulExp* exp) const noexcept;
    int InterpretParenExp(ParenExp* exp) const noexcept;
    int InterpretNumberExp(NumExp* exp) const noexcept;
};

} // namespace interpreter

#endif // INTERPRETER_INTERPRETER_H

头文件也很简单，就是定义了一个解释器类，其成员函数负责解释不同类型的 AST 节点。

\ToyLang\interpreter\interpreter.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "interpreter.h"

namespace interpreter {

int Interpreter::InterpretExp(Exp* exp) const noexcept {
    return InterpretAddExp(static_cast<AddExp*>(exp));
}

int Interpreter::InterpretAddExp(AddExp* exp) const noexcept {
    int res = InterpretMulExp(exp->leftMulExp.get());
    for (int i = 0; i < exp->operList.size(); i++) {
        if (exp->operList[i] == TokenType::kOpAdd) {
            res += InterpretMulExp(exp->mulExpList[i].get());
        }
        else {
            res -= InterpretMulExp(exp->mulExpList[i].get());
        }
    }
    return res;
}

int Interpreter::InterpretMulExp(MulExp* exp) const noexcept {
    int res = InterpretParenExp(exp->leftParenExp.get());
    for (int i = 0; i < exp->operList.size(); i++) {
        if (exp->operList[i] == TokenType::kOpMul) {
            res *= InterpretParenExp(exp->parenExpList[i].get());
        }
        else {
            res /= InterpretParenExp(exp->parenExpList[i].get());
        }
    }
    return res;
}
int Interpreter::InterpretParenExp(ParenExp* exp) const noexcept {
    if (exp->exp->GetType() == ExpType::kNum) {
        return InterpretNumberExp(static_cast<NumExp*>(exp->exp.get()));
    }
    else {
        return InterpretAddExp(static_cast<AddExp*>(exp->exp.get()));
    }
}

int Interpreter::InterpretNumberExp(NumExp* exp) const noexcept {
    return exp->num;
}

} // namespace interpreter

实现代码能看到些许上述语法分析的代码的影子，实际上就是树的深度优先遍历并向上返回运算结果。
只要理解了语法分析，解释的过程也很好理解。
如果你需要考虑四则运算的性能，甚至可以在语法分析阶段就返回数值结果，而不是构造 AST 树。

# 完整测试

\ToyLang\entry.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "lexer/lexer.h"
#include "parser/parser.h"
#include "interpreter/interpreter.h"

int main() {
    using namespace lexer;
    using namespace parser;
    using namespace interpreter;

    Lexer lexer{ "1 + 33 - 0 * (33 / 999) + 123" };
    Parser parser(&lexer);
    auto exp = parser.ParseExp();

    Interpreter inter;
    int res = inter.InterpretExp(exp.get());

    printf("%d", res);
}

# 完整代码

我将本节完整代码放到了 github 上，你可以将其克隆下来亲自调试运行，鉴于 vs 强大的调试能力，你可以一步一步观察 AST 树的构造过程，加深理解。