3. 中间表示

为了方便后期处理，我们先将 Brainfuck 代码转换为一种中间表示 (IR).

在 src 目录下添加文件 bfir.rs

此时目录结构

.
├── Cargo.lock
├── Cargo.toml
└── src
   ├── bfir.rs
   └── main.rs

main.rs

mod bfir;

fn main() {
    println!("Hello, world!");
}

本节以下代码都将写入 bfir.rs

IR 定义

AddVal, SubVal 表示将当前单元加减某一数值。

AddPtr, SubPtr 表示将数据指针加减某一数值。

Jz，Jnz 表示跳转指令，带有跳转地址。

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BfIR {
    AddVal(u8),  // +
    SubVal(u8),  // -
    AddPtr(u32), // >
    SubPtr(u32), // <
    GetByte,     // ,
    PutByte,     // .
    Jz,          // [
    Jnz,         // ]
}

错误处理

我们使用 thiserror 库，用来轻松定义错误类型。

https://github.com/dtolnay/thiserror

导入第三方库时：

若 Rust 版本 >= 1.62，可直接 cargo add 。

若 Rust 版本 < 1.62，推荐用 cargo-edit 插件。安装 cargo-edit 插件后，可以用命令导入第三方库。

https://github.com/killercup/cargo-edit

也可手动编辑 Cargo.toml。

cargo install cargo-edit

cargo add thiserror

错误定义

#[derive(Debug, thiserror::Error)]
pub enum CompileErrorKind {
    #[error("Unclosed left bracket")]
    UnclosedLeftBracket,
    #[error("Unexpected right bracket")]
    UnexpectedRightBracket,
}

#[derive(Debug)]
pub struct CompileError {
    line: u32,
    col: u32,
    kind: CompileErrorKind,
}

为 CompileError 实现 Display 和 Error，Display 用于对人友好的信息，Error 表明它是一个错误类型。

#[derive(Debug)]
pub struct CompileError {
    line: u32,
    col: u32,
    kind: CompileErrorKind,
}

impl fmt::Display for CompileError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} at line {}:{}", self.kind, self.line, self.col)
    }
}

编译为 IR

