85、STL与解释器模式：语法解析、表达式求值、抽象语法树

解释器模式，说白了就是「自己造一个迷你语言」。你给它一段文本，它按照你定的规则去解析，然后执行。我最早接触这个模式是在做一个配置规则引擎的时候，业务方天天改需求，改得我头皮发麻。后来我干脆用 STL 搭了一个简单的表达式解释器，把规则写在文本里，改规则不用重新编译——嗯，那感觉，真香。

解释器模式的核心思想

解释器模式的定义其实不复杂：给定一个语言，定义它的文法表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。你想想看，这不就是编译器干的事吗？只不过我们这里只做「解释执行」，不生成目标代码。

在 C++ 里，我们通常用类来代表文法中的每一个规则。比如一个加法表达式 a + b，我们可以用 AddExpression 类来表示，它内部持有左表达式和右表达式。这种树形结构，就是抽象语法树（AST）。

关键点：解释器模式适合那些「语法规则相对固定，但需要频繁解释执行」的场景。如果语法规则经常变，那还是上 Lex/Yacc 或者手写递归下降解析器吧。

用 STL 搭建表达式求值器

我们来看一个具体的例子：一个支持加减乘除和括号的算术表达式求值器。我会用 STL 的 std::variant、std::visit、std::any 这些现代特性来简化代码。

先定义 AST 节点类型：

#include <iostream>
#include <variant>
#include <memory>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <sstream>
#include <cctype>

// 前向声明
struct NumberExpr;
struct BinaryExpr;
struct VariableExpr;

// 用 variant 表示所有可能的表达式类型
using Expr = std::variant<
    std::unique_ptr<NumberExpr>,
    std::unique_ptr<BinaryExpr>,
    std::unique_ptr<VariableExpr>
>;

struct NumberExpr {
    double value;
};

struct BinaryExpr {
    char op;  // '+', '-', '*', '/'
    Expr left;
    Expr right;
};

struct VariableExpr {
    std::string name;
};

这里我用 std::variant 替代了传统的虚函数继承。为什么？因为 variant 是值语义，内存布局紧凑，没有虚表开销。我在项目中用 variant 重构过一个老旧的 AST，性能提升了大概 15%。

递归下降解析器

解析器负责把字符串变成 AST。我习惯用递归下降法，因为它直观，而且和文法规则一一对应。

class Parser {
public:
    explicit Parser(const std::string& input) 
        : input_(input), pos_(0) {}

    Expr parse() {
        return parseExpr();
    }

private:
    std::string input_;
    size_t pos_;

    char peek() {
        skipWhitespace();
        if (pos_ < input_.size()) return input_[pos_];
        return '\0';
    }

    char consume() {
        skipWhitespace();
        if (pos_ < input_.size()) return input_[pos_++];
        return '\0';
    }

    void skipWhitespace() {
        while (pos_ < input_.size() && std::isspace(input_[pos_])) {
            ++pos_;
        }
    }

    // 解析表达式：处理加减
    Expr parseExpr() {
        auto left = parseTerm();
        while (peek() == '+' || peek() == '-') {
            char op = consume();
            auto right = parseTerm();
            left = std::make_unique<BinaryExpr>(
                BinaryExpr{op, std::move(left), std::move(right)});
        }
        return left;
    }

    // 解析项：处理乘除
    Expr parseTerm() {
        auto left = parseFactor();
        while (peek() == '*' || peek() == '/') {
            char op = consume();
            auto right = parseFactor();
            left = std::make_unique<BinaryExpr>(
                BinaryExpr{op, std::move(left), std::move(right)});
        }
        return left;
    }

    // 解析因子：数字、变量、括号
    Expr parseFactor() {
        char c = peek();
        if (c == '(') {
            consume();  // '('
            auto expr = parseExpr();
            consume();  // ')'
            return expr;
        }
        if (std::isdigit(c) || c == '.') {
            return parseNumber();
        }
        if (std::isalpha(c)) {
            return parseVariable();
        }
        throw std::runtime_error("Unexpected character");
    }

    Expr parseNumber() {
        std::string num;
        while (std::isdigit(peek()) || peek() == '.') {
            num += consume();
        }
        return std::make_unique<NumberExpr>(
            NumberExpr{std::stod(num)});
    }

    Expr parseVariable() {
        std::string name;
        while (std::isalnum(peek()) || peek() == '_') {
            name += consume();
        }
        return std::make_unique<VariableExpr>(
            VariableExpr{name});
    }
};

小技巧：解析器里用 peek() 和 consume() 分离「查看下一个字符」和「消费它」两个动作，这样逻辑更清晰。我曾经在写一个 JSON 解析器时没注意这个细节，结果调试到凌晨两点……

