37、C++项目实战：简易编译器（语法分析）

语法分析，说白了就是让计算机理解你写的代码结构对不对。

我刚开始做编译器项目时，总觉得词法分析完了就万事大吉。结果一跑测试，各种括号不匹配、分号缺失的问题全冒出来了。嗯，那时候我才意识到——语法分析才是编译器的骨架。

语法分析到底在做什么？

词法分析把源代码切成了一个个token，比如关键字、标识符、运算符。但光有token还不够，你得告诉计算机这些token怎么组合才是合法的。

举个例子：

int a = 5 + 3;

词法分析会输出：int、a、=、5、+、3、;。

语法分析要回答的问题是：这个序列是否符合C++的语法规则？

我个人习惯把语法分析比作「搭积木」。每个语法规则就是一块积木的形状，只有形状匹配的积木才能拼在一起。

两种主流方法：自顶向下 vs 自底向上

语法分析的实现方式主要有两种。我当年在学校里学的时候，老师讲得特别理论化，搞得我一头雾水。后来自己动手写了一个，才真正搞明白。

方法 原理 优点 缺点
自顶向下（递归下降） 从起始符号开始，不断展开非终结符 实现简单，容易调试 不能处理左递归
自底向上（LR） 从输入token开始，不断归约到起始符号 能处理更多文法 实现复杂，表驱动难调试

我个人强烈推荐初学者用递归下降法。为什么？因为代码写出来跟语法规则几乎一一对应，出错了也好查。

核心观点：对于简易编译器，递归下降法是最务实的选择。别一上来就搞LR，那是给自己找麻烦。

递归下降法的实现套路

递归下降法的核心思想很简单：每个非终结符对应一个函数。比如表达式、语句、声明，各写一个解析函数。

来看一个具体的例子。假设我们要解析简单的算术表达式：

// 语法规则（简化版）
// expr    -> term ('+' term)*
// term    -> factor ('*' factor)*
// factor  -> NUMBER | '(' expr ')'

class Parser {
public:
    Parser(const std::vector<Token>& tokens) 
        : tokens(tokens), pos(0) {}

    // 解析入口
    ASTNode* parse() {
        return parseExpr();
    }

private:
    ASTNode* parseExpr() {
        ASTNode* left = parseTerm();
        while (match(TokenType::PLUS)) {
            Token op = previous();
            ASTNode* right = parseTerm();
            left = new BinaryOpNode(op, left, right);
        }
        return left;
    }

    ASTNode* parseTerm() {
        ASTNode* left = parseFactor();
        while (match(TokenType::MUL)) {
            Token op = previous();
            ASTNode* right = parseFactor();
            left = new BinaryOpNode(op, left, right);
        }
        return left;
    }

    ASTNode* parseFactor() {
        if (match(TokenType::NUMBER)) {
            return new NumberNode(previous());
        }
        if (match(TokenType::LPAREN)) {
            ASTNode* expr = parseExpr();
            consume(TokenType::RPAREN, "缺少右括号");
            return expr;
        }
        error("意外的token");
        return nullptr;
    }

    // 辅助方法
    bool match(TokenType type) {
        if (check(type)) {
            advance();
            return true;
        }
        return false;
    }

    bool check(TokenType type) {
        if (pos >= tokens.size()) return false;
        return tokens[pos].type == type;
    }

    Token advance() {
        return tokens[pos++];
    }

    Token previous() {
        return tokens[pos - 1];
    }

    void consume(TokenType type, const std::string& msg) {
        if (check(type)) {
            advance();
        } else {
            error(msg);
        }
    }

    void error(const std::string& msg) {
        throw std::runtime_error("语法错误: " + msg);
    }

    const std::vector<Token>& tokens;
    size_t pos;
};

你看，每个函数都对应一条语法规则。parseExpr对应expr规则，parseTerm对应term规则。这种一一对应的关系，让代码特别好理解。

小技巧：写递归下降解析器时，我习惯先画语法图，再写代码。语法图画清楚了，代码就是翻译工作。

