javascript - 如何制作功能齐全的brainf*ck解释器?
问题描述
我试图在 Javascript 中实现一个 BF 解释器。它适用于许多程序,如打印Hello world
、循环等。
这是我用于比较输出的示例解释器的链接: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
工作不正常:如果至少有一个输入字符,则每次调用时都会返回该字符-它永远不会增加输入索引。由于 bf2c 程序一直读取输入直到没有更多输入,这会导致您的无限循环。
您的代码的另一个问题是您在使用时抛出异常,
并且没有更多输入,导致 bf2c 在到达输入末尾时异常中止。因此,您需要使用 a 显式终止输入\0
,以便 bf2c 程序知道何时停止读取或更改getNextCharacter
为在输入结束时返回'\0'
而不是抛出异常。
推荐阅读
- react-native - 依赖 React-Core 时编写 CocoaPod (React/RCTBridge+Private.h)
- java - 使用 Apache 在防火墙后发送电子邮件
- ruby-on-rails - 如何在 Heroku 上重置 Postgresql 表的 id 序列
- machine-learning - 如何将用户输入列表传递给预测模型
- javascript - 从localStorage获取时如何检查空/未定义的字符串值
- sql - 查询以显示值的名称而不是一个表中的 ID
- c - linux kernel 4.12中wake_up_interruptible()的正确用法是什么?
- c - 如何使用 getchar 监控用户输入
- build - 如何启用 DRAFT API for zeromq/cppzmq 以使用 vcpkg 在 Windows 上构建?
- core-data - 将已删除的 CKRecord 与 CoreData NSManagedObject 协调一致