Software Systems Atlas

中文

English

中文

English

主题

第 11 卷 / 第 6 章 / 第 1 课

6.1 递归下降与 AST：把优先级写进调用结构 ​

词法分析把 1 + 2 * 3 交成五个 token。语法分析要恢复它们的层次：乘法成为加法的右子树，才能表达先乘后加。token 的队伍排好了，运算可不能只按先来后到。

本课目标 ​

  • 把适合预测分析的文法映射为递归函数；
  • 在解析过程中构造 AST；
  • 正确实现优先级和左、右结合；
  • 保留 span 与错误节点，而不是只返回成功或失败。

1. 从分层文法开始 ​

text
expression → additive
additive   → multiplicative (("+" | "-") multiplicative)*
multiplicative → unary (("*" | "/") unary)*
unary      → ("-" | "!") unary | primary
primary    → NUMBER | IDENT | "(" expression ")"

函数调用方向从低优先级走向高优先级：parse_additive 先调用 parse_multiplicative，因此乘法子树在加法组合前完成。

循环表达左结合。a - b - c 会逐次把已有左树与新右项组合成 (a-b)-c。右结合运算如赋值或幂，可以递归处理右侧，也可以用显式栈实现；不能照搬这个立即合并左树的循环。

2. AST 节点表达语义结构 ​

以下 C 代码是可集成的解析器骨架，不是独立程序。宿主需要提供 <stddef.h>、<stdbool.h>、<assert.h>，以及 token 枚举、arena、诊断容器和 make_* 构造函数。这里的 Token 含 kind、span、integer_value；上一章的 start/end 必须先转成 Span，整数转换需另行检查 long long 范围。构造函数要么返回有效节点，要么让整个解析安全终止，不能返回未处理的空指针。

c
typedef struct { size_t start, end; } Span;

typedef enum {
    EXPR_NUMBER,
    EXPR_NAME,
    EXPR_UNARY,
    EXPR_BINARY,
    EXPR_ERROR
} ExprKind;

typedef struct Expr Expr;
struct Expr {
    ExprKind kind;
    Span span;
    union {
        long long number;
        struct { Span name; } name;
        struct { TokenKind op; Expr *operand; } unary;
        struct { Expr *left; TokenKind op; Expr *right; } binary;
    } as;
};

生产实现还要确定节点内存所有权。常见做法是 arena：整棵 AST 生命周期一致，可批量释放，避免每个节点单独 malloc/free。若需要增量更新，则可能使用不可变绿树或引用计数结构。

3. Parser 游标与消费原语 ​

c
typedef struct {
    const Token *tokens;
    size_t count;
    size_t current;
    Arena *arena;
    DiagnosticList *diagnostics;
} Parser;

static const Token *peek(const Parser *p) {
    assert(p->count > 0 && p->current < p->count);
    return &p->tokens[p->current];
}

static bool match(Parser *p, TokenKind kind) {
    if (peek(p)->kind != kind) return false;
    if (kind != TOK_EOF) p->current++;
    return true;
}

static const Token *expect(Parser *p, TokenKind kind, const char *message) {
    if (peek(p)->kind == kind) {
        const Token *found = peek(p);
        if (kind != TOK_EOF) p->current++;
        return found;
    }
    report(p->diagnostics, peek(p)->span, message);
    return NULL;
}

宿主在入口验证：缓冲区非空，只有最后一项是 EOF，current 初值为零，token 与 arena 在解析期间有效。下面的消费原语在 EOF 上保持游标不动；断言只检查内部不变量，不能替代对外部输入的验证。expect 报错后是否消费 token 不能随意决定：消费错了可能跳过有效结构，不消费又可能让上层循环停滞。恢复策略放到下一课集中处理。

4. primary 构造叶子与括号结构 ​

c
static Expr *parse_expression(Parser *p);
static Expr *parse_unary(Parser *p);

