C++如何实现一个简单的AST解析器_C++编译原理与抽象语法树解析器实现-C++-PHP中文网

C++如何实现一个简单的AST解析器_C++编译原理与抽象语法树解析器实现

下次还敢

发布： 2025-11-18 12:08:12

原创

206人浏览过

<p>首先实现词法分析器将源码拆分为Token，接着设计AST节点表示数字与二元操作，再通过递归下降解析器按优先级构建表达式树，最终组合Lexer与Parser完成对“2 + 3 * 4”等算术表达式的AST解析。</p>

c++如何实现一个简单的ast解析器_c++编译原理与抽象语法树解析器实现

实现一个简单的AST（抽象语法树）解析器，需要从词法分析开始，逐步构建语法结构。C++中可以通过手动编写递归下降解析器来完成这一过程。下面是一个简化但完整的流程，帮助你理解编译原理中的核心环节：词法分析、语法分析和AST构建。

词法分析器（Lexer）

词法分析器负责将源代码拆分为一个个有意义的“记号”（Token）。例如，表达式 2 + 3 * 4 可以被分解为数字、操作符等Token。

定义Token类型：

enum TokenType {
    TOKEN_NUMBER,
    TOKEN_PLUS,
    TOKEN_MINUS,
    TOKEN_STAR,
    TOKEN_SLASH,
    TOKEN_EOF
};

登录后复制

每个Token包含类型和可能的数值（如数字的值）：

struct Token {
    TokenType type;
    double value; // 仅用于数字
};

登录后复制

Lexer类读取输入字符串，逐字符扫描并生成Token序列：

立即学习“C++免费学习笔记（深入）”；

class Lexer {
public:
    Lexer(const std::string& src) : source(src), pos(0) {}
<pre class='brush:php;toolbar:false;'>Token nextToken() {
    if (pos >= source.length()) return {TOKEN_EOF, 0};

    char c = source[pos];

    if (isdigit(c)) {
        std::string num;
        while (pos < source.length() && isdigit(source[pos])) {
            num += source[pos++];
        }
        return {TOKEN_NUMBER, std::stod(num)};
    }

    if (c == '+') { pos++; return {TOKEN_PLUS, 0}; }
    if (c == '-') { pos++; return {TOKEN_MINUS, 0}; }
    if (c == '*') { pos++; return {TOKEN_STAR, 0}; }
    if (c == '/') { pos++; return {TOKEN_SLASH, 0}; }

    pos++; // 跳过未知字符
    return nextToken();
}

登录后复制

private: std::string source; size_t pos; };

AST节点设计

抽象语法树由不同类型的节点构成。常见的有数字节点和二元操作节点。

struct ASTNode {
    virtual ~ASTNode() = default;
};

登录后复制

数字节点存储常量值：

struct NumberNode : ASTNode {
    double value;
    NumberNode(double v) : value(v) {}
};

登录后复制

二元操作节点保存左右子节点和操作符：

struct BinaryOpNode : ASTNode {
    std::unique_ptr<ASTNode> left;
    std::unique_ptr<ASTNode> right;
    TokenType op;
<pre class='brush:php;toolbar:false;'>BinaryOpNode(TokenType o, std::unique_ptr<ASTNode> l, std::unique_ptr<ASTNode> r)
    : op(o), left(std::move(l)), right(std::move(r)) {}

登录后复制

};

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

递归下降解析器（Parser）

解析器根据语法规则从Token流构建AST。我们实现最简单的算术表达式解析，支持加减乘除，并遵循优先级。

语法大致如下：

expr → term (('+' | '-') term)*
term → factor (('*' | '/') factor)*
factor → NUMBER

解析器代码：

class Parser {
public:
    Parser(Lexer l) : lexer(std::move(l)) {
        currentToken = lexer.nextToken();
    }
<pre class='brush:php;toolbar:false;'>std::unique_ptr<ASTNode> parse() {
    return parseExpr();
}

登录后复制

private: Lexer lexer; Token currentToken;

void consume(TokenType expected) {
    if (currentToken.type == expected) {
        currentToken = lexer.nextToken();
    } else {
        throw std::runtime_error("Unexpected token");
    }
}

std::unique_ptr<ASTNode> parseExpr() {
    auto node = parseTerm();
    while (currentToken.type == TOKEN_PLUS || currentToken.type == TOKEN_MINUS) {
        TokenType op = currentToken.type;
        consume(op);
        auto rhs = parseTerm();
        node = std::make_unique<BinaryOpNode>(op, std::move(node), std::move(rhs));
    }
    return node;
}

std::unique_ptr<ASTNode> parseTerm() {
    auto node = parseFactor();
    while (currentToken.type == TOKEN_STAR || currentToken.type == TOKEN_SLASH) {
        TokenType op = currentToken.type;
        consume(op);
        auto rhs = parseFactor();
        node = std::make_unique<BinaryOpNode>(op, std::move(node), std::move(rhs));
    }
    return node;
}

std::unique_ptr<ASTNode> parseFactor() {
    if (currentToken.type == TOKEN_NUMBER) {
        auto node = std::make_unique<NumberNode>(currentToken.value);
        consume(TOKEN_NUMBER);
        return node;
    }
    throw std::runtime_error("Expected number");
}

登录后复制

};

测试与使用

将各部分组合起来，测试一个简单表达式：

int main() {
    std::string source = "2 + 3 * 4";
    Lexer lexer(source);
    Parser parser(std::move(lexer));
<pre class='brush:php;toolbar:false;'>try {
    auto ast = parser.parse();
    // 这里可以添加遍历AST并求值的逻辑
    std::cout << "AST parsed successfully.\n";
} catch (const std::exception& e) {
    std::cerr << "Parse error: " << e.what() << '\n';
}

return 0;

登录后复制

}

你可以进一步扩展这个解析器，加入变量、函数调用、控制流等结构。关键在于分层处理：先分词，再按优先级解析语法，最后构造树形结构。

基本上就这些。不复杂但容易忽略细节，比如Token消费时机和内存管理（这里用了unique_ptr自动释放）。理解这个流程后，就能在此基础上实现更完整的语言前端。

以上就是C++如何实现一个简单的AST解析器_C++编译原理与抽象语法树解析器实现的详细内容，更多请关注php中文网其它相关文章！