01-手写一个简单的编译器¶

enum class TokenType {
    // 关键字
    INT,        // int
    RETURN,     // return

    // 标识符和字面量
    IDENTIFIER, // 变量名、函数名
    NUMBER,     // 数字

    // 运算符
    ASSIGN,     // =
    PLUS,       // +
    MINUS,      // -
    MULTIPLY,   // *
    DIVIDE,     // /

    // 分隔符
    SEMICOLON,  // ;
    LPAREN,     // (
    RPAREN,     // )
    LBRACE,     // {
    RBRACE,     // }

    // 特殊
    END,        // 文件结束
    INVALID     // 非法字符
};

// lexer.h
#ifndef LEXER_H
#define LEXER_H

#include <string>
#include <vector>
#include <cctype>

enum class TokenType {
    INT, RETURN, IDENTIFIER, NUMBER,
    ASSIGN, PLUS, MINUS, MULTIPLY, DIVIDE,
    SEMICOLON, LPAREN, RPAREN, LBRACE, RBRACE,
    END, INVALID
};

struct Token {
    TokenType type;
    std::string value;
    int line;
    int column;
};

class Lexer {
public:
    Lexer(const std::string& source);
    std::vector<Token> tokenize();

private:
    std::string source;
    size_t pos;
    int line;
    int column;

    char current() const;
    char advance();
    void skipWhitespace();
    Token readNumber();
    Token readIdentifier();
    Token readOperator();
};

#endif

// lexer.cpp
#include "lexer.h"

Lexer::Lexer(const std::string& source)
    : source(source), pos(0), line(1), column(1) {}

char Lexer::current() const {
    if (pos >= source.length()) return '\0';
    return source[pos];
}

char Lexer::advance() {
    char c = current();
    pos++;
    if (c == '\n') {
        line++;
        column = 1;
    } else {
        column++;
    }
    return c;
}

void Lexer::skipWhitespace() {
    while (std::isspace(current())) {
        advance();
    }
}

Token Lexer::readNumber() {
    std::string value;
    int startLine = line;
    int startCol = column;

    while (std::isdigit(current())) {
        value += advance();
    }

    return {TokenType::NUMBER, value, startLine, startCol};
}

Token Lexer::readIdentifier() {
    std::string value;
    int startLine = line;
    int startCol = column;

    while (std::isalnum(current()) || current() == '_') {
        value += advance();
    }

    TokenType type = TokenType::IDENTIFIER;
    if (value == "int") type = TokenType::INT;
    else if (value == "return") type = TokenType::RETURN;

    return {type, value, startLine, startCol};
}

Token Lexer::readOperator() {
    char c = current();
    int startLine = line;
    int startCol = column;
    advance();

    switch (c) {
        case '=': return {TokenType::ASSIGN, "=", startLine, startCol};
        case '+': return {TokenType::PLUS, "+", startLine, startCol};
        case '-': return {TokenType::MINUS, "-", startLine, startCol};
        case '*': return {TokenType::MULTIPLY, "*", startLine, startCol};
        case '/': return {TokenType::DIVIDE, "/", startLine, startCol};
        case ';': return {TokenType::SEMICOLON, ";", startLine, startCol};
        case '(': return {TokenType::LPAREN, "(", startLine, startCol};
        case ')': return {TokenType::RPAREN, ")", startLine, startCol};
        case '{': return {TokenType::LBRACE, "{", startLine, startCol};
        case '}': return {TokenType::RBRACE, "}", startLine, startCol};
        default: return {TokenType::INVALID, std::string(1, c), startLine, startCol};
    }
}

std::vector<Token> Lexer::tokenize() {
    std::vector<Token> tokens;

    while (current() != '\0') {
        skipWhitespace();

        if (current() == '\0') break;

        if (std::isdigit(current())) {
            tokens.push_back(readNumber());
        } else if (std::isalpha(current()) || current() == '_') {
            tokens.push_back(readIdentifier());
        } else {
            tokens.push_back(readOperator());
        }
    }

    tokens.push_back({TokenType::END, "", line, column});
    return tokens;
}

// ast.h
#ifndef AST_H
#define AST_H

#include <string>
#include <vector>
#include <memory>

// 前向声明
struct ASTNode;  // struct结构体：自定义复合数据类型
struct Program;
struct VarDecl;
struct BinaryOp;
struct Number;
struct Identifier;
struct ReturnStmt;

// 访问者模式
class ASTVisitor {
public:
    virtual ~ASTVisitor() = default;
    virtual void visit(Program* node) = 0;
    virtual void visit(VarDecl* node) = 0;
    virtual void visit(BinaryOp* node) = 0;
    virtual void visit(Number* node) = 0;
    virtual void visit(Identifier* node) = 0;
    virtual void visit(ReturnStmt* node) = 0;
};

// AST节点基类
struct ASTNode {
    virtual ~ASTNode() = default;
    virtual void accept(ASTVisitor* visitor) = 0;
};

// 程序节点
struct Program : ASTNode {
    std::vector<std::unique_ptr<ASTNode>> statements;
    void accept(ASTVisitor* visitor) override { visitor->visit(this); }
};

// 变量声明
struct VarDecl : ASTNode {
    std::string type;
    std::string name;
    std::unique_ptr<ASTNode> initializer;
    void accept(ASTVisitor* visitor) override { visitor->visit(this); }
};

// 二元运算
struct BinaryOp : ASTNode {
    std::string op;
    std::unique_ptr<ASTNode> left;
    std::unique_ptr<ASTNode> right;
    void accept(ASTVisitor* visitor) override { visitor->visit(this); }
};

// 数字字面量
struct Number : ASTNode {
    int value;
    explicit Number(int v) : value(v) {}
    void accept(ASTVisitor* visitor) override { visitor->visit(this); }
};

// 标识符
struct Identifier : ASTNode {
    std::string name;
    explicit Identifier(std::string n) : name(std::move(n)) {}
    void accept(ASTVisitor* visitor) override { visitor->visit(this); }
};

// 返回语句
struct ReturnStmt : ASTNode {
    std::unique_ptr<ASTNode> expression;
    void accept(ASTVisitor* visitor) override { visitor->visit(this); }
};

#endif

// parser.h
#ifndef PARSER_H
#define PARSER_H

#include "lexer.h"
#include "ast.h"
#include <memory>

class Parser {
public:
    explicit Parser(const std::vector<Token>& tokens);
    std::unique_ptr<Program> parse();

private:
    std::vector<Token> tokens;
    size_t pos;

    Token& current();
    Token& peek(size_t offset);
    Token& advance();
    bool match(TokenType type);
    Token& expect(TokenType type);

    std::unique_ptr<Program> parseProgram();
    std::unique_ptr<ASTNode> parseStatement();
    std::unique_ptr<VarDecl> parseVarDecl();
    std::unique_ptr<ReturnStmt> parseReturnStmt();
    std::unique_ptr<ASTNode> parseExpression();
    std::unique_ptr<ASTNode> parseTerm();
    std::unique_ptr<ASTNode> parseFactor();
};

#endif

// parser.cpp
#include "parser.h"
#include <stdexcept>

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

Token& Parser::current() {
    return tokens[pos];
}

Token& Parser::peek(size_t offset) {
    if (pos + offset >= tokens.size()) {
        return tokens.back();
    }
    return tokens[pos + offset];
}

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

bool Parser::match(TokenType type) {
    if (current().type == type) {
        advance();
        return true;
    }
    return false;
}

Token& Parser::expect(TokenType type) {
    if (current().type != type) {
        throw std::runtime_error("Expected token type " + std::to_string(static_cast<int>(type)));
    }
    return advance();
}

std::unique_ptr<Program> Parser::parse() {
    return parseProgram();
}

std::unique_ptr<Program> Parser::parseProgram() {
    auto program = std::make_unique<Program>();

    while (current().type != TokenType::END) {
        program->statements.push_back(parseStatement());
    }

    return program;
}

std::unique_ptr<ASTNode> Parser::parseStatement() {
    if (current().type == TokenType::INT) {
        return parseVarDecl();
    } else if (current().type == TokenType::RETURN) {
        return parseReturnStmt();
    }

    throw std::runtime_error("Unexpected token in statement");
}

std::unique_ptr<VarDecl> Parser::parseVarDecl() {
    auto decl = std::make_unique<VarDecl>();

    // int
    decl->type = advance().value;

    // identifier
    decl->name = expect(TokenType::IDENTIFIER).value;

    // = expression
    if (match(TokenType::ASSIGN)) {
        decl->initializer = parseExpression();
    }

    // ;
    expect(TokenType::SEMICOLON);

    return decl;
}

std::unique_ptr<ReturnStmt> Parser::parseReturnStmt() {
    auto stmt = std::make_unique<ReturnStmt>();
    advance(); // return

    if (current().type != TokenType::SEMICOLON) {
        stmt->expression = parseExpression();
    }

    expect(TokenType::SEMICOLON);
    return stmt;
}

std::unique_ptr<ASTNode> Parser::parseExpression() {
    auto left = parseTerm();

    while (current().type == TokenType::PLUS || current().type == TokenType::MINUS) {
        auto op = std::make_unique<BinaryOp>();
        op->op = advance().value;
        op->left = std::move(left);
        op->right = parseTerm();
        left = std::move(op);
    }

    return left;
}

std::unique_ptr<ASTNode> Parser::parseTerm() {
    auto left = parseFactor();

    while (current().type == TokenType::MULTIPLY || current().type == TokenType::DIVIDE) {
        auto op = std::make_unique<BinaryOp>();
        op->op = advance().value;
        op->left = std::move(left);
        op->right = parseFactor();
        left = std::move(op);
    }

    return left;
}

std::unique_ptr<ASTNode> Parser::parseFactor() {
    if (current().type == TokenType::NUMBER) {
        int value = std::stoi(advance().value);
        return std::make_unique<Number>(value);
    } else if (current().type == TokenType::IDENTIFIER) {
        return std::make_unique<Identifier>(advance().value);
    } else if (match(TokenType::LPAREN)) {
        auto expr = parseExpression();
        expect(TokenType::RPAREN);
        return expr;
    }

    throw std::runtime_error("Unexpected token in factor");
}

// codegen.h
#ifndef CODEGEN_H
#define CODEGEN_H

#include "ast.h"
#include <sstream>
#include <unordered_map>

class CodeGenerator : public ASTVisitor {
public:
    std::string generate(ASTNode* root);

    // Visitor方法
    void visit(Program* node) override;
    void visit(VarDecl* node) override;
    void visit(BinaryOp* node) override;
    void visit(Number* node) override;
    void visit(Identifier* node) override;
    void visit(ReturnStmt* node) override;

private:
    std::stringstream output;
    std::unordered_map<std::string, int> variables; // 变量名 -> 栈偏移
    int stackOffset = 0;
    int labelCounter = 0;

    void emit(const std::string& line);
    std::string newLabel();
};

#endif

// codegen.cpp
#include "codegen.h"

std::string CodeGenerator::generate(ASTNode* root) {
    output.str("");
    output.clear();
    variables.clear();
    stackOffset = 0;
    labelCounter = 0;

    // 第一遍：生成函数体代码，确定栈空间需求
    root->accept(this);
    std::string bodyCode = output.str();

    // 第二遍：生成完整程序（现在已知栈空间大小）
    output.str("");
    output.clear();

    // 汇编文件头
    emit(".globl main");
    emit(".text");
    emit("main:");
    emit("    push %rbp");
    emit("    mov %rsp, %rbp");
    // 为局部变量分配栈空间（16字节对齐）
    // 必须在使用push/pop前预留空间，否则push会覆盖局部变量
    if (stackOffset != 0) {
        int stackSpace = ((-stackOffset) + 15) & ~15;
        emit("    sub $" + std::to_string(stackSpace) + ", %rsp");
    }

    // 插入函数体代码
    output << bodyCode;

    // 函数结束
    emit("    mov %rbp, %rsp");
    emit("    pop %rbp");
    emit("    ret");

    return output.str();
}

