c++中如何实现简单的递归下降解析器_c++表达式解析基础【详解】_技术教程

递归下降解析器的核心结构是每个语法规则对应一个手写函数，通过函数间调用（含自调用）匹配输入，天然适配LL(1)语法；需消除左递归、显式管理token位置、依调用顺序体现优先级与结合性。

什么是递归下降解析器的核心结构

递归下降解析器不是某种库或模板，而是一种手写解析器的组织方式：每个语法规则对应一个函数，函数内部通过调用其他规则函数（包括自己）来匹配输入。它天然适合 LL(1) 类语法，比如简单算术表达式、变量声明等。C++ 里没有现成的“递归下降生成器”，你得自己写 parse_expr()、parse_term()、parse_factor() 这类函数，并控制好 token 流的推进。

如何处理左递归避免栈溢出

直接把 E → E + T | T 翻译成 parse_expr() { parse_expr(); match('+'); parse_term(); } 会无限递归崩溃。必须消除左递归。常见做法是改写为右递归结构，再用循环实现：

原始左递归规则：E → E + T | E - T | T
消除后：E → T { ('+' | '-') T }，即“一个 T 后跟零或多个 +T 或 -T”
对应 C++ 实现用 while 循环，不递归调用自身

ExprNode* parse_expr() {
    ExprNode* left = parse_term();
    while (current_token().type == PLUS || current_token().type == MINUS) {
        Token op = consume();
        ExprNode* right = parse_term();
        left = new BinaryOpNode(left, op, right);
    }
    return left;
}

token 流怎么管理才不出错

最易出问题的是 consume() 和 peek() 的配合。如果每次 parse_* 都盲目 consume()，遇到错误就无法回退；但全靠 peek() 又没法推进。推荐用“前瞻一个 token + 显式位置管理”：

维护一个 size_t pos 指向当前 token 索引，而非用迭代器或引用传递
current_token() 返回 tokens[pos]，consume() 执行 pos++ 并返回旧 token
所有 parse_* 函数只读不修改 pos，仅在确认匹配时才 consume()
错误恢复可简单跳过 token（如跳过到下一个 SEMI 或 R_PAREN），但不要尝试自动插入

为什么优先级和结合性要靠函数调用顺序体现

递归下降里没有“运算符优先级表”，优先级完全由函数调用层级决定。比如 parse_expr() 调用 parse_term()，parse_term() 再调用 parse_factor()，天然形成 expr → term → factor 的降序优先级链。结合性则靠循环方向控制：

左结合（1-2-3 → ((1-2)-3)）：用 while 在左侧节点上不断扩展
右结合（如幂运算 a^b^c）：需递归调用自身，例如 parse_power() 中先调 parse_f actor()，再检查 ^ 后递归调 parse_power()
不写错顺序：不能让 parse_term() 调用 parse_expr()，否则优先级反转，1+2*3 会解析成 (1+2)*3