54、STL与编译器开发：抽象语法树、符号表、中间代码生成

说实话，很多C++程序员写了好几年业务代码，一听到「编译器开发」就觉得那是大神干的事。我以前也这么想，直到有一次我接手了一个内部DSL（领域特定语言）的解析工具——说白了，就是给公司业务写一个迷你编译器。那时候我才发现，STL在编译器开发里简直是神兵利器。

今天咱们就聊聊编译器前端的三个核心环节：抽象语法树（AST）、符号表、中间代码生成。我会用STL的视角来拆解它们，而不是讲编译原理课本上的那些公式。

抽象语法树：用STL容器搭起代码的骨架

抽象语法树，说白了就是把源代码的语法结构变成一棵树。每个节点代表一个语法结构，比如表达式、语句、函数定义。我习惯用 std::variant 或继承体系来定义节点类型。

举个例子，一个简单的表达式解析结果：

// 用 variant 定义 AST 节点
struct BinaryExpr;
struct NumberLiteral;

using ASTNode = std::variant<
    NumberLiteral,
    BinaryExpr,
    // ... 其他节点类型
>;

struct NumberLiteral {
    double value;
};

struct BinaryExpr {
    char op;  // '+', '-', '*', '/'
    std::unique_ptr<ASTNode> left;
    std::unique_ptr<ASTNode> right;
};

为什么用 std::variant？因为它是类型安全的联合体，比裸指针和 void* 安全得多。我在项目中遇到过用 void* 存节点类型，结果运行时类型转换出错，查了两天才定位到问题。用 std::variant 配合 std::visit，编译器就能帮你检查所有分支是否覆盖完整。

核心思路：AST 的遍历和操作，本质上就是对容器的递归访问。STL 的 std::visit、std::variant、std::unique_ptr 组合起来，能写出既安全又优雅的树结构代码。

你想想看，如果不用 STL，你得自己写内存管理、自己写类型擦除、自己写遍历算法。而 STL 把这些脏活累活都干了，你只需要关注语法结构本身。

符号表：std::unordered_map 的经典战场

符号表就是一张大表，记录每个变量、函数、类型的作用域和属性。说白了，就是「这个名字是谁？它从哪里来？它是什么类型？」。

我一般用 std::unordered_map<std::string, SymbolInfo> 来实现。但要注意作用域嵌套——比如函数内部的局部变量和全局变量重名时，内层作用域要覆盖外层。

struct SymbolInfo {
    std::string typeName;   // 类型名
    bool isConst;           // 是否常量
    size_t scopeLevel;      // 作用域层级
    // ... 其他属性
};

class SymbolTable {
    std::vector<std::unordered_map<std::string, SymbolInfo>> scopes_;
public:
    void enterScope() {
        scopes_.emplace_back();  // 进入新作用域
    }
    void exitScope() {
        scopes_.pop_back();      // 退出作用域
    }
    bool insert(const std::string& name, const SymbolInfo& info) {
        auto& current = scopes_.back();
        return current.emplace(name, info).second;
    }
    SymbolInfo* lookup(const std::string& name) {
        // 从内向外查找
        for (auto it = scopes_.rbegin(); it != scopes_.rend(); ++it) {
            auto found = it->find(name);
            if (found != it->end()) return &found->second;
        }
        return nullptr;
    }
};

这里用 std::vector 来模拟作用域栈，每个作用域是一个 std::unordered_map。查找时从栈顶（最内层）开始，找到就返回。我曾经犯过一个错误：用 std::map 存符号表，结果在解析大型源文件时性能瓶颈全在符号查找上。换成 std::unordered_map 后，速度提升了将近一个数量级。

小技巧：如果符号表需要频繁遍历（比如输出所有符号），可以考虑用 std::vector<std::pair<std::string, SymbolInfo>> 配合 std::find_if。虽然查找是 O(n)，但遍历时缓存友好，实际场景中往往更快。

中间代码生成：用 std::vector 构建指令流

中间代码（IR）是 AST 和最终机器码之间的桥梁。常见的 IR 形式有三地址码、SSA 形式等。我习惯用 std::vector<Instruction> 来存储指令序列，每条指令是一个结构体。

