在解释器中实现Brainfuck循环

我想在我刚创建的编程语言中构建一个Brainfuck（该死的名字）解释器来证明它是图灵完备性的。在解释器中实现Brainfuck循环

到目前为止，一切都很清楚（<>+-,.） - 除了一件事情：循环（[]）。我假设你从这里知道（非常难）BF语法：

如何实现BF在我的翻译循环？

伪代码是怎么样的？当解释器达到循环开始（[）或循环结束（]）时，我该怎么办？

检查循环是否应该继续或停止是没有问题的（current cell==0），但：

何时何地我都检查？
如何知道循环开始的位置？
如何处理嵌套循环？

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

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

来源

2010-04-06 sub

Duplicate：http://stackoverflow.com/questions/1055758/creating-a-brainfk-parser-whats-the-best-method-of-parsing-loop-operators – 2010-06-14 21:21:17

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

如果是假的，你可以扫描匹配]字符的下，计数有多少[看，并确保您标记它们赶走你看到每个]。

如果确实如此，则需要跟踪其位置，以便稍后再跳回。我建议使用堆栈。将当前程序位置推入堆栈，然后在达到]时测试数据指针。如果是，则转到堆栈顶部的程序位置。如果它是错误的，从堆栈中弹出并继续。

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

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

来源

2010-04-06 20:47:32 rjh

我已经建成一个堆栈到我的编程语言，所以这很好：D感谢您的答案 – sub 2010-04-06 20:53:32

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

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

来源

2010-04-06 20:51:32

从我的头顶，可能有一些误差，但这样的事情应该工作：

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

来源

2010-04-06 20:56:17 Jakob

嗯..只有当它从未遇到过“]”时，因为如果是这样，它将返回该字符的位置。但是，即使是由于输入无效导致的段错误也不是很好，不是:)再一次，只是对解决方案的粗略说明，显然不是完美无瑕的解决方案。 – Jakob 2010-04-06 21:55:58

哦，对了，我错过了。我删除了我的评论。 – sepp2k 2010-04-06 22:57:16

我更喜欢使用跳转表（以及将原始BF转换为'字节码'）。优化BF解释器显然是一条可行的路！

来源

2010-05-31 16:01:50 Charles

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

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程序（计算Pi的N个数字）的执行速度，并且与源向前扫描退出[并向后扫描循环]的无辜实现相比，这增加了速度2倍。

来源

2010-06-14 21:15:29

在解释器中实现Brainfuck循环

回答

相关问题