抽象语法树（AST）的构建

语法分析不只是检查语法正确性，更重要的是构建抽象语法树。AST是编译器的中间表示，后续的语义分析、代码生成都依赖它。

我在项目中遇到过一个问题：一开始我把AST节点设计得特别复杂，每个节点都带了很多冗余信息。结果内存占用大，遍历速度还慢。后来我学乖了——AST节点只保留必要信息，其他东西放到符号表里。

// AST节点基类
class ASTNode {
public:
    virtual ~ASTNode() = default;
    virtual void accept(Visitor& visitor) = 0;
};

// 数字节点
class NumberNode : public ASTNode {
public:
    explicit NumberNode(int value) : value(value) {}
    void accept(Visitor& visitor) override {
        visitor.visit(this);
    }
    int value;
};

// 二元运算节点
class BinaryOpNode : public ASTNode {
public:
    BinaryOpNode(Token op, ASTNode* left, ASTNode* right)
        : op(op), left(left), right(right) {}
    void accept(Visitor& visitor) override {
        visitor.visit(this);
    }
    Token op;
    std::unique_ptr<ASTNode> left;
    std::unique_ptr<ASTNode> right;
};

这里用了访问者模式。为什么要用这个模式？因为后续你可能需要做类型检查、代码生成、优化等操作。访问者模式让你在不修改AST节点类的前提下，添加新的操作。

注意：AST节点一定要用智能指针管理内存。我见过有人用裸指针，结果内存泄漏查了一整天。C++11以后，请忘掉new和delete。

错误恢复机制

语法分析中最头疼的问题是什么？是错误恢复。

你想想看，用户写错了一行代码，你不能直接崩溃退出吧？你得尽量往后分析，把所有的错误都找出来。

我曾经在一个项目里，用户写了500行代码，第3行就少了个分号。我的解析器直接崩溃了，后面497行的错误一个都没报出来。用户气得直接打电话骂我。

从那以后，我学会了错误恢复的几种策略：

  1. 恐慌模式：遇到错误时，跳过当前token，直到遇到同步标记（比如分号、右大括号）。
  2. 插入模式：如果缺少某个token（比如分号），自动插入一个，继续解析。
  3. 删除模式：如果多了一个token，直接删除，继续解析。

最简单的实现是恐慌模式：

void synchronize() {
    advance(); // 跳过错误token
    while (pos < tokens.size()) {
        if (tokens[pos].type == TokenType::SEMICOLON ||
            tokens[pos].type == TokenType::RBRACE) {
            return;
        }
        advance();
    }
}

这个函数会在遇到错误时调用，一直跳到下一个分号或右大括号。虽然会漏掉一些错误，但至少不会崩溃。

SVG：语法分析核心流程

下面这张图展示了语法分析的整体流程，从token序列到AST的完整过程：

语法分析核心流程 Token序列 词法分析输出 递归下降解析器 parseExpr → parseTerm → parseFactor 抽象语法树 (AST) 供后续阶段使用 错误恢复机制 恐慌模式 / 插入 / 删除 AST结构示例：5 + 3 * 2 + 5 * 3 2

实战中的几个坑

写语法分析器的时候，有几个坑我踩过，分享给你：

  • 左递归问题：递归下降法不能直接处理左递归。比如expr ::= expr '+' term，会无限递归。解决办法是改写成右递归或循环。
  • 运算符优先级：我一开始把加减乘除写在一个函数里，结果解析1 + 2 * 3得到9而不是7。后来老老实实按优先级分层写。
  • 内存泄漏：AST节点用裸指针new出来，忘记delete。用std::unique_ptr或者std::shared_ptr，省心。

我的建议：先写一个最简单的版本，只支持整数加减法。跑通了再慢慢加功能。别想一口吃成胖子。

总结

语法分析是编译器的核心环节。递归下降法实现简单，适合初学者。关键是要理解语法规则和代码的一一对应关系，以及AST的构建方法。

嗯，今天就聊到这里。代码写好了记得多跑测试，各种边界情况都要覆盖到。

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

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