Brainfuck 解释器

本章导读

解释器（Interpreter）是"读取程序并执行"的程序。与编译器不同，解释器不生成目标代码，而是逐条读取指令、查表分发、执行操作。Brainfuck 的 8 条指令让这个过程极其直观——没有类型系统、没有变量名、没有函数调用，只有指针移动、字节加减和循环跳转。

50.1 Brainfuck 语言规范

Brainfuck 只有 8 条有效指令，其他字符全部忽略（视为注释）：

一个 Hello World 程序：

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

看起来像乱码？没关系——这正是 Brainfuck 的设计目的：用最少量的语义构建图灵完备计算。

50.2 磁带模型

Brainfuck 的"内存"是一条无限长的字节磁带，初始全为 0：

// 磁带：30000 字节（标准实现）
array<int> tape = array<int>(30000)   // 初始化为 0
int ptr = 0                             // 数据指针，指向当前格

// 程序存储为字符串
string program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>->+.>>.<-.++++++++++.>>.+++.------.--------.>>+.>++."
int pc = 0                              // 程序计数器（指令指针）

三个核心状态：

• tape：数据磁带，30000 个字节格
• ptr：数据指针，指向当前操作的格子
• pc：程序计数器，指向当前执行的指令

50.3 解释器主循环

解释器的核心是一个 while 循环 + 指令分发：

func interpret(string code, string input) as string
    array<int> tape = array<int>(30000)
    int ptr = 0
    int pc = 0
    int inputPos = 0
    string output = ""

    while pc < code.len()
        int ch = code[pc]

        if ch == 62 then            // '>'
            ptr += 1
        elif ch == 60 then          // '<'
            ptr -= 1
        elif ch == 43 then          // '+'
            tape[ptr] = (tape[ptr] + 1) % 256
        elif ch == 45 then          // '-'
            tape[ptr] = (tape[ptr] + 255) % 256
        elif ch == 46 then          // '.'
            output += string.char(tape[ptr])
        elif ch == 44 then          // ','
            if inputPos < input.len() then
                tape[ptr] = input[inputPos]
                inputPos += 1
            else
                tape[ptr] = 0       // EOF → 0
            end
        elif ch == 91 then          // '['
            if tape[ptr] == 0 then
                // 跳到匹配的 ] 之后
                int depth = 1
                while depth > 0
                    pc += 1
                    if code[pc] == 91 then depth += 1 end
                    if code[pc] == 93 then depth -= 1 end
                end
            end
        elif ch == 93 then          // ']'
            if tape[ptr] != 0 then
                // 跳回匹配的 [
                int depth = 1
                while depth > 0
                    pc -= 1
                    if code[pc] == 93 then depth += 1 end
                    if code[pc] == 91 then depth -= 1 end
                end
            end
        end
        // 其他字符忽略（注释）

        pc += 1
    end

    return output
end

注意 ASCII 码：'>' = 62，'<' = 60，'+' = 43，'-' = 45，'.' = 46，',' = 44，'[' = 91，']' = 93。xlang 的字符串索引返回字符的 ASCII 值。

50.4 括号匹配与跳转表

基础版每次遇到 [ 或 ] 都要线性扫描找匹配括号——O(n) 复杂度。优化：预计算跳转表：

// 预编译：构建跳转表
func buildJumpTable(string code) as array<int>
    array<int> jumps = array<int>(code.len())
    array<int> stack = array<int>(256)   // 括号栈
    int sp = 0

    int i = 0
    while i < code.len()
        if code[i] == 91 then        // '['
            stack[sp] = i
            sp += 1
        elif code[i] == 93 then      // ']'
            sp -= 1
            int open = stack[sp]
            jumps[open] = i          // [ → 匹配的 ]
            jumps[i] = open          // ] → 匹配的 [
        end
        i += 1
    end

    return jumps
end

有了跳转表，循环跳转变成 O(1) 数组查找：

// 优化后的 [ 和 ] 处理
elif ch == 91 then          // '['
    if tape[ptr] == 0 then
        pc = jumps[pc]      // O(1) 跳到匹配的 ]
    end
elif ch == 93 then          // ']'
    if tape[ptr] != 0 then
        pc = jumps[pc]      // O(1) 跳回匹配的 [
    end
end

对于深层嵌套循环（如 Sierpinski 三角形），这个优化可以将性能提升 10-100 倍。

50.5 完整解释器

组合所有部分，加上错误检查：

// bf.xl — Brainfuck 解释器（带跳转表优化）

func checkBrackets(string code) as bool
    int depth = 0
    int i = 0
    while i < code.len()
        if code[i] == 91 then depth += 1 end
        if code[i] == 93 then depth -= 1 end
        if depth < 0 then
            println("错误：多余的 ] 在位置 " + i.toString())
            return false
        end
        i += 1
    end
    if depth != 0 then
        println("错误：未闭合的 [，缺少 " + depth.toString() + " 个 ]")
        return false
    end
    return true
end

func buildJumpTable(string code) as array<int>
    array<int> jumps = array<int>(code.len())
    array<int> stack = array<int>(1024)
    int sp = 0
    int i = 0
    while i < code.len()
        if code[i] == 91 then
            stack[sp] = i
            sp += 1
        elif code[i] == 93 then
            sp -= 1
            jumps[stack[sp]] = i
            jumps[i] = stack[sp]
        end
        i += 1
    end
    return jumps
