最近用 Python 实现了一个BrainFuck 解释器，简单介绍一下过程。
BrainFuck 介绍
BrainFuck是一门非常简单的图灵完备的编程语言，只有 8 个指令： Brainfuck 包含一个有 30,000 个单元为 0 的数组，和一个数据指针指向当前的单元。
- : 指针指向的单元的值加 1
- - : 指针指向的单元的值减 1
- > : 将指针移动到下一个单元(右边的元素)
- < : 将指针移动到上一个单元(左边的元素)
- . : 打印当前单元的内容的 ASCII 值 (比如 65 = ‘A’).
- , : 读取一个字符到当前的单元
- [ : 如果当前单元的值是 0，则向后调转到对应的]处
- ] : 如果当前单元的值不是 0，则向前跳转到对应的[处
使用 BrainFuck 编写程序十分繁琐，以下是一个输出字符“A”的程序：
代码语言：javascript复制 [ > < - ] > .以下是来自New Bing对这段程序的解读：
[ > < - ]：这是一个循环，每次循环都会将数据指针右移一位，将新单元的值增加 10，然后左移一位，将原单元的值减 1，直到原单元的值变为 0。这样，循环结束后，数据指针右边的单元的值变为 60（6 乘以 10）。>：将数据指针右移一位，指向刚才修改过的单元。.：输出该单元的值对应的 ASCII 字符，即大写字母 A。
实现 BrainFuck 解释器
我们使用测试驱动设计的方法来实现 Brainfuck 解释器，首先需要约定一下 Brainfuck 解释器的接口：
约定接口
代码语言：javascript复制def execute(code: str, input: TextIO = sys.stdin, output: TextIO = sys.stdout):
pass定义一个execute函数，接受三个参数：
code：Brainfuck 代码input:：输入流，默认为sys.stdinoutput：输出流，默认为sys.stdout
编写测试用例
接下来定义测试用例，我们分别测试 Brainfuck 语言的 8 个指令是否工作正常，然后测试一下上述输出字符“A”的代码，我们这里直接使用了 Python 内置的 unittest 模块来编写测试用例：
代码语言：javascript复制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 类来维护解释器的状态：
代码语言：javascript复制@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 类来保存每一个指令：
代码语言：javascript复制@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 方法的逻辑。
- 从第一条指令开始执行，执行完毕后返回下一条指令的索引。
- 如果下一条指令的索引小于指令总数，则继续执行下一条指令，否则停止执行。
对于其他六个非循环指令来说，执行完指令后直接将指令索引向后移一位即可。对于“[”与“]”，需要根据情况返回不同的指令索引。
下面是八种指令的定义与执行逻辑。
代码语言：javascript复制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 方法，将源代码解析成指令序列。
首先可以将源代码中的每一个字符都映射到对应的指令类：
代码语言：javascript复制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 类来执行代码：
代码语言：javascript复制def execute(code: str, input: TextIO = sys.stdin, output: TextIO = sys.stdout):
vm = VirtualMachine(input=input, output=output)
vm.compile(code)
vm.run()运行测试，可以看到所有的测试用例都通过了。
代码语言：javascript复制@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 编译器将其编译成机器码，从而得到极致的执行效率。
总结
这个 Brainfuck 语言的解释器总体上比较简单，但还是反映了使用虚拟机的方式来实现解释器的主要流程。对于更复杂的语言，源代码解析的过程会更加复杂，多半要使用词法分析器和语法分析器，并将源码转化为一棵 AST 抽象语法树；并且需要支持更多的指令。
