Brainfuck 编程语言
Brainfuck 只有 8 条指令。假设 mp
为内存指针,mv
为 mp
所指内存单元的值,最初两者都为 0
[
:如果mv == 0
,则跳转到相应]
指令的下一条指令处;否则,执行下一条指令。]
:如果mv != 0
,则跳转到相应[
指令的下一条指令处;否则,执行下一条指令。+
:当前内存单元值加一,即mv += 1
(模 256)。-
:当前内存单元值减一,即mv -= 1
(模 256)。<
:内存指针前移,即mp -= 1
>
:内存指针后移,即mp += 1
.
:输出当前内存单元值mv
,
:从用户输入读取一个字节并将其存储在当前内存单元mp
中
例如
+[-]++.
+
:内存单元值mv
加一,得到mv = 1
[
:因为mv != 0
,所以执行下一条指令-
-
:内存单元值mv
加一,得到mv = 0
]
:因为mv == 0
,所以执行下一条指令+
+
:内存单元值mv
加一,得到mv = 1
+
:内存单元值mv
加一,得到mv = 2
.
:输出当前内存单元值mv
[+++++]+
[
:因为mv = 0
,所以跳转到相应]
的下一条指令+
+
:内存单元值mv
加一,得到mv = 1
将 Brianfuck 程序编译为 Brainfuck 汇编程序
Brainfuck 不是一个指令集架构(ISA),因为指令不是自包含的。它们依赖于上下文,即 [
和 ]
不包含跳转目标地址。
为了弥补这一缺陷,我们对 [
和 ]
指令进行修改,让它们后面跟上跳转目标地址。编译器会跟踪一个栈,该栈存储尚未被匹配的 [
。用 c
表示一个计数器,表示到目前位置已经执行了多少条指令。
- 当遇到
[
符号时,a) 将c
压栈,b) 输出指令[0
,其中 0 是跳转目标地址的占位符 - 当遇到
]
符号时,a) 出栈,得到i
,b) 将输出序列中位置为i
的指令[
的占位符设置为i
,即改为[i
,c) 输出指令]i+1
- 当遇到其它字符时,直接输出该字符,栈中不进行任何修改。
代码如下:
/// Initialize a Brainfuck Program from an appropriate file
pub fn from(code: &str) -> Result<Program> {
// keeps track of loop beginnings while (potentially nested) loops are being compiled
let mut loop_stack = vec![];
let mut instructions = Vec::new();
for c in code.chars() {
// to allow skipping a loop and jumping back to the loop's beginning, the respective start and end positions
// are recorded in the program
if c == '[' {
// placeholder for position of loop's end, to be filled in once position is known
instructions.push(Instruction::decode_from(c, Some(0)));
loop_stack.push(instructions.len() - 1);
} else if c == ']' {
// record loop's end in beginning
let start_pos = loop_stack.pop().unwrap();
instructions[start_pos].op_a = instructions.len() as u32;
// record loop's start
instructions.push(Instruction::decode_from(c, Some((start_pos + 1) as u32)));
} else if c != ' ' && c != '\n' && c != '\r' {
instructions.push(Instruction::decode_from(c, None));
}
}
Ok(Self { instructions })
}
对于输入 [----]
,输出为 Program { instructions: [[5, -, -, -, -, ]1] }
Brainfuck 虚拟机
Brainfuck 虚拟机的状态由两种寄存器组成:指令指针 pc
和无限个数据指针 mp
;初始值都为 0。mv
为 mp
中存储的值。
任何虚拟机都定义了一个状态转换函数。运行虚拟机会反复将此函数应用于状态,直到满足终止条件。
在 Brainfuck VM 中,当指令计数器 pc
超出程序长度时终止。
执行一条指令括取指令,执行,指令指针 pc
加一,代码如下:
/// Executes one cycle of the program, returning whether the program has finished.
#[inline]
#[allow(clippy::too_many_lines)]
fn execute_cycle(&mut self) -> Result<bool, ExecutionError> {
// Fetch the instruction at the current program counter.
let instruction = self.fetch();
// Execute the instruction.
self.execute_instruction(&instruction)?;
// Increment the clock.
self.state.global_clk += 1;
let done = self.state.pc == self.program.instructions.len() as u32;
Ok(done)
}
用 program[pc]
表示位置 pc
处的指令
状态转换函数如下:
- 如果
program[pc]
为>
,则mp += 1
,pc += 1
- 如果
program[pc]
为<
,则mp -= 1
,pc += 1
- 如果
program[pc]
为+
, 先从mp
中读出值mv
,然后执行mv += 1
,最后将新的mv
写回mp
中,pc += 1
- 如果
program[pc]
为-
, 先从mp
中读出值mv
,然后执行mv -= 1
,最后将新的mv
写回mp
中,pc += 1
- 如果
program[pc]
为[dst_pos
, 从mp
中读出值mv
,如果mv == 0
,则进行跳转pc = dst_pos
;否则pc += 1
- 如果
program[pc]
为]start_pos
, 从mp
中读出值mv
,如果mv != 0
,则进行跳转pc = start_pos
;否则pc += 1
- 如果
program[pc]
为,
,将输入符号写到mp
,pc += 1
- 如果
program[pc]
为.
,先从mp
中读出值mv
,然后将mv
写到输出流,pc += 1
没有评论