使用Rust实现一个Brainfuck解释器 _使用

一箫一剑平生意，负尽狂名十五年。这篇文章主要讲述使用Rust实现一个Brainfuck解释器相关的知识，希望能为你提供帮助。
[TOC]
brainfuck语法解析由于 fuck 在英语中是脏话，Brainfuck 有时被称为 Brainfsck，甚至被简称为 BF。它是大多数学生们学习编译器理论知识的好朋友，这一切都是因为它 fuck simple。我们对 JIT 编译器的第一次尝试是如此的简单，甚至有点可笑。不过你想笑就笑吧，很快就会轮到编译器嘲笑你了，你会被告知自己写的解释器有多么的慢。
Brainfuck 是一种简单且最小的图灵完备编程语言。这种语言由八种运算符构成：

字符	含义
>	指针加一
<	指针减一
+	指针指向的字节的值加一
-	指针指向的字节的值减一
。	输出指针指向的单元内容（ASCII码）
,	输入内容到指针指向的单元（ASCII码）
[	如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处
]	如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处

它几乎完全模仿自图灵纸带机，后者则是计算机的理论基础。理论上一切能被计算的问题都能通过 Brainfuck 被计算。
Brainfuck 可以通过解释器实现，也能通过编译器实现。当然本章将先实现一个解释器。我会使用 Rust 来编写这个解释器并省略了一部分无关紧要的代码，以使得核心逻辑清晰。
brainfuck opcode 定义定义一个枚举类型 Opcode 来代表以上的八种运算符，用ASCII码表示，然后编写一个转换函数将字节转换为 Opcode。由于 [ 与 ] 总是成双成对的出现且互相关联，代码内使用了 jtable 来存储它们之间的位置关系，以便快速决定跳转的目的地址。当然这不是必须的，也可以在解释 [ 和 ] 的时候实时的前向搜索或后向搜索以找到对应的符号位置。
代码示例：

pub enum Opcode SHR = 0x3E, SHL = 0x3C, ADD = 0x2B, SUB = 0x2D, PUTCHAR = 0x2E, GETCHAR = 0x2C, LB = 0x5B, RB = 0x5D,impl From< u8> for Opcode fn from(u: u8) -> Self match u 0x3E => Opcode::SHR, 0x3C => Opcode::SHL, 0x2B => Opcode::ADD, 0x2D => Opcode::SUB, 0x2E => Opcode::PUTCHAR, 0x2C => Opcode::GETCHAR, 0x5B => Opcode::LB, 0x5D => Opcode::RB, _ => unreachable!(),pub struct Code // 指令数组 pub instrs: Vec< Opcode> , // 存储 [ 和 ] 的位置关系 pub jtable: std::collections::HashMap< usize, usize> ,impl Code pub fn from(data: Vec< u8> ) -> Result< Self, Box< dyn std::error::Error> > let dict: Vec< u8> = vec![ Opcode::SHR as u8, Opcode::SHL as u8, Opcode::ADD as u8, Opcode::SUB as u8, Opcode::PUTCHAR as u8, Opcode::GETCHAR as u8, Opcode::LB as u8, Opcode::RB as u8, ]; let instrs: Vec< Opcode> = data.iter() .filter(|x| dict.contains(x)) .map(|x| Opcode::from(*x)) .collect(); // 借助栈结构来匹配 [ 和 ] 符号，然后存入 jtable 中 let mut jstack: Vec< usize> = Vec::new(); let mut jtable: std::collections::HashMap< usize, usize> = std::collections::HashMap::new(); for (i, e) in instrs.iter().enumerate() if Opcode::LB == *e jstack.push(i); if Opcode::RB == *e let j = jstack.pop().ok_or("pop from empty list")?; jtable.insert(j, i); jtable.insert(i, j); Ok(Codeinstrs, jtable )

brainfuck 解释器实现创建 res 目录，然后再该目录下创建 hello_world.bf 文件，其内容就是 Brainfuck 语法编写的 hello world：

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

参考：https://en.wikipedia.org/wiki/Brainfuck

然后我们 main 函数里编写一部分代码，这部分代码会从文件中读取字符，然后将它们转换为 Opcode 的数组：

mod opcode; use opcode::Opcode, Code; fn main() -> Result< (), Box< dyn std::error::Error> > // 获取命令行参数 let args: Vec< String> = std::env::args().collect(); // 第一个参数就是传递的文件路径，例如：brainfuck res/hello_world.bf let data = https://www.songbingjia.com/android/std::fs::read(& args[1])?; // 转换为 Opcode 的数组 let code = Code::from(data)?; println!(":?", code.instrs); Ok(())

