执行>,[.>,]通过移动指针的循环中的一个解释

Question

我想建立一个>,[.>,]通过移动指针(该死的名称)的口译在我的新创建的编程语言来证明这是图灵完整性。

现在，一切都清楚迄今为止(<>+-,.)-除了一件事：循环([]).我假定你知道(极其困难)BF法从这里:

• 我如何实施的BF循环，在我解释?

怎么可能伪看起来像什么？我该怎么办时，该解释达到一个循环的开始([)或循环结束(])?

检查如果循环应该继续或停止不是问题(current cell==0)，但：

• 当和我在哪里都要检查吗？
• 如何知道那里的循环的开始是什么位置？
• 如何处理嵌套循环？

作为的循环，可以嵌套我想，我不能只用一个变量包含的起始位置的目前的循环。

我已经看到非常小的BF口译员实施的各种语言，我不知道他们是如何得到的循环，工作但找不出来。

Answer 1

当你到达 [, 你测试的数据指针。

如果它是错误的，你可以扫描下 匹配 ] 字，计算了多少 [ 你看，并确保纪念他们正如你看到的每 ].

如果这是真的，你需要跟踪的其位置所以你可以跳回到它。我建议使用一堆。推动当前程序的位置上堆，那么当你到达 ], 测试数据指针。如果这是真的，去最上面的程序上的位置。如果它是虚假的，出的位置关闭堆和继续。

因为你窝成内在的循环，堆叠将干净地记录下每个循环。

看看 堆(维基百科).这是类似于如何组件的程序处理功能的电话。

Answer 2

这里是我的"优化"版本的解释，这预先编制的环跳跃。

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 阵列其后磋商期间执行的。

我比较的执行速度长期运行的BF计划(计算N数字Pi)和这种增加的速度2x相比，一个无辜的执行在其源被扫描前退出 [ 和扫描的倒退到环路上 ].

Answer 3

我如何实施的BF循环，在我解释?

这就是–这完全取决于你的语言。对的情况下一堆编程语言(或者任何语言可以使用一堆)，@该公司从事给了一个很好的解决方案。其他语言使用不同的解决方案，例如递归(即隐含的使用stack)。

Answer 4

从我的头顶，可能会有些错误，但这样的事情，应当工作：

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 5

我更喜欢使用一个跳跃表(随着转换的原BF'码').优化BF口译人员是明显的方式去！