如何制作功能齐全的 brainf*ck 解释器?
How to make a fully functional brainf*ck interpreter?
我尝试在 Javascript 中实现 BF 解释器。它适用于许多程序,如打印 Hello world
、循环等
这是我用来比较输出的示例解释器 link:https://sange.fi/esoteric/brainfuck/impl/interp/i.html
但是当我尝试 运行 一个 BF to C
程序时,它卡住了,就像陷入了无限循环。然而,它在上面的示例解释器中确实有效。我做错了什么?
这是一个 BF
代码,它将输入 BF
代码转换为 C
。
+++[>+++++<-]>>+<[>>++++>++>+++++>+++++>+>>+<++[++<]>---]
>++++.>>>.+++++.>------.<--.+++++++++.>+.+.<<<<---.[>]<<.<<<.-------.>++++.
<+++++.+.>-----.>+.<++++.>>++.>-----.
<<<-----.+++++.-------.<--.<<<.>>>.<<+.>------.-..--.+++.-----<++.<--[>+<-]
>>>>>--.--.<++++.>>-.<<<.>>>--.>.
<<<<-----.>----.++++++++.----<+.+++++++++>>--.+.++<<<<.[>]<.>>
,[>>+++[<+++++++>-]<[<[-[-<]]>>[>]<-]<[<+++++>-[<+++>-[<-->-[<+++>-
[<++++[>[->>]<[>>]<<-]>[<+++>-[<--->-[<++++>-[<+++[>[-[-[-[->>]]]]<[>>]<<-]
>[<+>-[<->-[<++>-[<[-]>-]]]]]]]]]]]]]
<[
-[-[>+<-]>]
<[<<<<.>+++.+.+++.-------.>---.++.<.>-.++<<<<.[>]>>>>>>>>>]
<[[<]>++.--[>]>>>>>>>>]
<[<<++..-->>>>>>]
<[<<..>>>>>]
<[<<..-.+>>>>]
<[<<++..---.+>>>]
<[<<<.>>.>>>>>]
<[<<<<-----.+++++>.----.+++.+>---.<<<-.[>]>]
<[<<<<.-----.>++++.<++.+++>----.>---.<<<.-[>]]
<[<<<<<----.>>.<<.+++++.>>>+.++>.>>]
<.>
]>
,]
<<<<<.<+.>++++.<----.>>---.<<<-.>>>+.>.>.[<]>++.[>]<.
这是我的实现:
class Node {
constructor() {
this.value = 0;
this.next = null;
this.prev = null;
}
increment() {
this.value++;
}
decrement() {
this.value--;
}
}
class Memory {
constructor() {
this.current = new Node();
this.outputBuffer = [];
}
moveRight() {
if (this.current.next === null) {
const rightNode = new Node();
rightNode.prev = this.current
this.current.next = rightNode;
}
this.current = this.current.next;
}
moveLeft() {
if (this.current.prev === null) {
const leftNode = new Node()
leftNode.next = this.current;
this.current.prev = leftNode;
}
this.current = this.current.prev;
}
increment() {
this.current.increment();
}
decrement() {
this.current.decrement();
}
print() {
this.outputBuffer.push(String.fromCharCode(this.current.value));
}
input(ch) {
this.current.value = ch.charCodeAt(0);
}
}
class Interpreter {
reset() {
this.memory = new Memory();
this.instructionPointer = 0;
this.inputPointer = 0;
this.openingToClosingBrackets = new Map();
this.closingToOpeningBrackets = new Map();
}
interpret(code, input = "") {
this.reset();
this.code = code;
this.matchSquareBrackets();
this.input = input;
while (!this.reachedEOF()) {
const instruction = this.code[this.instructionPointer];
switch (instruction) {
case "+": this.memory.increment(); break;
case "-": this.memory.decrement(); break;
case ">": this.memory.moveRight(); break;
case "<": this.memory.moveLeft(); break;
case ".": this.memory.print(); break;
case ",": this.memory.input(this.getNextCharacter()); break;
case "[": this.loopStart(); break;
case "]": this.loopEnd(); break;
}
this.instructionPointer++;
}
return this.memory.outputBuffer.join("");
}
reachedEOF() {
return this.instructionPointer >= this.code.length;
}
getNextCharacter() {
if (this.inputPointer >= this.input.length) {
throw new Error("EOF. Expected more input characters.");
}
return this.input[this.inputPointer];
}
loopStart() {
if (this.memory.current.value !== 0) {
return;
}
this.instructionPointer = this.openingToClosingBrackets.get(
this.instructionPointer
);
}
loopEnd() {
if (this.memory.current.value === 0) {
return;
}
this.instructionPointer = this.closingToOpeningBrackets.get(
this.instructionPointer
);
}
matchSquareBrackets() {
const openingStack = [];
for (let i = 0; i < this.code.length; i++) {
const ch = this.code[i];
if (ch === "[") {
openingStack.push(i);
}
if (ch === "]") {
if (openingStack.length === 0) {
throw new Error("No matching '[' for ']' at index: " + i);
}
const openingMatch = openingStack.pop();
this.openingToClosingBrackets.set(openingMatch, i);
this.closingToOpeningBrackets.set(i, openingMatch);
}
}
if (openingStack.length > 0) {
throw new Error(
"No matching ']' for '[' at indices: " + openingStack.join(", ")
);
}
}
}
您的 getNextCharacter
无法正常工作:如果至少有一个输入字符,它会在每次调用时 return 该字符 - 它永远不会增加输入索引。由于 bf2c 程序一直读取输入直到没有更多输入,这会导致无限循环。
你的代码的另一个问题是当使用 ,
并且没有更多输入时你抛出异常,导致 bf2c 在到达输入末尾时异常中止。因此,您要么需要使用 [=12=]
显式终止输入,以便 bf2c 程序知道何时停止读取,要么在最后将 getNextCharacter
更改为 return '[=14=]'
输入而不是抛出异常。
我尝试在 Javascript 中实现 BF 解释器。它适用于许多程序,如打印 Hello world
、循环等
这是我用来比较输出的示例解释器 link:https://sange.fi/esoteric/brainfuck/impl/interp/i.html
但是当我尝试 运行 一个 BF to C
程序时,它卡住了,就像陷入了无限循环。然而,它在上面的示例解释器中确实有效。我做错了什么?
这是一个 BF
代码,它将输入 BF
代码转换为 C
。
+++[>+++++<-]>>+<[>>++++>++>+++++>+++++>+>>+<++[++<]>---]
>++++.>>>.+++++.>------.<--.+++++++++.>+.+.<<<<---.[>]<<.<<<.-------.>++++.
<+++++.+.>-----.>+.<++++.>>++.>-----.
<<<-----.+++++.-------.<--.<<<.>>>.<<+.>------.-..--.+++.-----<++.<--[>+<-]
>>>>>--.--.<++++.>>-.<<<.>>>--.>.
<<<<-----.>----.++++++++.----<+.+++++++++>>--.+.++<<<<.[>]<.>>
,[>>+++[<+++++++>-]<[<[-[-<]]>>[>]<-]<[<+++++>-[<+++>-[<-->-[<+++>-
[<++++[>[->>]<[>>]<<-]>[<+++>-[<--->-[<++++>-[<+++[>[-[-[-[->>]]]]<[>>]<<-]
>[<+>-[<->-[<++>-[<[-]>-]]]]]]]]]]]]]
<[
-[-[>+<-]>]
<[<<<<.>+++.+.+++.-------.>---.++.<.>-.++<<<<.[>]>>>>>>>>>]
<[[<]>++.--[>]>>>>>>>>]
<[<<++..-->>>>>>]
<[<<..>>>>>]
<[<<..-.+>>>>]
<[<<++..---.+>>>]
<[<<<.>>.>>>>>]
<[<<<<-----.+++++>.----.+++.+>---.<<<-.[>]>]
<[<<<<.-----.>++++.<++.+++>----.>---.<<<.-[>]]
<[<<<<<----.>>.<<.+++++.>>>+.++>.>>]
<.>
]>
,]
<<<<<.<+.>++++.<----.>>---.<<<-.>>>+.>.>.[<]>++.[>]<.
这是我的实现:
class Node {
constructor() {
this.value = 0;
this.next = null;
this.prev = null;
}
increment() {
this.value++;
}
decrement() {
this.value--;
}
}
class Memory {
constructor() {
this.current = new Node();
this.outputBuffer = [];
}
moveRight() {
if (this.current.next === null) {
const rightNode = new Node();
rightNode.prev = this.current
this.current.next = rightNode;
}
this.current = this.current.next;
}
moveLeft() {
if (this.current.prev === null) {
const leftNode = new Node()
leftNode.next = this.current;
this.current.prev = leftNode;
}
this.current = this.current.prev;
}
increment() {
this.current.increment();
}
decrement() {
this.current.decrement();
}
print() {
this.outputBuffer.push(String.fromCharCode(this.current.value));
}
input(ch) {
this.current.value = ch.charCodeAt(0);
}
}
class Interpreter {
reset() {
this.memory = new Memory();
this.instructionPointer = 0;
this.inputPointer = 0;
this.openingToClosingBrackets = new Map();
this.closingToOpeningBrackets = new Map();
}
interpret(code, input = "") {
this.reset();
this.code = code;
this.matchSquareBrackets();
this.input = input;
while (!this.reachedEOF()) {
const instruction = this.code[this.instructionPointer];
switch (instruction) {
case "+": this.memory.increment(); break;
case "-": this.memory.decrement(); break;
case ">": this.memory.moveRight(); break;
case "<": this.memory.moveLeft(); break;
case ".": this.memory.print(); break;
case ",": this.memory.input(this.getNextCharacter()); break;
case "[": this.loopStart(); break;
case "]": this.loopEnd(); break;
}
this.instructionPointer++;
}
return this.memory.outputBuffer.join("");
}
reachedEOF() {
return this.instructionPointer >= this.code.length;
}
getNextCharacter() {
if (this.inputPointer >= this.input.length) {
throw new Error("EOF. Expected more input characters.");
}
return this.input[this.inputPointer];
}
loopStart() {
if (this.memory.current.value !== 0) {
return;
}
this.instructionPointer = this.openingToClosingBrackets.get(
this.instructionPointer
);
}
loopEnd() {
if (this.memory.current.value === 0) {
return;
}
this.instructionPointer = this.closingToOpeningBrackets.get(
this.instructionPointer
);
}
matchSquareBrackets() {
const openingStack = [];
for (let i = 0; i < this.code.length; i++) {
const ch = this.code[i];
if (ch === "[") {
openingStack.push(i);
}
if (ch === "]") {
if (openingStack.length === 0) {
throw new Error("No matching '[' for ']' at index: " + i);
}
const openingMatch = openingStack.pop();
this.openingToClosingBrackets.set(openingMatch, i);
this.closingToOpeningBrackets.set(i, openingMatch);
}
}
if (openingStack.length > 0) {
throw new Error(
"No matching ']' for '[' at indices: " + openingStack.join(", ")
);
}
}
}
您的 getNextCharacter
无法正常工作:如果至少有一个输入字符,它会在每次调用时 return 该字符 - 它永远不会增加输入索引。由于 bf2c 程序一直读取输入直到没有更多输入,这会导致无限循环。
你的代码的另一个问题是当使用 ,
并且没有更多输入时你抛出异常,导致 bf2c 在到达输入末尾时异常中止。因此,您要么需要使用 [=12=]
显式终止输入,以便 bf2c 程序知道何时停止读取,要么在最后将 getNextCharacter
更改为 return '[=14=]'
输入而不是抛出异常。