经过 cargo build 得到程序的二进制文件后，执行以下命令，打印的内容如下：

PS W:\\WorkSpace\\Rust\\brainfuck> ./target/debug/brainfuck W:\\WorkSpace\\Rust\\brainfuck\\src\\res\\hello_world.bf [ADD, ADD, ADD, ADD, ADD, ADD, ADD, ADD, LB, SHR, ADD, ADD, ADD, ADD, LB, SHR, ADD, ADD, SHR, ADD, ADD, ADD, SHR, ADD, ADD, ADD, SHR, ADD, SHL, SHL, SHL, SHL, SUB, RB, SHR, ADD, SHR, ADD, SHR, SUB, SHR, SHR, ADD, LB, SHL, RB, SHL, SUB, RB, SHR, SHR, PUTCHAR, SHR, SUB, SUB, SUB, PUTCHAR, ADD, ADD, ADD, ADD , ADD, ADD, ADD, PUTCHAR, PUTCHAR, ADD, ADD, ADD, PUTCHAR, SHR, SHR, PUTCHAR, SHL, SUB, PUTCHAR, SHL, PUTCHAR, ADD, ADD, ADD, PUTCHAR, SUB, SUB, SUB, SUB , SUB, SUB, PUTCHAR, SUB, SUB, SUB, SUB, SUB, SUB, SUB, SUB, PUTCHAR, SHR, SHR, ADD, PUTCHAR, SHR, ADD, ADD, PUTCHAR]

在拿到 Opcode 数组之后，便可以编写针对 Opcode 解释器。Brainfuck 的解释执行需要首先定义一个无限长的纸带（字节数组），当前指针 SP，Opcode 源代码以及程序计数器 PC，然后通过一个主循环匹配不同的指令并解释执行。代码示例：

mod opcode; use std::io::Write; use std::io::Read; use opcode::Opcode, Code; struct Interpreter // 表示无限长的纸带 stack: Vec< u8> ,impl std::default::Default for Interpreter fn default() -> Self // 初始化，提供默认值 Selfstack: vec![0; 1] impl Interpreter fn run(& mut self, data: Vec< u8> ) -> Result< (), Box< dyn std::error::Error> > // 将源文件中的内容转换为 Opcode 数组 let code = Code::from(data)?; let code_len = code.instrs.len(); // Program counter，程序计数器 let mut pc: usize = 0; // Stack Pointer，栈指针，也就是表示在纸带的哪个位置 let mut sp: usize = 0; // 解释器的主循环 loop if pc > = code_len // 代码已经执行完了 break; // 匹配相应的指令并解释执行 match code.instrs[pc] Opcode::SHR => sp += 1; // 如果达到了纸带的长度就进行填充，延长纸带的长度 if sp == self.stack.len() self.stack.push(0)Opcode::SHL => sp = if sp == 00elsesp - 1 , Opcode::ADD => // 允许溢出 self.stack[sp] = self.stack[sp].overflowing_add(1).0; Opcode::SUB => self.stack[sp] = self.stack[sp].overflowing_sub(1).0; Opcode::PUTCHAR => // 将字符打印到标准输出 std::io::stdout().write_all(& [self.stack[sp]])?; Opcode::GETCHAR => let mut buf: Vec< u8> = vec![0; 1]; // 从标准输入读取字符 std::io::stdin().read_exact(& mut buf)?; // 将字符写到纸带上 self.stack[sp] = buf[0]; Opcode::LB => // 如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处 if self.stack[sp] == 0x00 pc = code.jtable[& pc]; Opcode::RB => // 如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处 if self.stack[sp] != 0x00 pc = code.jtable[& pc]; // 移动计数器，执行下一个指令 pc += 1; Ok(())fn main() -> Result< (), Box< dyn std::error::Error> > let args: Vec< String> = std::env::args().collect(); let data = https://www.songbingjia.com/android/std::fs::read(& args[1])?; let mut interpreter = Interpreter::default(); interpreter.run(data); Ok(())

编写完以上代码后，和之前一样，通过 cargo build 得到程序的二进制文件后，执行以下命令会输出 Hello World! ：

PS W:\\WorkSpace\\Rust\\brainfuck> ./target/debug/brainfuck W:\\WorkSpace\\Rust\\brainfuck\\src\\res\\hello_world.bf Hello World! PS W:\\WorkSpace\\Rust\\brainfuck>

