使用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：

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

參考：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 = 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(())
}

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>

參考

[1] 中間語言，維基百科，https://zh.wikipedia.org/zh-hans/中間語言
[2] 邱奇-圖靈論題，維基百科，https://en.wikipedia.org/wiki/Church-Turing_thesis

使用Rust實作一個Brainfuck解釋器

brainfuck文法解析

brainfuck opcode 定義

brainfuck 解釋器實作

測試

使用中間表示

使用中間表示優化運作速度

參考

繼續閱讀

Microsoft Visual C++ 與 MinGW，附圖

error C2143: syntax error : missing ';' before 'type' in Visual C++

dev c++ 中文支援：Illegal byte sequence

轉換與類類型

C++ 99 個常見錯誤一

VBScript編譯器(VBS也瘋狂) v2.3 綠色

個人覺得C++BuilderX是個失敗的作品

黑馬程式員——話說萬丈高樓平地起，C#基礎鞏固筆記

《JAVA程式設計思想》第四版學習需要我記住的something –持有對象

《JAVA程式設計思想》第四版學習需要我記住的something--多态

《JAVA程式設計思想》第四版學習需要我記住的something –複用類

【C++進階】__stdcall 詳解函數調用約定

DOG（4）：解析器的部分實作細節先來說說parser一些可能迷惑的地方結果如何傳回?pcd其實是一回事最後的一點說明

effective c++ 第三版讀書筆記1

可變參數宏， Variadic Macros

什麼是BNF範式