enum class OpCode {
    ADD, SUB, MUL, DIV,
    LOAD, STORE,
    JMP, JMP_IF,
    // ...
};

struct Instruction {
    OpCode op;
    std::string dest;
    std::string src1;
    std::string src2;
    // 可选：行号、调试信息
};

class IRGenerator {
    std::vector<Instruction> ir_;
    std::string newTemp() {
        static int counter = 0;
        return "%t" + std::to_string(counter++);
    }
public:
    void generate(const ASTNode& node) {
        std::visit([this](const auto& n) {
            generateImpl(n);
        }, node);
    }
    const std::vector<Instruction>& getIR() const {
        return ir_;
    }
};

生成 IR 的过程，其实就是遍历 AST，把每个节点翻译成一条或多条指令。比如 a + b * c 会生成：

%t1 = b * c
%t2 = a + t1

这里 newTemp() 函数用 std::to_string 生成临时变量名，简单粗暴但有效。我在实际项目中遇到过一个问题：临时变量名用整数递增，结果在调试时很难对应回源代码。后来我改成了「行号+序号」的格式，比如 %10_3 表示第10行第3个临时变量，调试体验好了很多。

注意：IR 生成时一定要考虑类型检查和类型转换。比如 int + double 需要插入隐式类型转换指令。我见过一个编译器因为漏了类型转换，生成的 IR 在后续优化阶段直接崩溃。

SVG 框架图：编译器前端核心流程

编译器前端核心流程（STL视角） 词法分析 std::string + 正则 语法分析 std::variant + unique_ptr 语义分析 unordered_map + vector 中间代码生成 vector<Instruction> 符号表 unordered_map + vector STL 核心组件：variant / unique_ptr / unordered_map / vector / visit 关键数据结构映射： AST节点 → std::variant + std::unique_ptr 符号表 → std::unordered_map + std::vector（作用域栈） IR指令流 → std::vector<Instruction> 临时变量名 → std::to_string + 计数器

实战经验：STL 在编译器开发中的几个坑

嗯，这里我要说几个我踩过的坑，希望能帮你省点时间。

  • std::variant 的递归问题：AST 节点经常需要递归引用（比如 BinaryExpr 包含左右子节点）。直接用 std::variant<BinaryExpr, ...> 会编译失败，因为类型不完整。解决方案是用 std::unique_ptr<ASTNode> 间接引用，或者用 std::vector<std::unique_ptr<ASTNode>> 存子节点列表。
  • std::unordered_map 的迭代器失效：符号表在插入新符号时，如果触发了 rehash，所有迭代器都会失效。我建议在遍历符号表时不要同时插入，或者先收集要插入的符号，批量处理。
  • std::vector 的扩容开销：IR 指令序列动辄成千上万条，如果 std::vector 频繁扩容，性能会很难看。我习惯在生成 IR 前先 reserve() 一个预估大小，比如 AST 节点数的两倍。

我的个人习惯：在编译器开发中，我会尽量用 std::unique_ptr 管理 AST 节点的生命周期，用 std::shared_ptr 只在符号表需要共享所有权时使用。大多数情况下，unique_ptr 就足够了，而且性能更好。

总结：STL 让编译器开发不再「高不可攀」

说实话，编译器开发听起来吓人，但拆开来看，无非就是「解析文本 → 构建树 → 查表 → 生成指令」。STL 的容器和算法正好覆盖了这些需求：std::variant 处理异构节点，std::unordered_map 做快速查找，std::vector 存指令流。

我记得第一次用 STL 写完一个迷你编译器时，最大的感受就是：原来那些编译原理课本上的概念，用 STL 实现起来这么直接。你不需要自己写红黑树、不用手撸哈希表、不用操心内存泄漏——STL 把这些都包了。

如果你正在考虑写一个自己的脚本语言或者 DSL，别犹豫，拿起 STL 开干吧。从 AST 到符号表再到 IR，每一步都有现成的工具等着你。

公众号:蓝海资料掘金营，微信deep3321
← 上一章 📖 返回目录 下一章 →