测试经过了以上小节的学习，希望你能自己独立编写好完整的 Brainfuck 解释器！当你完成时，可以尝试运行以下程序，它能在屏幕上输出斐波那契数列。虽然不太清楚上古的程序员们是如何写出这份代码的，不过我也不在乎…毕竟代码和人有一个能跑就算成功，不是吗？

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

使用中间表示使用中间表示优化运行速度
目前为止，我们已经有了一个能正常跑的解释器，但我对上面的代码并不满意，如果你仔细观察，可以发现 Brainfuck 源代码中存在着大量冗余。将 Hello World 的代码以 Opcode 的形式打印出来：

[ ADD,ADD,ADD,ADD,ADD,ADD,ADD,ADD, ADD,ADD,LB,SHR,ADD,ADD,ADD,ADD, ADD,ADD,ADD,SHR,ADD,ADD,ADD,ADD, ADD,ADD,ADD,ADD,ADD,ADD,SHR,ADD, ADD,ADD,SHR,ADD,SHL,SHL,SHL,SHL, SUB,RB,SHR,ADD,ADD,PUTCHAR, SHR,ADD, PUTCHAR, ADD,ADD,ADD,ADD,ADD,ADD,ADD, PUTCHAR, PUTCHAR, ADD,ADD,ADD,PUTCHAR, SHR,ADD, ADD,PUTCHAR, SHL,SHL,ADD,ADD,ADD,ADD, ADD,ADD,ADD,ADD,ADD,ADD,ADD,ADD, ADD,ADD,ADD,PUTCHAR, SHR,PUTCHAR, ADD,ADD, ADD,PUTCHAR, SUB,SUB,SUB,SUB,SUB,SUB, PUTCHAR, SUB,SUB,SUB,SUB,SUB,SUB,SUB, SUB,PUTCHAR, SHR,ADD,PUTCHAR, SHR,PUTCHAR, ]

如果希望解释器执行的稍微快一点，可以对相邻的相同操作符进行折叠操作，我们已经知道一个 ADD 操作符执行的是加 1 操作，那么如果相邻着十个连续的 ADD，便可以 ADD(10) 来表示。为此定义如下的中间语言表示。
我们定义一个新的枚举类型，用于表示 brianfuck 中几种指令的中间表达形式：

#[derive(Debug)] pub enum IR SHR(u32), SHL(u32), ADD(u8), SUB(u8), PUTCHAR, GETCHAR, JIZ(u32), // Jump if zero, alias of "[" JNZ(u32), // Jump if not zero, alias of "]"

然后我们需要编写一个转换器，以便将原始代码翻译为中间代码。这很简单，代码如下：

use crate::opcode::Opcode; pub struct Code pub instrs: Vec< IR> ,impl Code pub fn from(data: Vec< Opcode> ) -> Result< Self, Box< dyn std::error::Error> > // 存储匹配到的指令，遇到相同且相邻指令时进行折叠 let mut instrs: Vec< IR> = Vec::new(); // 借助栈结构来匹配 [ 和 ] 符号 let mut jstack: Vec< u32> = Vec::new(); for e in data match e Opcode::SHR => // 如果最后一个元素是 IR::SHR 则将其计数值加一，也就是折叠起来，否则就添加新元素 match instrs.last_mut() Some(IR::SHR(x)) => *x += 1; _ => instrs.push(IR::SHR(1))Opcode::SHL => match instrs.last_mut() Some(IR::SHL(x)) => *x += 1; _ => instrs.push(IR::SHL(1))Opcode::ADD => match instrs.last_mut() Some(IR::ADD(x)) => // 允许溢出 let (b, _) = x.overflowing_add(1); *x = b; _ => instrs.push(IR::ADD(1))Opcode::SUB => match instrs.last_mut() Some(IR::SUB(x)) => // 允许溢出 let (b, _) = x.overflowing_add(1); *x = b; _ => instrs.push(IR::SUB(1))Opcode::PUTCHAR => instrs.push(IR::PUTCHAR)Opcode::GETCHAR => instrs.push(IR::GETCHAR)Opcode::LB => instrs.push(IR::JIZ(0)); // 将 IR::JIZ 符号所在的索引位置压入栈中 jstack.push((instrs.len() - 1) as u32)Opcode::RB => let j = jstack.pop().ok_or("pop from empty list")?; // IR::JNZ 所存储的值是对应 IR::JIZ 指令在 instrs 中的索引位置 instrs.push(IR::JNZ(j)); let instrs_len = instrs.len(); match & mut instrs[j as usize] IR::JIZ(x) => // 同样，IR::JIZ 所存储的值是对应 IR::JNZ 指令在 instrs 中的索引位置 *x = (instrs_len - 1) as u32_ => unreachable!()Ok(Codeinstrs )

