Back

用 Python 写一个 Brainfuck 解释器(一) - It works!

Brainfuck ,是一种极小化的计算机语言,它是由 Urban Müller 在 1993 年创建的。由于 fuck 在英语中是脏话,这种语言有时被称为 brainfck 或 brainf** ,甚至被简称为 BF 。

—— Wikipedia

Brainfuck 语言基于一个简单的机器模型 —— 8 种指令,一个被初始化为 0 的数组,一个指向数组中元素的指针(初始时指向数组的第一个字节),和用于输入输出的两个字节流。虽然 Brainfuck 如此简单,但它仍然是 图灵完备 的。

当一个 Brainfuck 程序执行时,执行环境会依照指令序列数组进行操作。

Brainfuck 语言的每种指令均用一个字符表示,各指令的含义如下:

字符含义等价的 C 语言表示
>指针向前移动一个字节++ptr;
<指针向后移动一个字节--ptr;
+指针指向的字节的值加一++(*ptr);
-指针指向的字节的值减一--(*ptr);
.输出指针指向的单元内容(ASCII 字符)putchar(*ptr);
,输入内容到指针指向的单元(ASCII 字符)*ptr = getchar();
[如果指针指向的单元值为零,向后跳转到对应的 ] 指令的下一指令处while (*ptr) {
]如果指针指向的单元值不为零,向前跳转到对应的 [ 指令的下一指令处}

Brainfuck 语言的语法和执行模型都十分简单,但又可以在 Brainfuck 程序上执行多种现代编译器中常见的优化。因此,写一个 Brainfuck 编译器 / 解释器是入门编译原理的一个很好的例子。

解释器

作为本系列的第一篇文章,这里将尝试用最简单的方式实现一个解释器。

(以下所有 Python 代码均应在 Python 3 下运行)

读入代码:

with open(sys.argv[1], 'rb') as code_file:
    code = code_file.read().decode("utf8")

把 Brainfuck 的机器模型表示出来:

MEM_SIZE = 1048576 # 数组内存大小,这里设定为 1 MB
mem = bytearray([0 for i in range(MEM_SIZE)]) # 创建大小为 MEM_SIZE 的字节数组
mem_ptr = 0 # 指向数组中当前位置的指针
code_ptr = 0 # 指向当前指令的指针

解释执行:

while code_ptr < len(code):
    op = code[code_ptr]

    if op == '>':
        mem_ptr += 1
    elif op == '<':
        mem_ptr -= 1
    elif op == '+':
        new_value = int(mem[mem_ptr]) + 1
        mem[mem_ptr] = new_value % 256 # 模拟 8 字节无符号整数溢出
    elif op == '-':
        new_value = int(mem[mem_ptr]) - 1
        mem[mem_ptr] = new_value % 256
    elif op == '.':
        sys.stdout.write(chr(mem[mem_ptr]))
        sys.stdout.flush()
    elif op == ',':
        mem[mem_ptr] = ord(sys.stdin.read(1))

    code_ptr += 1

到目前为止,我们实现了 Brainfuck 语言中除循环外的所有指令。循环指令的实现与之前的代码相比略显复杂。

首先,我们需要实现配对括号(循环开始标志 [ 和结束标志 ] )的查找:

# 存储配对括号的位置
bracket_pairs = [None for i in range(len(code))]

# 寻找配对括号 (Lazy)
def lookup_bracket():
    if bracket_pairs[code_ptr] != None:
        return bracket_pairs[code_ptr]

    if code[code_ptr] == '[':
        depth = 1
        pairing = code_ptr
        while depth != 0:
            pairing += 1
            if code[pairing] == '[':
                depth += 1
            elif code[pairing] == ']':
                depth -= 1
        if depth != 0:
            raise Exception("No pairing bracket found for bracket at position " + str(code_ptr))
        bracket_pairs[code_ptr] = pairing
        bracket_pairs[pairing] = code_ptr
        return pairing
    elif code[code_ptr] == ']':
        raise Exception("Found `]` without pairing `[`")
    else:
        assert(False)

然后就可以在解释执行循环里加上 [] 指令:

    # ...
    elif op == '[':
        pairing_location = lookup_bracket()
        if mem[mem_ptr] == 0:
            code_ptr = pairing_location
    elif op == ']':
        if mem[mem_ptr] != 0:
            code_ptr = lookup_bracket()

至此,我们的 Brainfuck 解释器就完成了。将解释器代码保存为 brainfuck.py ,在命令行下运行 python3 brainfuck.py your_code.bf 即可执行 Brainfuck 程序。

试试运行这个程序:

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

保存为 hello_world.bf ,执行 python3 brainfuck.py hello_world.bf 。这会在终端输出一行 Hello World!

在很多地方都可以找到有意思的 Brainfuck 程序,如 brainfuck-jit, brainfuck/examples

完整代码:

import sys

with open(sys.argv[1], 'rb') as code_file:
    code = code_file.read().decode("utf8")

MEM_SIZE = 1048576
mem = bytearray([0 for i in range(MEM_SIZE)])
mem_ptr = 0
code_ptr = 0
bracket_pairs = [None for i in range(len(code))]

def lookup_bracket():
    if bracket_pairs[code_ptr] != None:
        return bracket_pairs[code_ptr]

    if code[code_ptr] == '[':
        depth = 1
        pairing = code_ptr
        while depth != 0:
            pairing += 1
            if code[pairing] == '[':
                depth += 1
            elif code[pairing] == ']':
                depth -= 1
        if depth != 0:
            raise Exception("No pairing bracket found for bracket at position " + str(code_ptr))
        bracket_pairs[code_ptr] = pairing
        bracket_pairs[pairing] = code_ptr
        return pairing
    elif code[code_ptr] == ']':
        raise Exception("Found `]` without pairing `[`")
    else:
        assert(False)

while code_ptr < len(code):
    op = code[code_ptr]

    if op == '>':
        mem_ptr += 1
    elif op == '<':
        mem_ptr -= 1
    elif op == '+':
        new_value = int(mem[mem_ptr]) + 1
        mem[mem_ptr] = new_value % 256
    elif op == '-':
        new_value = int(mem[mem_ptr]) - 1
        mem[mem_ptr] = new_value % 256
    elif op == '.':
        sys.stdout.write(chr(mem[mem_ptr]))
        sys.stdout.flush()
    elif op == ',':
        mem[mem_ptr] = ord(sys.stdin.read(1))
    elif op == '[':
        pairing_location = lookup_bracket()
        if mem[mem_ptr] == 0:
            code_ptr = pairing_location
    elif op == ']':
        if mem[mem_ptr] != 0:
            code_ptr = lookup_bracket()

    code_ptr += 1
Submit