深入理解C++抽象语法树（AST）

什么是抽象语法树？

抽象语法树是一种树状数据结构，用于表示源代码的语法结构。它省略了源代码中的括号、分号等不影响语义的细节，只保留程序的关键结构信息。例如，表达式 2 + 3 * 4 在 AST 中会以乘法节点为子节点、加法节点为根的形式组织，体现运算优先级。

为什么需要自己实现 AST？

虽然像 Clang 这样的成熟工具已经提供了强大的 C++ AST 支持，但手动实现一个简易 AST 能帮助你：

• 深入理解编译器前端的工作原理
• 掌握 C++语法分析 的基本流程
• 为后续开发代码检查工具、重构引擎打下基础

实现步骤概览

我们将通过以下三步构建一个支持简单算术表达式的 AST：

1. 定义 AST 节点的基类和派生类
2. 编写词法分析器（Lexer）
3. 实现递归下降解析器（Parser）

第一步：定义 AST 节点

我们首先定义一个抽象基类 Expr，然后为数字、二元运算等创建具体节点类型。

#include <memory>#include <string>class Expr {public:    virtual ~Expr() = default;};// 数字字面量节点class NumberExpr : public Expr {public:    double value;    NumberExpr(double val) : value(val) {}};// 二元运算节点（如 +, -, *, /）class BinaryExpr : public Expr {public:    char op; // 运算符    std::unique_ptr<Expr> left;    std::unique_ptr<Expr> right;    BinaryExpr(char operation,               std::unique_ptr<Expr> lhs,               std::unique_ptr<Expr> rhs)        : op(operation), left(std::move(lhs)), right(std::move(rhs)) {}};

第二步：词法分析器（Lexer）

词法分析器将输入字符串分解为一个个“词法单元”（Token），比如数字、运算符等。

enum class TokenType {    Number,    Plus, Minus, Star, Slash,    LParen, RParen,    EndOfFile};struct Token {    TokenType type;    double number_value = 0.0;};class Lexer {    std::string input;    size_t pos = 0;public:    Lexer(const std::string& str) : input(str) {}    Token getNextToken() {        // 跳过空白字符        while (pos < input.size() && isspace(input[pos]))            ++pos;        if (pos >= input.size())            return {TokenType::EndOfFile};        char c = input[pos];        if (isdigit(c) || c == '.') {            // 解析数字            size_t start = pos;            while (pos < input.size() &&                   (isdigit(input[pos]) || input[pos] == '.'))                ++pos;            double val = std::stod(input.substr(start, pos - start));            return {TokenType::Number, val};        }        ++pos; // 消费当前字符        switch (c) {            case '+': return {TokenType::Plus};            case '-': return {TokenType::Minus};            case '*': return {TokenType::Star};            case '/': return {TokenType::Slash};            case '(': return {TokenType::LParen};            case ')': return {TokenType::RParen};            default:                throw std::runtime_error("未知字符: " + std::string(1, c));        }    }};

第三步：递归下降解析器

解析器根据语法规则，递归地构建 AST。我们支持带括号和四则运算的表达式，并遵循标准运算优先级。

class Parser {    Lexer lexer;    Token current_token;    void advance() {        current_token = lexer.getNextToken();    }public:    Parser(const std::string& input) : lexer(input) {        advance(); // 获取第一个 token    }    std::unique_ptr<Expr> parseExpression(int precedence = 0);    std::unique_ptr<Expr> parsePrimary() {        Token tok = current_token;        if (tok.type == TokenType::Number) {            advance();            return std::make_unique<NumberExpr>(tok.number_value);        }        if (tok.type == TokenType::LParen) {            advance();            auto expr = parseExpression();            if (current_token.type != TokenType::RParen) {                throw std::runtime_error("缺少右括号")；            }            advance();            return expr;        }        throw std::runtime_error("意外的 token");    }    int getPrecedence(TokenType op) {        switch (op) {            case TokenType::Plus:            case TokenType::Minus: return 10;            case TokenType::Star:            case TokenType::Slash: return 20;            default: return 0;        }    }    std::unique_ptr<Expr> parseExpression(int precedence) {        auto lhs = parsePrimary();        while (true) {            int prec = getPrecedence(current_token.type);            if (prec <= precedence) break;            TokenType op = current_token.type;            advance();            auto rhs = parseExpression(prec);            lhs = std::make_unique<BinaryExpr>(                static_cast<char>(op), std::move(lhs), std::move(rhs)            );        }        return lhs;    }};

使用示例

现在我们可以用这个简易解析器构建 AST 了：

int main() {    try {        Parser parser("(2 + 3) * 4");        auto ast = parser.parseExpression();        // 此时 ast 指向一个 BinaryExpr 节点，其 left 是 (2+3)，right 是 4        std::cout << "AST 构建成功！\n";    } catch (const std::exception& e) {        std::cerr << "错误: " << e.what() << std::endl;    }    return 0;}

总结

通过本教程，你已经掌握了如何从零开始实现一个支持基本算术表达式的 C++抽象语法树。虽然这只是一个简化版，但它涵盖了 AST实现教程 的核心思想：定义节点、词法分析、语法解析。

进一步学习的方向包括：

• 支持变量、函数调用等更复杂的语法
• 添加语义分析（如类型检查）
• 集成到实际的 编程语言解析 工具链中

记住，理解 C++语法分析 不仅能提升你的底层编程能力，还能为你打开编译器、解释器、静态分析工具等高级领域的大门。动手实践是掌握这些知识的最佳方式！