[TOC]
使用Rust实现一个Brainfuck解释器
brainfuck语法解析
由于 fuck 在英语中是脏话，Brainfuck 有时被称为 Brainfsck，甚至被简称为 BF。它是大多数学生们学习编译器理论知识的好朋友，这一切都是因为它 fuck simple。我们对 JIT 编译器的第一次尝试是如此的简单，甚至有点可笑。不过你想笑就笑吧，很快就会轮到编译器嘲笑你了，你会被告知自己写的解释器有多么的慢。
Brainfuck 是一种简单且最小的图灵完备编程语言。这种语言由八种运算符构成：
| 字符 | 含义 |
|---|---|
| > | 指针加一 |
| < | 指针减一 |
| + | 指针指向的字节的值加一 |
| - | 指针指向的字节的值减一 |
| 。 | 输出指针指向的单元内容（ASCII码） |
| , | 输入内容到指针指向的单元（ASCII码） |
| [ | 如果指针指向的单元值为零，向后跳转到对应的 ] 指令的次一指令处 |
| ] | 如果指针指向的单元值不为零，向前跳转到对应的 [ 指令的次一指令处 |
它几乎完全模仿自图灵纸带机，后者则是计算机的理论基础。理论上一切能被计算的问题都能通过 Brainfuck 被计算。
我们常常使用“可计算性”来描述一个问题是否能被计算。任何计算装置: 算盘，计算机，iPhone 等等，都不能超越图灵机模型的计算能力（考虑速度，只考虑可计算性）。这就是“图灵-邱奇论题（Church–Turing thesis）”。这是一个未被证明的假说，但是实践使人们越来越确信这个假说是真的。
一个著名的不可计算的函数是“海狸很忙函数”。该函数接受输入 n，返回具有 n 个状态的图灵机在停机之前所能打印的最大符号数量。找到海狸很忙函数的上限等于解决停机问题，该问题已被确定不能使用图灵机解决。由于海狸很忙函数不能被图灵机计算，邱奇-图灵论题断言该函数不能使用任何方法进行有效计算。
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(Code { instrs, jtable })
}
}
brainfuck 解释器实现
创建 res 目录，然后再该目录下创建 hello_world.bf 文件，其内容就是 Brainfuck 语法编写的 hello world：
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
然后我们 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 = 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 {
// 初始化，提供默认值
Self { stack: 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 == 0 { 0 } else { sp - 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 = 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) 来表示。为此定义如下的中间语言表示。
中间语言（英语：Intermediate Language，IR），在计算机科学中，是指一种应用于抽象机器（abstract machine）的编程语言，它设计的目的，是用来帮助我们分析计算机程序。这个术语源自于编译器，在编译器将源代码编译为目的码的过程中，会先将源代码转换为一个或多个的中间表述，以方便编译器进行最佳化，并产生出目的机器的机器语言。
我们定义一个新的枚举类型，用于表示 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(Code { instrs })
}
}
经过中间语言优化后的 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 {
// 初始化，提供默认值
Self { stack: 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 == 0 { 0 } else { sp - 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 = 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>
在测试中，基于中间语言的解释器大概要比原始解释器快 5 倍左右。但请记住本文设计的 IR 并非最优化的，其仍然有优化空间，例如，可以进一步融合连续的 ADD 和 SUB 以单个 ADD 或 SUB 替代。
下一篇文章将会介绍如何针对该中间语言编写 JIT 编译器。其核心思想是：将中间语言翻译为语义等价的汇编代码。
参考
- [1] 中间语言，维基百科，https://zh.wikipedia.org/zh-hans/中間語言
- [2] 邱奇-图灵论题，维基百科，https://en.wikipedia.org/wiki/Church-Turing_thesis
