我想用我新创建的编程语言构建一个 Brainfuck（该死的名字）解释器，以证明它是图灵完备的。
现在，到目前为止一切都清楚了（<>+-,.）——除了一件事：循环（[]）。我假设您从这里开始了解（非常困难的）BF 语法：
伪代码是什么样子的？[当解释器到达循环开始（ ）或循环结束（ ）时，我该怎么办]？
检查循环是否应该继续或停止不是问题（current cell==0），而是：
由于循环可以嵌套，我想我不能只使用包含当前循环起始位置的变量。
我见过用各种语言实现的非常小的 BF 解释器，我想知道他们是如何设法使循环工作但无法弄清楚的。
当你到达时[，你测试数据指针。
如果它是假的，您可以扫描下一个匹配 ]的字符，计算[您看到的数量，并确保在看到每个 时将它们标记出来]。
如果是真的，您需要跟踪它的位置，以便稍后跳回它。我建议使用堆栈。将当前程序位置压入堆栈，然后当您到达 时]，测试数据指针。如果为真，则转到堆栈上最顶层的程序位置。如果为假，则从堆栈中弹出该位置并继续。
当您嵌套到内部循环中时，堆栈将清楚地记录每个循环的上下文。
请参阅堆栈（维基百科）。这类似于汇编程序如何处理函数调用。
这是我的解释器的“优化”版本，它预编译循环跳转。
def interpret2(code):
data = [0] * 5000 # data memory
cp = 0 # code pointer
dp = 0 # data pointer
# pre-compile a jump table
stack = []
jump = [None] * len(code)
for i,o in enumerate(code):
if o=='[':
stack.append(i)
elif o==']':
jump[i] = stack.pop()
jump[jump[i]] = i
# execute
while cp < len(code):
cmd = code[cp]
if cmd == '>': dp += 1
elif cmd == '<': dp -= 1
elif cmd == '+': data[dp] += 1
elif cmd == '-': data[dp] -= 1
elif cmd == '.': stdout.write(chr(data[dp]))
elif cmd == ',': data[dp] = ord(stdin.read(1))
elif cmd == '[' and not data[dp]: # skip loop if ==0
cp = jump[cp]
elif cmd == ']' and data[dp]: # loop back if !=0
cp = jump[cp]
cp += 1
它对代码进行空运行，跟踪括号（在堆栈中），并在并行jump数组中标记 goto 地址，稍后在执行期间查询该地址。
[我比较了长时间运行的 BF 程序（计算 Pi 的 N 位）的执行速度，与前向扫描源以退出并向后扫描以循环的无辜实现相比，这将速度提高了 2 倍]。
如何在我的解释器中实现 BF 循环？
这就是重点——这完全取决于您的语言。对于基于堆栈的编程语言（或任何可以使用堆栈的语言），@rjh 提供了一个很好的解决方案。其他语言将使用不同的解决方案，例如递归（即隐式使用堆栈）。
从我的头上看，可能有一些错误，但这样的事情应该有效：
char* interpret(char* instructions){
char* c = instructions;
while (*c) {
if (*c == ".") putchar(*p);
else if (*c == ",") *p = getchar();
else if (*c == '+') (*p)++;
else if (*c == '-') (*p)--;
else if (*c == '<') p--;
else if (*c == '>') p++;
else if (*c == '[') c = interpret(c+1);
else if (*c == ']') { if (*p) c = instructions else return c; }
c++;
}
return 0;
}
使用 Brainf*ck 源代码调用解释。指针 p 指向当前内存位置。当发现 [. 遇到 ] 时从此递归调用返回。
我更喜欢使用跳转表（以及将原始 BF 转换为“字节码”）。优化BF解释器显然是要走的路！