求值器：用 std::visit 遍历 AST

AST 建好了，接下来就是求值。这里 std::visit 是神器，它帮我们做类型匹配，不用手写一堆 if-else。

class Evaluator {
public:
    using Value = std::variant<double, std::string>;

    Value evaluate(const Expr& expr) {
        return std::visit(*this, expr);
    }

    // 重载 operator() 处理每种节点
    Value operator()(const std::unique_ptr<NumberExpr>& num) {
        return num->value;
    }

    Value operator()(const std::unique_ptr<VariableExpr>& var) {
        auto it = vars_.find(var->name);
        if (it != vars_.end()) {
            return it->second;
        }
        throw std::runtime_error("Undefined variable: " + var->name);
    }

    Value operator()(const std::unique_ptr<BinaryExpr>& bin) {
        auto leftVal = evaluate(bin->left);
        auto rightVal = evaluate(bin->right);

        // 确保两边都是 double
        if (!std::holds_alternative<double>(leftVal) ||
            !std::holds_alternative<double>(rightVal)) {
            throw std::runtime_error("Type mismatch in binary expression");
        }

        double l = std::get<double>(leftVal);
        double r = std::get<double>(rightVal);

        switch (bin->op) {
            case '+': return l + r;
            case '-': return l - r;
            case '*': return l * r;
            case '/': 
                if (r == 0) throw std::runtime_error("Division by zero");
                return l / r;
            default:
                throw std::runtime_error("Unknown operator");
        }
    }

    void setVariable(const std::string& name, double value) {
        vars_[name] = value;
    }

private:
    std::map<std::string, double> vars_;
};

你看，std::visit 配合 lambda 或者函数对象，代码非常紧凑。每个节点类型对应一个重载，编译器帮你做 dispatch。我在重构一个旧项目时，把原来 200 行的 switch-case 替换成了 variant + visit，代码量直接砍半。

SVG 流程图：表达式解析与求值全过程

输入表达式字符串 词法分析 (Tokenizer) 语法分析 (Parser) 抽象语法树 (AST) 求值器 (Evaluator) 输出求值结果 "3 + 5 * (2 - 1)" → 拆分成 token 序列 → 递归下降构建树 → 树形结构表示 → 后序遍历求值 → 最终数值

避坑指南：我踩过的几个坑

  • 左递归问题：递归下降解析器不能直接处理左递归文法。比如 Expr ::= Expr '+' Term 这种，会无限递归。我刚开始写解析器时就在这里栽了跟头，后来改成循环解析才搞定。
  • 运算符优先级：加减和乘除的优先级不同，必须分层解析。我见过有人试图用一个函数搞定所有优先级，结果解析 3 + 4 * 5 得到 35 而不是 23。
  • 错误处理：解析器遇到非法输入时，最好给出有意义的错误信息，比如「第 5 行第 3 列，期望数字但遇到 '#'」。我早期只抛一个 std::runtime_error("parse error")，被同事吐槽了好久。

注意：解释器模式不适合性能敏感的场景。每次解释执行都要遍历 AST，如果表达式被反复求值，建议先编译成字节码或者直接生成机器码。我在一个高频交易项目中就吃过这个亏，后来改用了 JIT 编译。

扩展：支持变量和函数

上面的求值器已经支持变量了。我们还可以进一步扩展，比如支持自定义函数。用 std::function 来存储函数实现，用 std::map 做名字查找：

class ExtendedEvaluator : public Evaluator {
public:
    using FuncType = std::function<double(const std::vector<double>&)>;

    void setFunction(const std::string& name, FuncType func) {
        funcs_[name] = std::move(func);
    }

    // 在 parseFactor 里增加函数调用解析
    // 在求值时查找 funcs_ 并调用
};

这样，你的迷你语言就可以支持 sin(3.14)、max(a, b) 这样的调用了。我在一个数据分析工具里就是这么做的，用户可以在配置里写公式，不用改 C++ 代码。

总结

解释器模式 + STL，是一对黄金搭档。std::variant 和 std::visit 让 AST 遍历变得优雅，std::map 和 std::function 让扩展变得简单。我个人觉得，掌握这个组合，等于掌握了一种「创造语言」的能力——虽然只是迷你语言，但在很多场景下已经足够用了。

最后提醒一句：不要过度设计。如果你的语法只有两三个规则，手写 if-else 可能比完整的解释器模式更合适。我在早期项目中就犯过「拿着锤子看什么都像钉子」的毛病，现在学乖了——先写简单的，复杂了再重构。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →