鸭梨公共文档

主题

使用 LLVM 构建 BrainFuck 编译器前端的完整指南 ​

1. 编译器开发主要步骤 ​

1.1 语言定义与规范 ​

  • 定义 BrainFuck 的 8 个有效字符：
    text
    > < + - . , [ ]
  • 建立内存模型规范：30000 字节的循环数组，初始指针位于中间位置

1.2 项目结构设计 ​

典型编译器前端项目结构：

text
bfc/
├── include/
│   └── ast.h         # AST 节点定义
├── src/
│   ├── lexer.cpp     # 词法分析
│   ├── parser.cpp    # 语法分析
│   ├── codegen.cpp   # IR 生成
│   └── main.cpp      # 主程序
├── runtime/
│   └── runtime.c     # IO 系统函数
└── CMakeLists.txt

1.3 核心组件实现流程 ​

2. 关键代码实现 ​

2.1 词法分析器（Lexer） ​

cpp
// lexer.cpp
enum Token {
    TOK_EOF, TOK_PTR_INC,   TOK_PTR_DEC,
    TOK_DATA_INC, TOK_DATA_DEC,
    TOK_OUTPUT, TOK_INPUT,
    TOK_LOOP_START, TOK_LOOP_END
};

class Lexer {
    std::string Input;
    size_t Position;
  
    char currentChar() { return Input[Position]; }
  
public:
    Lexer(const std::string &input) : Input(input), Position(0) {}
  
    int getNextToken() {
        while (Position < Input.size()) {
            switch (currentChar()) {
                case '>': Position++; return TOK_PTR_INC;
                case '<': Position++; return TOK_PTR_DEC;
                case '+': Position++; return TOK_DATA_INC;
                case '-': Position++; return TOK_DATA_DEC;
                case '.': Position++; return TOK_OUTPUT;
                case ',': Position++; return TOK_INPUT;
                case '[': Position++; return TOK_LOOP_START;
                case ']': Position++; return TOK_LOOP_END;
                default:  Position++; // 忽略其他字符
            }
        }
        return TOK_EOF;
    }
};

2.2 AST 节点定义 ​

cpp
// ast.h
class ExprAST {
public:
    virtual ~ExprAST() = default;
    virtual llvm::Value *codegen() = 0;
};

class LoopAST : public ExprAST {
    std::vector<std::unique_ptr<ExprAST>> Body;
public:
    LoopAST(std::vector<std::unique_ptr<ExprAST>> body)
        : Body(std::move(body)) {}
  
    llvm::Value *codegen() override;
};

class PtrMoveAST : public ExprAST {
    int Offset;
public:
    PtrMoveAST(int offset) : Offset(offset) {}
    llvm::Value *codegen() override;
};

2.3 IR 生成核心逻辑 ​

cpp
// codegen.cpp
static llvm::LLVMContext Context;
static llvm::IRBuilder<> Builder(Context);
static std::unique_ptr<llvm::Module> Module;

// 内存结构初始化
llvm::Value *initMemory() {
    auto *arrayTy = llvm::ArrayType::get(
        llvm::Type::getInt8Ty(Context), 30000);
    auto *glob = new llvm::GlobalVariable(
        *Module, arrayTy, false,
        llvm::GlobalValue::InternalLinkage,
        llvm::ConstantAggregateZero::get(arrayTy),
        "bf_memory");
  
    // 初始化指针
    auto *ptr = Builder.CreateGEP(
        arrayTy, glob,
        {Builder.getInt32(0), Builder.getInt32(15000)});
    return ptr;
}

// 生成循环结构
llvm::Value *LoopAST::codegen() {
    auto *func = Builder.GetInsertBlock()->getParent();
  
    // 创建基本块
    llvm::BasicBlock *condBB = llvm::BasicBlock::Create(Context, "loop_cond", func);
    llvm::BasicBlock *bodyBB = llvm::BasicBlock::Create(Context, "loop_body");
    llvm::BasicBlock *exitBB = llvm::BasicBlock::Create(Context, "loop_exit");
  
    Builder.CreateBr(condBB);
    Builder.SetInsertPoint(condBB);
  
    // 生成条件判断
    auto *cell = Builder.CreateLoad(Builder.getInt8Ty(), currentPtr);
    auto *cond = Builder.CreateICmpNE(
        cell, llvm::ConstantInt::get(Context, llvm::APInt(8, 0)));
    Builder.CreateCondBr(cond, bodyBB, exitBB);
  
    // 生成循环体
    func->getBasicBlockList().push_back(bodyBB);
    Builder.SetInsertPoint(bodyBB);
    for (auto &expr : Body) {
        expr->codegen();
    }
    Builder.CreateBr(condBB);
  
    // 设置退出块
    func->getBasicBlockList().push_back(exitBB);
    Builder.SetInsertPoint(exitBB);
  
    return nullptr;
}

3. BrainFuck 编译器完整实现 ​

3.1 构建命令（CMake） ​

cmake
# CMakeLists.txt
cmake_minimum_required(VERSION 3.10)
project(bfc)

find_package(LLVM REQUIRED CONFIG)
add_definitions(${LLVM_DEFINITIONS})
include_directories(${LLVM_INCLUDE_DIRS})

add_executable(bfc
    src/lexer.cpp
    src/parser.cpp
    src/codegen.cpp
    src/main.cpp
    runtime/runtime.c)

target_link_libraries(bfc
    LLVMSupport
    LLVMCore
    LLVMIRReader)

3.2 运行时库实现 ​

c
// runtime/runtime.c
#include <stdio.h>

char bf_memory[30000] = {0};
char *ptr = bf_memory + 15000;

void bf_putchar(char c) { putchar(c); }
char bf_getchar() { return getchar(); }

3.3 编译与使用 ​

bash
# 生成可执行文件
$ mkdir build && cd build
$ cmake .. -DLLVM_DIR=/path/to/llvm/cmake
$ make

# 编译 BrainFuck 程序
$ ./bfc hello.bf -o hello
$ ./hello

4. 测试案例：Hello World ​

输入文件 hello.bf：

text
++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.

编译执行后应输出：

text
Hello World!

5. 关键优化技术 ​

  1. 指令折叠：合并连续的同类型操作

    cpp
    // 优化前：+++++
Builder.CreateStore(
    Builder.CreateAdd(
        Builder.CreateLoad(ptr), 
        Builder.getInt8(1)));
// 重复 5 次

// 优化后：
Builder.CreateStore(
    Builder.CreateAdd(
        Builder.CreateLoad(ptr),
        Builder.getInt8(5)));

  2. 循环优化：使用 LLVM 内置优化 pass

    cpp
    llvm::PassManager pm;
pm.add(llvm::createLoopSimplifyPass());
pm.add(llvm::createLICMPass());
pm.run(*Module);

本实现完整支持 BrainFuck 语言规范，生成的 IR 可进一步通过 opt 工具进行优化，最终生成高效的可执行文件。