pub fn compile(src: &str) -> Result<Vec<BfIR>, CompileError> {
    let mut code: Vec<BfIR> = vec![];

    let mut stk: Vec<(u32, u32, u32)> = vec![];

    let mut line: u32 = 1;
    let mut col: u32 = 0;

compile 函数接收一个字符串，返回 IR 序列。

code 存储已解析的 IR，stk 作为栈，存储左括号的IR位置、源代码行位置、源代码列位置，line 和 col 分别记录行号和列号。

主循环结构

for ch in src.chars() {
    col += 1;
    match ch {
        ...
    }
}

处理换行

'\n' => {
    line += 1;
    col = 0;
}

处理普通指令

'+' => code.push(BfIR::AddVal(1)),
'-' => code.push(BfIR::SubVal(1)),
'>' => code.push(BfIR::AddPtr(1)),
'<' => code.push(BfIR::SubPtr(1)),
',' => code.push(BfIR::GetByte),
'.' => code.push(BfIR::PutByte),

处理左括号，将左括号位置入栈。

'[' => {
    let pos = code.len() as u32;
    stk.push((pos, line, col));
    code.push(BfIR::Jz)
}

处理右括号，从栈中弹出左括号位置，如果栈为空，说明没有匹配的左括号，生成一个编译错误并返回。如果有匹配的左括号，则正常生成 IR。

']' => {
    stk.pop().ok_or(CompileError {
        line,
        col,
        kind: CompileErrorKind::UnexpectedRightBracket,
    })?;

    code.push(BfIR::Jnz)
}

忽略其他字符

_ => {}

循环结束后，如果栈不为空，说明有左括号没有匹配到右括号，弹出左括号位置，生成编译错误。最后返回生成的IR.

if let Some((_, line, col)) = stk.pop() {
    return Err(CompileError {
        line,
        col,
        kind: CompileErrorKind::UnclosedLeftBracket,
    });
}
Ok(code)

完整代码

pub fn compile(src: &str) -> Result<Vec<BfIR>, CompileError> {
    let mut code: Vec<BfIR> = vec![];

    let mut stk: Vec<(u32, u32, u32)> = vec![];

    let mut line: u32 = 1;
    let mut col: u32 = 0;

    for ch in src.chars() {
        col += 1;
        match ch {
            '\n' => {
                line += 1;
                col = 0;
            }
            '+' => code.push(BfIR::AddVal(1)),
            '-' => code.push(BfIR::SubVal(1)),
            '>' => code.push(BfIR::AddPtr(1)),
            '<' => code.push(BfIR::SubPtr(1)),
            ',' => code.push(BfIR::GetByte),
            '.' => code.push(BfIR::PutByte),
            '[' => {
                let pos = code.len() as u32;
                stk.push((pos, line, col));
                code.push(BfIR::Jz)
            }
            ']' => {
                stk.pop().ok_or(CompileError {
                    line,
                    col,
                    kind: CompileErrorKind::UnexpectedRightBracket,
                })?;

                code.push(BfIR::Jnz)
            }
            _ => {}
        }
    }
    if let Some((_, line, col)) = stk.pop() {
        return Err(CompileError {
            line,
            col,
            kind: CompileErrorKind::UnclosedLeftBracket,
        });
    }
    Ok(code)
}

简单优化

brainfuck 代码中经常有连续的算术加减和指针移动，这些操作完全可以折叠起来。

优化函数直接操作 IR 序列，用一次遍历完成折叠，原地操作。时间复杂度 O(n)，空间复杂度 O(1)。

这里定义两个宏来避免复制粘贴大量同样的代码。

    let mut i = 0;
    let mut pc = 0;

    macro_rules! _fold_ir {
        ($variant:ident, $x:ident) => {{
            let mut j = i + 1;
            while j < len {
                if let $variant(d) = code[j] {
                    $x = $x.wrapping_add(d);
                } else {
                    break;
                }
                j += 1;
            }
            i = j;
            code[pc] = $variant($x);
            pc += 1;
        }};
    }

    macro_rules! _normal_ir {
        () => {{
            code[pc] = code[i];
            pc += 1;
            i += 1;
        }};
    }

    use BfIR::*;
    while i < len {
        match code[i] {
            AddPtr(mut x) => _fold_ir!(AddPtr, x),
            SubPtr(mut x) => _fold_ir!(SubPtr, x),
            AddVal(mut x) => _fold_ir!(AddVal, x),
            SubVal(mut x) => _fold_ir!(SubVal, x),
            GetByte => _normal_ir!(),
            PutByte => _normal_ir!(),
            Jz => _normal_ir!(),
            Jnz => _normal_ir!(),
        }
    }

    code.truncate(pc);
    code.shrink_to_fit();
}

简单测试

Rust 内置一套单元测试框架，在模块内随手写个函数，标上 #[test]，然后运行命令 cargo test。cargo 会收集所有测试，逐个运行，并报告结果。

#[test]
fn test_compile() {
    assert_eq!(
        compile("+[,.]").unwrap(),
        vec![
            BfIR::AddVal(1),
            BfIR::Jz,
            BfIR::GetByte,
            BfIR::PutByte,
            BfIR::Jnz,
        ]
    );

    match compile("[").unwrap_err().kind {
        CompileErrorKind::UnclosedLeftBracket => {}
        _ => panic!(),
    };

    match compile("]").unwrap_err().kind {
        CompileErrorKind::UnexpectedRightBracket => {}
        _ => panic!(),
    };

    let mut code = compile("[+++++]").unwrap();
    optimize(&mut code);
    assert_eq!(code, vec![BfIR::Jz, BfIR::AddVal(5), BfIR::Jnz]);
}