章节目录

Parser：在括号 head 位置识别 `sub1` 和 `letrec`

本节阅读量:

第五章不需要修改 lexer。它仍然只给左右括号补空格，再按空白切分 token，并不知道递归是什么。

贯穿示例：

1
2
3
4
5

(letrec sum n
    (if (eq? n 0)
        0
        (+ n (sum (sub1 n))))
    (sum 5))

会被切成下面这串 token：

1
2
3
4

["(", "letrec", "sum", "n",
 "(", "if", "(", "eq?", "n", "0", ")", "0",
 "(", "+", "n", "(", "sum", "(", "sub1", "n", ")", ")", ")", ")",
 "(", "sum", "5", ")", ")"]

lexer 会原样保留 letrec、sub1 和 eq?。它们是不是特殊形式，要由 parse_expr() 查看左括号后的 head 决定。

特殊形式优先，普通调用兜底

parser 读到左括号后，先用 peek() 查看 head，但不立刻统一消费：

1
2
3
4
5
6

if (token == "(") {
    const std::string& head = peek();

    // 依次检查固定特殊形式
    // 都不匹配时，再解析普通函数调用
}

第五章完整快照的分派顺序是：

1
2
3
4
5
6
7
8

head 是 +          解析两个操作数，产生 AddExpr
head 是 sub1       解析一个操作数，产生 Sub1Expr
head 是 let        解析名字、value、body，产生 LetExpr
head 是 letrec     解析函数名、参数名、函数体、body，产生 LetRecExpr
head 是 eq?        解析两个操作数，产生 EqExpr
head 是 if         解析条件、then、else，产生 IfExpr
head 是 lambda     解析参数和函数体，产生 LambdaExpr
没有匹配特殊形式   从当前位置解析 callee 和 argument，产生 CallExpr

这些特殊形式必须放在普通调用之前。否则 (letrec sum n ... ...) 会被误当作“调用名为 letrec 的函数”，sub1 也会落进普通调用分支。

普通调用不能提前消费 head，因为 callee 本身可能是任意表达式。例如 ((lambda x x) 42) 的 callee 是另一个括号表达式。保留当前位置，再递归调用 parse_expr()，才能读出第四章已经支持的动态 callee。

解析 sub1

sub1 是一个固定的一元特殊形式。实现位于 code/05_recursion/src/front/parser.cpp：

1
2
3
4
5
6

if (head == "sub1") {
    advance();
    auto expr = parse_expr();
    expect(")", "expected ')' after sub1 expression");
    return std::make_unique<Sub1Expr>(std::move(expr));
}

逐步看这四行：

1
2
3
4

advance()       消费固定 head：sub1
parse_expr()    递归读取唯一的操作数
expect(")")    要求操作数之后立刻结束
make_unique     创建 Sub1Expr，并接过操作数 AST 的所有权

因此：

1
2

(sub1 5)          -> Sub1(Int(5))
(sub1 (+ 2 3))    -> Sub1(Add(Int(2), Int(3)))

parser 只检查形状，不检查操作数最终是不是数字。(sub1 (lambda x x)) 可以产生 AST，之后由解释器在求值时报告类型错误。

解析 letrec

letrec 分支依次读取两个名字和两个表达式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

if (head == "letrec") {
    advance();
    std::string name = expect_identifier("expected function name after 'letrec'");
    std::string param = expect_identifier("expected parameter name after letrec function name");
    auto function_body = parse_expr();
    auto body = parse_expr();
    expect(")", "expected ')' after letrec body");
    return std::make_unique<LetRecExpr>(
        name, param, std::move(function_body), std::move(body));
}

读取顺序与 AST 字段顺序完全相同：

1
2
3
4
5
6

advance()              消费固定 head：letrec
expect_identifier()    读取递归函数名 name
expect_identifier()    读取参数名 param
parse_expr()           读取 function_body
parse_expr()           读取 letrec 的 body
expect(")")            要求到此结束

parser 不会在这里执行 function_body，也不会建立 name -> function 的环境。它只创建 LetRecExpr。自绑定属于下一节解释器和后面的 IR lowering。

