从零构建C++语法分析器（手把手教你实现C++语言解析器）

什么是语法分析器？

语法分析器是编译器前端的重要组成部分。它的任务是根据语言的文法规则，判断输入的记号序列是否合法，并构建出抽象语法树（Abstract Syntax Tree, AST）。

例如，对于表达式 a + b * c，词法分析器会将其拆分为记号：[ID:a, PLUS, ID:b, STAR, ID:c]。语法分析器则要识别这是一个合法的算术表达式，并构建出如下结构：

      +     / \    a   *       / \      b   c

实现前的准备：定义基础结构

我们将使用递归下降（Recursive Descent）方法来实现语法分析器。首先，定义几个关键的数据结构。

1. Token 类型定义

enum class TokenType {    IDENTIFIER,    NUMBER,    PLUS,    MINUS,    STAR,    SLASH,    LPAREN,    RPAREN,    EOF_TOKEN};struct Token {    TokenType type;    std::string lexeme;    int line;    Token(TokenType t, std::string l, int ln)        : type(t), lexeme(std::move(l)), line(ln) {}};

2. AST 节点基类

class Expr {public:    virtual ~Expr() = default;};class BinaryExpr : public Expr {public:    std::unique_ptr<Expr> left;    TokenType op;    std::unique_ptr<Expr> right;    BinaryExpr(std::unique_ptr<Expr> l, TokenType o, std::unique_ptr<Expr> r)        : left(std::move(l)), op(o), right(std::move(r)) {}};class LiteralExpr : public Expr {public:    std::string value;    explicit LiteralExpr(std::string v) : value(std::move(v)) {}};

核心：递归下降解析器实现

我们以支持加减乘除和括号的简单表达式为例，实现一个符合运算优先级的解析器。

解析函数设计

我们将按照运算符优先级从低到高编写函数：

• parseExpression() → 处理加减
• parseTerm() → 处理乘除
• parseFactor() → 处理数字、标识符和括号

完整 Parser 类代码

class Parser {private:    std::vector<Token> tokens;    size_t current = 0;    bool match(TokenType type) {        if (isAtEnd()) return false;        if (tokens[current].type != type) return false;        current++;        return true;    }    Token consume(TokenType type, const std::string& message) {        if (!match(type)) {            // 简化错误处理            throw std::runtime_error(message);        }        return tokens[current - 1];    }    bool isAtEnd() {        return current >= tokens.size();    }    std::unique_ptr<Expr> parseExpression() {        return parseTerm();    }    std::unique_ptr<Expr> parseTerm() {        auto expr = parseFactor();        while (match(TokenType::PLUS) || match(TokenType::MINUS)) {            Token op = tokens[current - 1];            auto right = parseFactor();            expr = std::make_unique<BinaryExpr>(std::move(expr), op.type, std::move(right));        }        return expr;    }    std::unique_ptr<Expr> parseFactor() {        auto expr = parsePrimary();        while (match(TokenType::STAR) || match(TokenType::SLASH)) {            Token op = tokens[current - 1];            auto right = parsePrimary();            expr = std::make_unique<BinaryExpr>(std::move(expr), op.type, std::move(right));        }        return expr;    }    std::unique_ptr<Expr> parsePrimary() {        if (match(TokenType::NUMBER) || match(TokenType::IDENTIFIER)) {            return std::make_unique<LiteralExpr>(tokens[current - 1].lexeme);        }        if (match(TokenType::LPAREN)) {            auto expr = parseExpression();            consume(TokenType::RPAREN, "Expect ')' after expression.");            return expr;        }        throw std::runtime_error("Unexpected token in primary.");    }public:    explicit Parser(std::vector<Token> t) : tokens(std::move(t)) {}    std::unique_ptr<Expr> parse() {        try {            return parseExpression();        } catch (const std::exception& e) {            std::cerr << "Parse error: " << e.what() << std::endl;            return nullptr;        }    }};

如何测试你的 C++ 语法分析器？

你可以编写一个简单的主函数，模拟词法分析结果并调用解析器：

int main() {    // 模拟词法分析器输出：a + b * 2    std::vector<Token> tokens = {        Token(TokenType::IDENTIFIER, "a", 1),        Token(TokenType::PLUS, "+", 1),        Token(TokenType::IDENTIFIER, "b", 1),        Token(TokenType::STAR, "*", 1),        Token(TokenType::NUMBER, "2", 1),        Token(TokenType::EOF_TOKEN, "", 1)    };    Parser parser(tokens);    auto ast = parser.parse();    if (ast) {        std::cout << "Parsing succeeded! AST built." << std::endl;    } else {        std::cout << "Parsing failed." << std::endl;    }    return 0;}

总结与进阶

通过本教程，你已经掌握了如何用C++实现一个基础的C++语法分析器。虽然这个例子只处理了算术表达式，但它为你理解C++编译器原理打下了坚实基础。

下一步，你可以尝试：

• 添加更多运算符（如比较、逻辑运算）
• 支持函数调用和变量声明
• 实现更完善的错误恢复机制
• 结合真正的词法分析器（如使用Flex或手写）

记住，手把手实现语法分析器不仅能加深你对编程语言的理解，还能提升你的系统编程能力。希望这篇C++语言解析教程对你有所帮助！