实现一个 BrainFuck 解释器

杜逸先

发布于 2023-04-13 16:36:23

5460

发布于 2023-04-13 16:36:23

文章被收录于专栏：追不上乌龟的兔子追不上乌龟的兔子

最近用 Python 实现了一个BrainFuck 解释器，简单介绍一下过程。

BrainFuck 介绍

BrainFuck是一门非常简单的图灵完备的编程语言，只有 8 个指令： Brainfuck 包含一个有 30,000 个单元为 0 的数组，和一个数据指针指向当前的单元。

+ : 指针指向的单元的值加 1
- : 指针指向的单元的值减 1
> : 将指针移动到下一个单元(右边的元素)
< : 将指针移动到上一个单元(左边的元素)
. : 打印当前单元的内容的 ASCII 值 (比如 65 = ‘A’).
, : 读取一个字符到当前的单元
[ : 如果当前单元的值是 0，则向后调转到对应的]处
] : 如果当前单元的值不是 0，则向前跳转到对应的[处

使用 BrainFuck 编写程序十分繁琐，以下是一个输出字符“A”的程序：

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

以下是来自New Bing对这段程序的解读：

++++++：将数据指针指向的单元的值增加 6，变为 6。
[ > ++++++++++ < - ]：这是一个循环，每次循环都会将数据指针右移一位，将新单元的值增加 10，然后左移一位，将原单元的值减 1，直到原单元的值变为 0。这样，循环结束后，数据指针右边的单元的值变为 60（6 乘以 10）。
>：将数据指针右移一位，指向刚才修改过的单元。
+++++：将该单元的值增加 5，变为 65。
.：输出该单元的值对应的 ASCII 字符，即大写字母 A。

实现 BrainFuck 解释器

我们使用测试驱动设计的方法来实现 Brainfuck 解释器，首先需要约定一下 Brainfuck 解释器的接口：

约定接口

def execute(code: str, input: TextIO = sys.stdin, output: TextIO = sys.stdout):
    pass

定义一个execute函数，接受三个参数：

code：Brainfuck 代码
input:：输入流，默认为sys.stdin
output：输出流，默认为sys.stdout

编写测试用例

接下来定义测试用例，我们分别测试 Brainfuck 语言的 8 个指令是否工作正常，然后测试一下上述输出字符“A”的代码，我们这里直接使用了 Python 内置的 unittest 模块来编写测试用例：

from io import StringIO
from unittest import TestCase, main

from brainfuck import execute


class TestExecute(TestCase):
    def test_output(self):
        buffer = StringIO()
        execute(".", output=buffer)
        self.assertEqual(buffer.getvalue(), chr(0))

    def test_input(self):
        input = StringIO("A")
        output = StringIO()
        execute(",.", input=input, output=output)
        self.assertEqual(input.getvalue(), "A")

    def test_move_right(self):
        buffer = StringIO()
        execute(">.", output=buffer)
        self.assertEqual(buffer.getvalue(), chr(0))

    def test_move_left(self):
        buffer = StringIO()
        execute("+><.", output=buffer)
        self.assertEqual(buffer.getvalue(), chr(1))

    def test_increment(self):
        buffer = StringIO()
        execute("+.", output=buffer)
        self.assertEqual(buffer.getvalue(), chr(1))

    def test_decrement(self):
        buffer = StringIO()
        execute("+-.", output=buffer)
        self.assertEqual(buffer.getvalue(), chr(0))

    def test_loop(self):
        buffer = StringIO()
        execute("++[>+<-]>.", output=buffer)
        self.assertEqual(buffer.getvalue(), chr(2))

    def test_full(self):
        buffer = StringIO()
        execute("++++++ [ > ++++++++++ < - ] > +++++ .", output=buffer)
        self.assertEqual(buffer.getvalue(), "A")


if __name__ == "__main__":
    main()

设计与实现

Brainfuck 程序执行过程中需要不断移动指针，并修改指针指向的单元的值，因此我们需要两个变量来维护指针和数据单元的状态。方便起见，我们直接定义一个 VirtualMachine 类来维护解释器的状态：

@dataclass
class VirtualMachine:
    memory: bytearray = field(
        default_factory=lambda: bytearray(MEMORY_SIZE), repr=False
    )
    pointer: int = 0
    input: TextIO = field(default=sys.stdin, repr=False)
    output: TextIO = field(default=sys.stdout, repr=False)

值得注意的是我们使用 bytearray 来保存数据单元的值，对于纯数值的处理，使用 bytearray 会比 list 更加高效。

接下来需要考虑的是如何解析与处理指令。在不考虑“[”与“]”两个控制循环的指令的情况下，只需要根据指令的类型来执行对应的操作（移动指针，修改数据单元或者处理 IO）即可。但是在处理循环指令时，我们要根据情况进行指令跳转，包括从“[”跳转到“]”跳出循环，或者从“]”跳转到“[”重新执行循环体。

为了处理循环指令，将每一个指令保存起来是有必要的，不然就需要在解析源代码的时候进行指令跳转，使得解析过程变得复杂。

其实完全可以参考常见的编程语言的解释器的实现，将源代码解析成中间代码，然后再解释执行中间代码，这样就可以将解析与执行分离开来，使得解析过程变得简单，而且也可以将解析过程与执行过程分别进行优化，比如 Python 字节码。

我们可以设计一个 Instruction 类来保存每一个指令：

@dataclass
class Instruction:
    vm: "VirtualMachine" = field(repr=False)
    index: int

    def _execute(self):
        pass

    def execute(self) -> int:
        self._execute()
        return self.index + 1

然后在 VirtualMachine 类中定义一个instructions属性，用来保存所有的指令：

@dataclass
class VirtualMachine:
    memory: bytearray = field(
        default_factory=lambda: bytearray(MEMORY_SIZE), repr=False
    )
    instructions: list[Instruction] = field(default_factory=list)
    pointer: int = 0
    input: TextIO = field(default=sys.stdin, repr=False)
    output: TextIO = field(default=sys.stdout, repr=False)

    def compile(self, code: str):
        pass

     def run(self):
        index = 0
        cnt = len(self.instructions)
        while (index := self.instructions[index].execute()) < cnt:
            pass

我们先略过 compile 方法的实现，看一下 run 方法的逻辑。

从第一条指令开始执行，执行完毕后返回下一条指令的索引。
如果下一条指令的索引小于指令总数，则继续执行下一条指令，否则停止执行。

对于其他六个非循环指令来说，执行完指令后直接将指令索引向后移一位即可。对于“[”与“]”，需要根据情况返回不同的指令索引。

下面是八种指令的定义与执行逻辑。

class Increment(Instruction):
    def _execute(self):
        self.vm.memory[self.vm.pointer] += 1


class Decrement(Instruction):
    def _execute(self):
        self.vm.memory[self.vm.pointer] -= 1


class MoveRight(Instruction):
    def _execute(self):
        self.vm.pointer = (self.vm.pointer + 1) % MEMORY_SIZE


class MoveLeft(Instruction):
    def _execute(self):
        self.vm.pointer = (self.vm.pointer - 1) % MEMORY_SIZE


class Read(Instruction):
    def _execute(self):
        self.vm.memory[self.vm.pointer] = ord(self.vm.input.read(1))


class Write(Instruction):
    def _execute(self):
        self.vm.output.write(chr(self.vm.memory[self.vm.pointer]))


@dataclass
class LoopEnd(Instruction):
    jump_to: int

    def _execute(self):
        if self.vm.memory[self.vm.pointer] == 0:
            return self.index + 1
        return self.jump_to

    def execute(self) -> int:
        return self._execute()


@dataclass
class LoopStart(Instruction):
    jump_to: int | None

    def _execute(self):
        if self.vm.memory[self.vm.pointer] != 0:
            return self.index + 1
        return self.jump_to

    def execute(self) -> int:
        return self._execute()

可以看到将问题范围缩小到每一种指令的执行时，逻辑十分简单。

接下来我们来实现 compile 方法，将源代码解析成指令序列。

首先可以将源代码中的每一个字符都映射到对应的指令类：

INSTRUCTION_MAPPING: dict[str, Type[Instruction]] = {
    ">": MoveRight,
    "<": MoveLeft,
    "+": Increment,
    "-": Decrement,
    ".": Write,
    ",": Read,
    "[": LoopStart,
    "]": LoopEnd,
}

然后就是解析源代码，将每一个字符映射到对应的指令类，然后将指令类实例化，最后将指令实例添加到instructions中即可。

def compile(self, code: str):
    self.clear()
    index = 0
    left: int | None = None
    for ch in code:
        instruction = INSTRUCTION_MAPPING.get(ch)
        if instruction:
            match instruction.__qualname__:
                case "LoopStart":
                    left = index
                    self.instructions.append(LoopStart(self, index, None))
                case "LoopEnd":
                    assert left is not None, "Unmatched ]"
                    setattr(self.instructions[left], "jump_to", index)
                    self.instructions.append(LoopEnd(self, index, jump_to=left))
                    left = None
                case _:
                    self.instructions.append(instruction(self, index))
            index += bool(instruction)
    assert left == None, "Unmatched ["

这段代码的逻辑整体比较清晰：

遇到非指令字符直接忽略。
遇到非循环的六种指令，直接实例化对应的指令对象，然后将指令对象添加到instructions中。
遇到“[”时，创建一个 LoopLeft 对象，jump_to 初始化为 None，将当前指令索引保存到left变量中，然后将 LoopLeft 对象添加到instructions中。
遇到“]”时，创建一个 LoopEnd 对象，将当前的 left 值保存到jump_to属性中，然后将 LoopEnd 对象添加到instructions中。如果 left 为 None,说明程序有误，这个“]”指令没有对应的“[”指令。然后根据 left 找到这段循环的起始位置，将起始位置的 LoopLeft 对象的 jump_to 属性设置为当前指令索引，然后将 left 变量设置为 None。
最后遍历完所有字符后，检查left变量是否为 None，如果不为 None，则说明存在未匹配的“[”。

定义好所有的指令，并实现 compile 和 run 方法后，我们可以修改 execute 函数，使用新的 VirtualMachine 类来执行代码：

def execute(code: str, input: TextIO = sys.stdin, output: TextIO = sys.stdout):
    vm = VirtualMachine(input=input, output=output)
    vm.compile(code)
    vm.run()

运行测试，可以看到所有的测试用例都通过了。

@duyixian1234 ➜ /workspaces/bf-py (main) $ python -m test -v
test_decrement (__main__.TestExecute) ... ok
test_full (__main__.TestExecute) ... ok
test_increment (__main__.TestExecute) ... ok
test_input (__main__.TestExecute) ... ok
test_loop (__main__.TestExecute) ... ok
test_move_left (__main__.TestExecute) ... ok
test_move_right (__main__.TestExecute) ... ok
test_output (__main__.TestExecute) ... ok

----------------------------------------------------------------------
Ran 8 tests in 0.003s

OK

我还为 VirtualMachine 添加了一个 reset 方法，用于重置内存和指针。具体的实现可以看源代码仓库。

可能的改进

这个 Brainfuck 解释器的实现已经比较完善了，不过受限于 Python，整体的执行效率不会特别高。我们已经起了一个好头，将 Brainfuck 源代码编译成了指令序列，或者说是字节码。我们可以将这个字节码保存到文件中，然后用更高效的编程语言（C，Rust）实现字节码解释器，来执行这段字节码，效率可以显著提升。

更极端一点的话，我们可以直接将字节码转化为 LLVM IR，然后使用 LLVM 编译器将其编译成机器码，从而得到极致的执行效率。