用 Rust 从零实现一个 Brainfuck 解释器


写一个 Brainfuck 解释器,是我用来理解虚拟机的一次练习。它只有八条指令、一条数据带和一个指针,代码量不大,适合把取指、译码、执行的循环完整地写一遍。

八条指令与括号匹配

八条指令里,前六条都是简单的指针和数值操作,[ 和 ] 需要多考虑一层。第一版我准备在运行时向后扫描、寻找配对的括号,写到一半发现嵌套循环会反复扫描同一段代码,复杂度不理想。后来改成加载时用栈扫描一次,把配对的下标双向存进哈希表:

'[' => stack.push(index),
']' => {
    if let Some(start) = stack.pop() {
        brackets.insert(start, index);
        brackets.insert(index, start);
    }
}

指令指针的跳转语义

主循环里,我一开始把跳转目标写成了配对括号的下一条指令,结果 Hello World 的输出多了一个字符。原因是循环末尾统一执行 instruction_ptr += 1,所以 [ 应该跳到配对的 ] 本身,] 应该跳回配对的 [,再靠这一次自增落到正确位置。这个问题不大,但让我把指令指针的语义重新理了一遍。

一个调试用的非标准指令

调试嵌套循环时,屏幕上只有错误的输出,看不到数据带的状态。我加了一个非标准指令 &,执行时打印当前指针位置和整条数据带。它不属于语言本身,但对定位指针偏移很直接。

数据带与输入输出

数据带初始有 32 个 i64 单元格,指针右移越界时执行 push(0),因此只会向右增长。输入用 read_exact 每次读一个字节,输出用 char::from_u32 加 print!。

与标准不一致的地方

输出这一处后来出了问题。运行一个会产生负值的程序时,解释器 panic 了:-1 as u32 得到 4294967295,from_u32 返回 None,随后的 expect 终止了进程。标准里 . 的语义是写一个字节,而我实现的是输出一个 Unicode 字符。两者在 ASCII 范围内看不出区别,超出以后就不一样了。

单元格类型也有类似的情况。我选了 i64,考虑的是避免溢出;标准 Brainfuck 的单元格通常是 8 位无符号数,255 加一会回绕成 0。有些程序依赖这种回绕,用 i64 反而对不上。

数据指针左移时同样有边界问题。在 0 号格执行 <,debug 模式下 usize 会因减法下溢 panic,release 模式会回绕成 usize::MAX,下一次访问仍然崩溃。我没有加检查,因为当时只把它当作学习项目,但这个行为后来一直记得。

括号不匹配没有在加载阶段校验。孤立的 ] 会被静默忽略,未闭合的 [ 要到运行时查表才以 “key not found” 失败,错误信息里也没有源码位置。

整体结构

整个解释器不到 150 行,没有第三方依赖。它不算严格符合标准,但包含了虚拟机的基本结构:指令指针、数据指针、内存、跳转表和 I/O。写完这个版本之后,再看栈式虚拟机和字节码解释器,结构就清楚了很多。


文章作者: NekokeCore
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 NekokeCore !
 上一篇
用 TypeScript 在 GitHub 贡献图上“作画”:Time Assassin 用 TypeScript 在 GitHub 贡献图上“作画”:Time Assassin
GitHub 贡献图是一张按周排列的日期网格,每列 7 天,一年大约 53 列。我写 time_assassin 的出发点很简单:既然每个格子对应一天,能不能先选好日期,再让 Git 在这些日期产生提交。 两个时间戳Git 的每个提交有
2023-04-09
下一篇 
密码破解与心理学 密码破解与心理学
仅供学习与交流,切勿对真实目标操作,否则后果自负! 十大基本规律 绝大多数人都高估了破译密码的难度和低估了自己密码存在的风险,因而,往往把能够破解密码的人当成神秘人物,同时基本很少有修改自己密码的习惯。 绝大多数人一生常用的密码通常不会
2021-11-25 NekokeCore
  目录