经过中间语言优化后的 Hello World! 代码如下所示，它大概减少了 60% 左右的大小：

[ ADD(10),JIZ(12),SHR(1),ADD(7),SHR(1),ADD(10),SHR(1),ADD(3), SHR(1),ADD(1),SHL(4),SUB(1),JNZ(1),SHR(1),ADD(2),PUTCHAR, SHR(1),ADD(1),PUTCHAR, ADD(7),PUTCHAR, PUTCHAR,ADD(3),PUTCHAR, SHR(1),ADD(2),PUTCHAR, SHL(2),ADD(15), PUTCHAR,SHR(1),PUTCHAR, ADD(3),PUTCHAR,SUB(6),PUTCHAR, SUB(8),PUTCHAR,SHR(1),ADD(1), PUTCHAR,SHR(1),PUTCHAR ]

之后我们便可以针对此中间语言编写解释器，其实整体逻辑与之前并没什么太大差别。代码示例：

mod opcode; mod ir_code; use std::io::Write; use std::io::Read; use ir_code::IR; struct Interpreter // 表示无限长的纸带 stack: Vec< u8> ,impl std::default::Default for Interpreter fn default() -> Self // 初始化，提供默认值 Selfstack: vec![0; 1] impl Interpreter fn run(& mut self, data: Vec< u8> ) -> Result< (), Box< dyn std::error::Error> > // 将源文件中的内容转换为 Opcode 数组 let opcode_code = opcode::Code::from(data)?; // 将 opcode 转换为 ir code let code = ir_code::Code::from(opcode_code.instrs)?; let code_len = code.instrs.len(); // Program counter，程序计数器 let mut pc: usize = 0; // Stack Pointer，栈指针，也就是表示在纸带的哪个位置 let mut sp: usize = 0; // 解释器的主循环 loop if pc > = code_len // 代码已经执行完了 break; // 匹配相应的指令并解释执行 match code.instrs[pc] IR::SHR(x) => sp += x as usize; // 如果超过了纸带的长度就进行扩充 if sp > = self.stack.len() let expand = sp - self.stack.len() + 1; for _ in 0..expand self.stack.push(0); IR::SHL(x) => sp = if sp == 00elsesp - x as usize , IR::ADD(x) => // 允许溢出 self.stack[sp] = self.stack[sp].overflowing_add(x).0; IR::SUB(x) => self.stack[sp] = self.stack[sp].overflowing_sub(x).0; IR::PUTCHAR => // 将字符打印到标准输出 std::io::stdout().write_all(& [self.stack[sp]])?; IR::GETCHAR => let mut buf: Vec< u8> = vec![0; 1]; // 从标准输入读取字符 std::io::stdin().read_exact(& mut buf)?; // 将字符写到纸带上 self.stack[sp] = buf[0]; IR::JIZ(x) => // 如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处 if self.stack[sp] == 0x00 pc = x as usize; IR::JNZ(x) => // 如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处 if self.stack[sp] != 0x00 pc = x as usize; // 移动计数器，执行下一个指令 pc += 1; Ok(())fn main() -> Result< (), Box< dyn std::error::Error> > let args: Vec< String> = std::env::args().collect(); let data = https://www.songbingjia.com/android/std::fs::read(& args[1])?; let mut interpreter = Interpreter::default(); interpreter.run(data); Ok(())

同样，对以上代码使用 cargo build 得到程序的二进制文件后，执行以下命令将会输出 Hello World! ：

PS W:\\WorkSpace\\Rust\\brainfuck> ./target/debug/brainfuck_ir W:\\WorkSpace\\Rust\\brainfuck\\src\\res\\hello_world.bf Hello World! PS W:\\WorkSpace\\Rust\\brainfuck>

【使用Rust实现一个Brainfuck解释器】在测试中，基于中间语言的解释器大概要比原始解释器快 5 倍左右。但请记住本文设计的 IR 并非最优化的，其仍然有优化空间，例如，可以进一步融合连续的 ADD 和 SUB 以单个 ADD 或 SUB 替代。
参考