end

func run(string code, string input) as string
    if not checkBrackets(code) then return "" end

    array<int> jumps = buildJumpTable(code)
    array<int> tape = array<int>(30000)
    int ptr = 0
    int pc = 0
    int inputPos = 0
    string output = ""

    while pc < code.len()
        int ch = code[pc]
        if ch == 62 then ptr += 1
        elif ch == 60 then ptr -= 1
        elif ch == 43 then tape[ptr] = (tape[ptr] + 1) % 256
        elif ch == 45 then tape[ptr] = (tape[ptr] + 255) % 256
        elif ch == 46 then output += string.char(tape[ptr])
        elif ch == 44 then
            if inputPos < input.len() then
                tape[ptr] = input[inputPos]
                inputPos += 1
            else
                tape[ptr] = 0
            end
        elif ch == 91 then
            if tape[ptr] == 0 then pc = jumps[pc] end
        elif ch == 93 then
            if tape[ptr] != 0 then pc = jumps[pc] end
        end
        pc += 1
    end
    return output
end

// 测试
string hello = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>->+.>>.<-.++++++++++.>>.+++.------.--------.>>+.>++."
println(run(hello, ""))   // Hello World!

50.6 输入输出处理

Brainfuck 的 I/O 模型：

• 输出（.）：将当前格的值作为 ASCII 码输出一个字符
• 输入（,）：读取一个字节到当前格；EOF 时写入 0（标准行为之一）

// 输出：tape[ptr] → ASCII 字符
elif ch == 46 then
    output += string.char(tape[ptr])

// 输入：从预定义的 input 字符串读取
elif ch == 44 then
    if inputPos < input.len() then
        tape[ptr] = input[inputPos]
        inputPos += 1
    else
        tape[ptr] = 0   // EOF 处理
    end

50.7 测试：Hello World

// 经典 Hello World
string hello = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>->+.>>.<-.++++++++++.>>.+++.------.--------.>>+.>++."
string result = run(hello, "")
assert result == "Hello World!\n", "Hello World failed"
println("✓ Hello World: " + result)

// 执行过程解析（前几个字符）：
// ++++++++ → tape[0] = 8
// [        → 开始循环（tape[0] != 0）
// >++++    → tape[1] += 4
// [>++>+++>+++>+<<<<-] → 内层循环：tape[1] 次，给 tape[2-5] 累加
// ...
// 最终 tape[1]='H'(72), tape[2]='e'(101), tape[3]='l'(108)...

50.8 测试：Cat 程序

Cat 程序：读入什么就输出什么（直到 EOF）：

// Cat：读一个字符，输出，循环直到 EOF(0)
string cat = ",[.,]"
string input = "Hello xlang!"
string result = run(cat, input)
assert result == "Hello xlang!", "Cat failed"
println("✓ Cat: " + result)

// 执行过程：
// , → 读入 'H'(72) 到 tape[0]
// [ → tape[0] != 0，进入循环
// . → 输出 'H'
// , → 读入 'e'(101)
// ] → tape[0] != 0，跳回 [
// ... 重复直到读入 EOF(0)
// ] → tape[0] == 0，退出循环

50.9 调试与错误处理

添加调试模式和错误检测：

// 带调试输出的解释器
func runDebug(string code, string input, bool verbose) as string
    // ... 同 run() ...
    // 在每条指令后打印状态：
    if verbose then
        println("pc=" + pc.toString() +
            " ch=" + string.char(ch) +
            " ptr=" + ptr.toString() +
            " tape[ptr]=" + tape[ptr].toString())
    end
end

// 常见错误检测
func validate(string code) as bool
    // 1. 括号匹配
    if not checkBrackets(code) then return false end

    // 2. 指针越界检查（静态分析困难，运行时检测）
    // 在 run() 中加入：
    // if ptr < 0 or ptr >= 30000 then
    //     println("运行时错误：指针越界 pc=" + pc.toString())
    //     return ""
    // end

    return true
end

50.10 扩展方向

• 编译器：将 Brainfuck 编译为 C 代码（每条指令映射为 C 语句），用 TCC 即时编译执行
• 优化器：合并连续的 +/-/>/<（如 +++ → tape[ptr]+=3），消除 [] 空循环
• 调试器：单步执行、断点、磁带可视化
• Brainfuck 变体：Befunge（二维）、Ook!（用 "Ook." 代替符号）、Brainfuck-16（16 位格）
• 自解释器：用 Brainfuck 写一个 Brainfuck 解释器（约 4000 字符）

深入细节

⚠️ 常见错误

本章小结

复习题

1. Brainfuck 的 8 条指令分别对应什么操作？哪些是 I/O 指令？
2. [ 和 ] 的跳转条件分别是什么？它们组合实现了什么控制结构？
3. 跳转表相比线性扫描的优势是什么？预计算的时间复杂度是多少？
4. 为什么 tape[ptr] = (tape[ptr] + 255) % 256 等价于减 1？
5. EOF 时 , 指令写入 0 和写入 255 会导致什么不同的程序行为？
6. 如何检测 Brainfuck 程序的括号是否匹配？
7. 为什么说 Brainfuck 是图灵完备的？它等价于什么计算模型？
8. 如果要实现 Brainfuck 调试器，需要保存哪些状态？

编程练习