在解释器中实现Brainfuck循环

Question

我想用我刚刚创建的编程语言构建一个Brainfuck(该死的名字)解释器,以证明它是图灵完整性.

现在,到目前为止一切都很清楚(<>+-,.) - 除了一件事:循环([]).我假设你从这里知道(极其困难的)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数组中标记goto地址,稍后在执行期间查询.

我比较了长时间运行的BF程序的执行速度(计算Pi的N位数),这比无辜的实现提高了2倍,其中源被向前扫描以退出[并向后扫描到循环].