在解释器中实现 Brainfuck 循环

Question

我想用我新创建的编程语言构建一个 Brainfuck（该死的名字）解释器，以证明它的图灵完备性。

现在，到目前为止一切都清楚了 (<>+-,.) - 除了一件事：循环 ([])。 我假设您从这里开始就知道（极其困难的）BF 语法：

• How do I Implement the BF Loops in myterpreter?

伪代码是什么样的？当解释器到达循环开始 ([) 或循环结束 (]) 时，我应该做什么？

检查循环是否应该继续或停止不是问题（当前单元==0），而是：

• 我必须何时何地进行检查？
• 如何知道循环开始的位置？
• 如何处理嵌套循环？

由于循环可以嵌套，我想我不能只使用包含当前循环起始位置的变量。

我见过用各种语言实现的非常小的 BF 解释器，我想知道他们是如何设法让循环工作的，但无法弄清楚。

Answer 1

如何在解释器中实现 BF 循环？

这就是重点——这完全取决于您的语言。对于基于堆栈的编程语言（或任何可以使用堆栈的语言）的情况，@rjh 给出了一个很好的解决方案。其他语言将使用不同的解决方案，例如递归（即隐式使用堆栈）。

Answer 2

从我的想法来看，其中可能存在一些错误，但类似这样的事情应该有效：

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 指向当前内存位置。发现 [ 时进行递归调用。当遇到 ] 时，从此递归调用返回。

Answer 3

我更喜欢使用跳转表（以及将原始 BF 转换为“字节码”）。优化 BF 解释器显然是正确的出路！

Answer 4

当到达 [ 时，测试数据指针。

如果为 false，您可以扫描下一个匹配 ] 字符，计算您看到的 [ 数量，并确保将它们标记为您会看到每个 ]。

如果这是真的，您需要跟踪它的位置，以便稍后跳回它。我建议使用堆栈。将当前程序位置压入堆栈，然后当到达 ] 时，测试数据指针。如果为真，则转到堆栈中最顶层的程序位置。如果为 false，则将该位置从堆栈中弹出并继续。

当您嵌套到内部循环中时，堆栈将清楚地记录每个循环的上下文。

请参阅堆栈 (wikipedia)。这类似于汇编程序处理函数调用的方式。

Answer 5

这是我的解释器的“优化”版本，它预编译循环跳转。

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

它对代码进行空运行，跟踪括号（在堆栈中）并在并行跳转数组中标记转到地址，稍后在执行过程中会查阅该地址。

我比较了长时间运行的 BF 程序（计算 Pi 的 N 位）的执行速度，与向前扫描源以退出 [ 并向后扫描以循环的无辜实现相比，这将速度提高了 2 倍在]上。