void CodeGenerator::emit(const std::string& line) {
    output << line << "\n";
}

std::string CodeGenerator::newLabel() {
    return ".L" + std::to_string(labelCounter++);
}

void CodeGenerator::visit(Program* node) {
    for (auto& stmt : node->statements) {
        stmt->accept(this);
    }
}

void CodeGenerator::visit(VarDecl* node) {
    // 为变量分配栈空间
    stackOffset -= 4; // 假设int为4字节
    variables[node->name] = stackOffset;

    if (node->initializer) {
        // 计算初始值
        node->initializer->accept(this);
        // 结果在eax中,存入变量位置
        emit("    mov %eax, " + std::to_string(stackOffset) + "(%rbp)");
    }
}

void CodeGenerator::visit(BinaryOp* node) {
    // 生成右操作数
    node->right->accept(this);
    emit("    push %rax"); // 保存右操作数

    // 生成左操作数
    node->left->accept(this);
    emit("    pop %rbx");  // 恢复右操作数到rbx

    // 执行运算
    if (node->op == "+") {
        emit("    add %ebx, %eax");
    } else if (node->op == "-") {
        emit("    sub %ebx, %eax");
    } else if (node->op == "*") {
        emit("    imul %ebx, %eax");
    } else if (node->op == "/") {
        emit("    mov %eax, %edx");
        emit("    sar $31, %edx");  // 符号扩展
        emit("    idiv %ebx");
    }
}

void CodeGenerator::visit(Number* node) {
    emit("    mov $" + std::to_string(node->value) + ", %eax");
}

void CodeGenerator::visit(Identifier* node) {
    auto it = variables.find(node->name);
    if (it != variables.end()) {
        emit("    mov " + std::to_string(it->second) + "(%rbp), %eax");
    } else {
        throw std::runtime_error("Undefined variable: " + node->name);
    }
}

void CodeGenerator::visit(ReturnStmt* node) {
    if (node->expression) {
        node->expression->accept(this);
        // 结果已经在eax中,作为返回值
    } else {
        emit("    mov $0, %eax");
    }
}

// main.cpp
#include <iostream>  // 引入头文件
#include <fstream>
#include "lexer.h"
#include "parser.h"
#include "codegen.h"

int main(int argc, char* argv[]) {  // 指针：存储变量的内存地址
    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " <source file>" << std::endl;
        return 1;
    }

    // 读取源文件
    std::ifstream file(argv[1]);
    if (!file) {
        std::cerr << "Cannot open file: " << argv[1] << std::endl;
        return 1;
    }

    std::string source((std::istreambuf_iterator<char>(file)),
                       std::istreambuf_iterator<char>());

    try {
        // 词法分析
        std::cout << "=== Lexical Analysis ===" << std::endl;
        Lexer lexer(source);
        auto tokens = lexer.tokenize();

        for (const auto& token : tokens) {
            std::cout << "Token: " << static_cast<int>(token.type)
                      << " Value: " << token.value << std::endl;
        }

        // 语法分析
        std::cout << "\n=== Syntax Analysis ===" << std::endl;
        Parser parser(tokens);
        auto ast = parser.parse();
        std::cout << "Parsing successful!" << std::endl;

        // 代码生成
        std::cout << "\n=== Code Generation ===" << std::endl;
        CodeGenerator codegen;
        std::string assembly = codegen.generate(ast.get());
        std::cout << assembly << std::endl;

        // 保存汇编文件
        std::ofstream out("output.s");
        out << assembly;
        out.close();

        std::cout << "\nAssembly code saved to output.s" << std::endl;
        std::cout << "Compile with: gcc output.s -o output" << std::endl;

    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}