贯穿示例怎样递归下降

对 recursive_sum.lang，最外层解析过程是：

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

head = letrec
├── name: sum
├── param: n
├── function_body
│   └── head = if
│       ├── condition: head = eq?
│       ├── then: Int(0)
│       └── else: head = +
│           ├── lhs: Var(n)
│           └── rhs: 普通调用
│               ├── callee: Var(sum)
│               └── argument: head = sub1
│                   └── Var(n)
└── body: 普通调用
    ├── callee: Var(sum)
    └── argument: Int(5)

两个 (sum ...) 的 head 都是 sum，没有命中固定特殊形式，所以由最后的普通调用分支生成 CallExpr。(sub1 n) 则命中新的特殊形式分支，生成 Sub1Expr。

最终根节点是：

1

LetRec(sum, n, If(Eq(Var(n), Int(0)), Int(0), Add(Var(n), Call(Var(sum), Sub1(Var(n))))), Call(Var(sum), Int(5)))

普通 identifier 仍然只是 letter+

函数名和参数名都通过 expect_identifier() 读取。底层检查没有因 sub1 或 letrec 扩大：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

bool is_identifier(const std::string& text) {
    if (text.empty()) {
        return false;
    }

    for (char c : text) {
        if (!std::isalpha(static_cast<unsigned char>(c))) {
            return false;
        }
    }
    return true;
}

所以：

1
2

sum、down、number     合法的普通 identifier
sum1、my_sum、down?   不是普通 identifier

sub1 含有数字，eq? 含有问号；它们只由 parser 在括号 head 位置按固定拼写识别。它们不是读者可以拿来当普通变量名的 identifier。

letrec 本身只含英文字母。当前 parser 没有全局“保留字表”，所以它在普通变量位置可以被读成 identifier；但只要出现在括号 head 位置，就一定优先进入 letrec 特殊形式分支，而不会被理解成普通 callee。教程示例避免把特殊形式的拼写用作用户变量名，以免制造无关困惑。

固定读取数量就是 arity 检查

sub1 必须有一个操作数，letrec 必须有两个名字和两个表达式。parser 读取固定数量后立刻要求右括号，从而拒绝多余部分。

下面是当前实现的实际错误信息：

源码 parser 报错
(sub1) expected integer, variable, arithmetic, let, letrec, eq?, if, lambda, or function call
(sub1 1 2) expected ')' after sub1 expression
(letrec 1 n 0 0) expected function name after 'letrec'
(letrec sum n1 0 0) expected parameter name after letrec function name
(letrec sum n 0) expected integer, variable, arithmetic, let, letrec, eq?, if, lambda, or function call
(letrec sum n 0 1 2) expected ')' after letrec body

缺少操作数或 body 时，parse_expr() 会在本应出现表达式的位置遇到 )，因此当前快照给出通用的“expected …”错误；多写内容时，则会由紧随其后的 expect(")") 给出更具体的右括号错误。

函数名和参数名相同并不是 arity 或 token 形状错误，所以 parser 会接受 (letrec f f f (f 1))。参数怎样遮蔽递归函数名属于环境语义，上一节已经说明。

parse_program() 还会检查根表达式后是否有剩余 token。两个并列的顶层表达式不会被悄悄忽略，而会报告：

1

error: expected end of input

实际运行 parser

在第五章目录运行：

1
2
3
4

cd code/05_recursion
make
./mini ast examples/recursive_sum.lang
./mini ast examples/countdown.lang

输出中应该同时出现：

1
2
3

LetRec(...)
Call(Var(sum), Sub1(Var(n)))
Call(Var(down), Sub1(Var(n)))

到这里，源码已经稳定变成包含 Sub1Expr 和 LetRecExpr 的 AST。下一步才会让解释器为这些节点定义行为：sub1 怎样检查数字，以及递归函数值怎样记录 self name、在调用时建立指向当前 callee 的自绑定。

5.2 AST：结构仍是一棵树，递归来自名字

上一节

5.4 解释器：每次调用都把函数自己带进去

下一节
本节目录