其他

如何用C++实现简易编译器：从词法分析到语法树构建

悠悠楠杉

2025-09-04

0 评论

4 阅读

正在检测是否收录...

09/04

从零构建编译器前端

当我在大学第一次尝试写编译器时，被那些复杂的理论概念吓得不轻。直到动手实现才发现，编译器开发就像搭积木，只要拆解成小模块，用C++也能构建出可运行的简易编译器。让我们从最基础的词法分析开始。

词法分析器的实现

词法分析的本质就是把字符流转化为有意义的单词（token）。我们先定义基础结构：

cpp
enum TokenType {
INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF
};

struct Token {
TokenType type;
std::string value;
};

实现词法分析器时，我习惯用正则表达式匹配模式。C++11的<regex>库派上用场：

cpp
std::vector tokenize(const std::string& input) {
static const std::vector<std::pair<std::regex, TokenType>> patterns {
{std::regex("^\d+"), INTEGER}, // 匹配整数
{std::regex("^\+"), PLUS}, // 匹配加号
// 其他运算符匹配规则...
};

std::vector<Token> tokens;
std::string remaining = input;

while(!remaining.empty()) {
    bool matched = false;
    for (const auto& [regex, type] : patterns) {
        std::smatch match;
        if (std::regex_search(remaining, match, regex)) {
            tokens.push_back({type, match.str()});
            remaining = match.suffix().str();
            matched = true;
            break;
        }
    }
    if (!matched) throw std::runtime_error("非法字符");
}
tokens.push_back({EOF, ""});
return tokens;

}

这个版本虽然简单，但已经能处理基础算术表达式。实际项目中，我会添加行列号记录以便错误定位。

构建抽象语法树（AST）

得到token流后，我们需要构建语法树。先定义AST节点基类：

cpp
class ASTNode {
public:
virtual ~ASTNode() = default;
virtual int evaluate() const = 0;
};

class NumberNode : public ASTNode {
int value;
public:
NumberNode(int val) : value(val) {}
int evaluate() const override { return value; }
};

class BinaryOpNode : public ASTNode {
std::unique_ptr left, right;
TokenType op;
public:
// 构造函数和evaluate实现...
};

递归下降语法分析

采用递归下降法解析表达式时，需要处理运算符优先级。我的经验是先写辅助函数：

cpp
std::uniqueptr parseexpression(const std::vector& tokens, sizet& pos) { auto node = parseterm(tokens, pos);
while (pos < tokens.size() &&
(tokens[pos].type == PLUS || tokens[pos].type == MINUS)) {
Token op = tokens[pos++];
auto right = parseterm(tokens, pos); node = std::makeunique(std::move(node), op.type, std::move(right));
}
return node;
}

std::uniqueptr parseterm(const std::vector& tokens, size_t& pos) {
// 类似处理乘除的高优先级运算
}

这种分层的解析方式能自然处理运算符优先级。记得在解析函数中加入错误恢复：

cpp if (tokens[pos].type != EXPECTED_TYPE) { throw std::runtime_error("语法错误：期待 " + tokenTypeToString(EXPECTED_TYPE) + " 但得到 " + tokens[pos].value); }