static Expr *parse_primary(Parser *p) {
    const Token *current = peek(p);
    if (match(p, TOK_NUMBER)) {
        return make_number(p->arena, current->integer_value, current->span);
    }
    if (match(p, TOK_IDENTIFIER)) {
        return make_name(p->arena, current->span);
    }
    if (match(p, TOK_LEFT_PAREN)) {
        const Token *left = current;
        Expr *inside = parse_expression(p);
        const Token *right = expect(p, TOK_RIGHT_PAREN, "缺少右括号");
        inside->span = (Span){
            left->span.start, right != NULL ? right->span.end : inside->span.end
        };
        return inside;
    }

    report(p->diagnostics, current->span, "需要表达式");
    if (current->kind != TOK_EOF && current->kind != TOK_RIGHT_PAREN) p->current++;
    return make_error(p->arena, current->span);
}

AST 可以不保留独立括号节点，但仍应保存覆盖括号的 span，或另存 parenthesized 标记。格式化器和精确源码变换可能需要完整 CST；“AST 有括号节点就一定错”是过度结论。

5. 用循环构造左结合二元树 ​

c
static Expr *parse_multiplicative(Parser *p) {
    Expr *left = parse_unary(p);
    while (peek(p)->kind == TOK_STAR || peek(p)->kind == TOK_SLASH) {
        TokenKind op = p->tokens[p->current++].kind;
        Expr *right = parse_unary(p);
        left = make_binary(p->arena, left, op, right);
    }
    return left;
}

static Expr *parse_additive(Parser *p) {
    Expr *left = parse_multiplicative(p);
    while (peek(p)->kind == TOK_PLUS || peek(p)->kind == TOK_MINUS) {
        TokenKind op = p->tokens[p->current++].kind;
        Expr *right = parse_multiplicative(p);
        left = make_binary(p->arena, left, op, right);
    }
    return left;
}

对 1 + 2 * 3，乘法函数先返回 *(2,3)，加法函数再构造 +(1,*(2,3))。

6. 一元运算与右递归 ​

c
static Expr *parse_unary(Parser *p) {
    if (peek(p)->kind == TOK_MINUS || peek(p)->kind == TOK_BANG) {
        const Token *op = &p->tokens[p->current++];
        Expr *operand = parse_unary(p);
        return make_unary(p->arena, op->kind, operand, op->span.start);
    }
    return parse_primary(p);
}

递归允许 !!-x。骨架还没有深度计数器；接入不受信任输入前，应同时限制前缀链与括号嵌套，或使用显式栈。仅限制 token 总数不能保证系统调用栈足够大，数万个前缀运算符就可能将它耗尽。

7. 完整消费是入口职责 ​

c
static Expr *parse_expression(Parser *p) {
    return parse_additive(p);
}

Expr *parse(Parser *p) {
    Expr *result = parse_expression(p);
    if (peek(p)->kind != TOK_EOF) {
        report(p->diagnostics, peek(p)->span, "表达式后存在多余 token");
    }
    return result;
}

parse_expression 在这里委托给最低优先级层。返回一个节点可能伴随诊断；调用方必须检查诊断容器，不能直接把带错误节点的树拿去执行。

只调用 parse_expression 而不检查 EOF，会把 1 + 2 garbage 的合法前缀误当作完整成功。嵌入语句解析时则应检查该上下文的终止 token，如分号或右括号。

常见误区 ​

  • 每个文法都能直接变成递归下降：左递归和预测冲突需要处理。
  • 括号从 AST 删除后位置也可以丢：诊断和源码工具仍需完整跨度。
  • 成功返回节点代表消费了全部输入：入口必须检查上下文终止符。
  • 递归深度理论无界所以实现也无需限制：实际调用栈和内存有限。

练习 ​

  1. 增加比较运算层，保证比较优先级低于加法。
  2. 实现右结合赋值 a = b = 1，画出 AST。
  3. 为每个节点计算覆盖左右子节点和运算符的 span。
  4. 对一万个前缀 ! 和深层括号分别设计深度限制与诊断。

小结 ​

递归下降把文法层级变成函数调用层级，把结合性变成循环或递归方向。AST 构造与语法识别同步进行，但源跨度、错误节点和内存所有权必须从第一版接口就考虑。

下一课用 FIRST/FOLLOW 集解释“为什么一个 token 足以选择产生式”，并设计遇错后仍能继续解析的同步策略。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang