Parser：把 token 组成 AST

本节阅读量:

上一节 lexer 已经把源码切成了 token。

比如源码：

1

(+ 40 2)

会先变成：

1

["(", "+", "40", "2", ")"]

但 token 只是小块，还不是结构。

parser 要做的是：

1

tokens -> AST

也就是把这一串 token 读成：

1

Add(Int(40), Int(2))

parser 不再关心字符

lexer 已经处理了这些细节：

1
2
3


源码里有几个空格。
数字有几位字符。
括号有没有和旁边的字符粘在一起。

所以 parser 不需要在原始字符串上移动下标。它只看 token：

1

(   +   40   2   )

parser 问的是：

1
2
3


下一个 token 是整数吗？
下一个 token 是左括号吗？
如果是左括号，后面是不是一个加法表达式？

第一章的语言规则是：

1
2


expr ::= integer
       | "(" "+" expr expr ")"

parser 的代码基本就是把这两条规则翻译成 C++。

Parser 记住当前位置

代码在：

1

code/01_numbers/src/front/parser.cpp

Parser 这个类主要保存两个东西：

1
2


std::vector<std::string> tokens_;
std::size_t current_ = 0;

可以先这样理解：

1
2


tokens_   lexer 切出来的一串 token
current_  现在读到第几个 token

如果 token 是：

1

["(", "+", "40", "2", ")"]

刚开始：

1
2


current_ = 0
当前 token 是 "("

读走一个 token 后：

1
2


current_ = 1
当前 token 是 "+"

parser 就是靠这个位置，一步一步往前读。

peek、advance 和 expect

先看三个小工具函数：

1
2
3
4
5
6


const std::string& Parser::peek() const {
    if (current_ >= tokens_.size()) {
        throw std::runtime_error("unexpected end of input");
    }
    return tokens_[current_];
}

peek() 只看当前 token，不前进。

1
2
3
4
5


std::string Parser::advance() {
    std::string token = peek();
    ++current_;
    return token;
}

advance() 做两件事：

1
2


取出当前 token。
把 current_ 往后移一格。

比如当前是：

1
2


current_ = 0
tokens_[0] = "("

调用 advance() 后：

1
2


返回 "("
current_ 变成 1

再看 expect：

1
2
3
4
5
6


void Parser::expect(const std::string& token, const char* message) {
    if (current_ >= tokens_.size() || tokens_[current_] != token) {
        throw std::runtime_error(message);
    }
    advance();
}

expect("+", "...") 的意思是：

1
2
3


下一个 token 必须是 "+"。
如果不是，就报错。
如果是，就把它读走。

它适合处理语法里固定必须出现的东西，比如：

1
2


加法开头的 +
加法结尾的 )

parse_program 只允许一个表达式

对外使用 parser 时，调用的是：

1
2
3
4


std::unique_ptr<Expr> parse(const std::string& source) {
    Parser parser(lex(source));
    return parser.parse_program();
}

parse 先调用 lex(source)，拿到 token 列表，再创建 Parser。

真正读完整程序的是：

1
2
3
4
5
6
7


std::unique_ptr<Expr> Parser::parse_program() {
    auto expr = parse_expr();
    if (current_ != tokens_.size()) {
        throw std::runtime_error("expected end of input");
    }
    return expr;
}

第一章规定：

1

一个完整程序就是一个表达式。

所以 parse_program() 会先读一个表达式。读完以后，它还要检查后面没有多余 token。

比如：

1

42

可以。

但：

1

42 43

不可以。因为第一个表达式 42 已经读完了，后面还剩一个多余的 43。

parse_expr 对应语言规则

最核心的函数是 parse_expr()：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


std::unique_ptr<Expr> Parser::parse_expr() {
    std::string token = advance();

    if (is_integer(token)) {
        return std::make_unique<IntExpr>(std::stol(token));
    }

    if (token == "(") {
        expect("+", "expected '+' after '('");
        auto lhs = parse_expr();
        auto rhs = parse_expr();
        expect(")", "expected ')' after addition");
        return std::make_unique<AddExpr>(std::move(lhs), std::move(rhs));
    }

    throw std::runtime_error("expected integer or '(+ expr expr)'");
}

先不要被 C++ 写法吓住。按语言规则看，它只有两种分支：

1
2


读到整数      生成 Int
读到左括号    按 (+ expr expr) 读取加法

这正好对应：

1
2


expr ::= integer
       | "(" "+" expr expr ")"

换句话说，这整个函数就是把 expr 的两条规则写成两个 if。

如果 token 是整数，比如：

1

"42"

parser 会生成：

1

Int(42)

代码是：

1
2
3


if (is_integer(token)) {
    return std::make_unique<IntExpr>(std::stol(token));
}

is_integer(token) 判断字符串是不是整数形式。它允许：

但只有一个 "-" 不行，因为负号后面必须还有数字。

std::stol(token) 把字符串变成真正的整数值。std::make_unique<IntExpr>(...) 创建 IntExpr 节点，并把它交给 unique_ptr 管理。

如果第一个 token 是 "("，第一章只允许它是加法：

1

(+ expr expr)

所以 parser 接下来期待看到 +：

1

expect("+", "expected '+' after '('");

然后读左边表达式：

1

auto lhs = parse_expr();

再读右边表达式：

1

auto rhs = parse_expr();

最后期待右括号：

1

expect(")", "expected ')' after addition");

如果这些都成功，就把左右两边包成一个加法节点：

1

return std::make_unique<AddExpr>(std::move(lhs), std::move(rhs));

这里的 lhs 和 rhs 本身也是 unique_ptr<Expr>。std::move(lhs) 和 std::move(rhs) 表示：

1

把左右子表达式交给 AddExpr 保存。

递归怎样读出嵌套结构

这两行最关键：

1
2


auto lhs = parse_expr();
auto rhs = parse_expr();

parse_expr() 的任务是读一个表达式。加法的左边和右边也都是表达式，所以它要调用自己。

例如：

1

(+ (+ 1 2) 3)

外层加法可以拆成：

1
2


左边：(+ 1 2)
右边：3

读左边时，parser 又调用一次 parse_expr()，把 (+ 1 2) 读成：

1

Add(Int(1), Int(2))

读右边时，再调用一次 parse_expr()，把 3 读成：

1

Int(3)

最后外层加法组合成：

1

Add(Add(Int(1), Int(2)), Int(3))

这不是炫技。递归正好对应第一节语言规则里的这句话：

1

表达式里面还能继续出现表达式。

常见错误从哪里报出来

看几个非法程序，错误都来自刚才那些固定期待：

1
2
3
4


(- 10 1)     读到 "(" 后期待 "+"，却看到 "-"
(+ 1)        读完左边后还要读右边，却直接遇到 ")"
(+ 1 2 3)    读完两个子表达式后期待 ")"，却看到多出来的 "3"
(+40 2)      lexer 切成 "(", "+40", "2", ")"，parser 期待 "+"，却看到 "+40"

这些错误信息不追求漂亮，但位置是对的：parser 在“下一个 token 不符合语法规则”的地方停下来。

试一下 parser

运行：

1
2
3


cd code/01_numbers
make
./mini ast examples/add.lang

输出：

1

Add(Int(40), Int(2))

再运行：

1

./mini ast examples/nested_add.lang

输出类似：

1

Add(Add(Int(1), Int(2)), Add(Int(3), Int(4)))

这说明 parser 已经把 token 组装成了 AST。

到这里，源码已经从文本变成了结构。下一节就可以沿着这棵 AST 直接算结果了。

1.3 Lexer：把源码切成 token

1.5 解释器：沿着 AST 直接算结果

本节目录