在 cmp 中超出最大递归深度，Python

Question

我是 Python 的初级程序员，试图通过构建 BF 解释器来练习。但是，它不适用于 Hello, World!程序：

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

给出一个RuntimeError: maximum recursion depth exceeded in cmp。我的代码如下。

import sys

script, file = sys.argv


tape, tapeslct, cmdslct = [0], 0, 0
code = open(file)
program = filter(lambda x: x in ['.', ',', '[', ']', '<', '>', '+', '-'], code.read())
print(str(program))
program = list(program)

def execute(cmd):
    global tape
    global tapeslct
    global cmdslct
    if cmd == "+":
        tape[tapeslct] += 1
    if cmd == "-":
        tape[tapeslct] -= 1
    if cmd == ">":
        tapeslct += 1
        if tapeslct == len(tape):
            tape.append(0)
    if cmd == "<":
        tapeslct -= 1
    if cmd == ".":
        print(chr(tape[tapeslct]))
    if cmd == ",":
        tape[tapeslct] = ord(input())
    if cmd == "[":
        if tape[tapeslct] >= 1:
            loopend = 0
            testfor = cmdslct
            while loopend == 0:
                testfor += 1
                if program[testfor] == "]" and tape[tapeslct] >= 0:
                    testfor = cmdslct + 1
                    execute(program[testfor])
                elif program[testfor] == "]" and tape[tapeslct] == 0:
                    loopend = 1
                    cmdslct = testfor + 1
                else:
                    execute(program[testfor])
        else:
            while loopend == 0:
                testfor += 1
                if program[testfor] == "]":
                    loopend = 1
while len(program) > cmdslct:
    execute(program[cmdslct])
    cmdslct += 1

lambda 片段取自 Python 中的另一个 BF 解释器，找到 here。

我很可能错过了一些东西。

Answer 1

据我所知，您的 [ 和 ] 实现很不稳定。您在子程序中开始使用不同的指令指针（testfor 而不是 cmdslct）；但是当你点击另一个 [ 时，你会从 cmdslct 而不是当前的 testfor 开始下一个循环，这使得嵌套循环变得不可能。

我建议您不要将循环视为特殊循环。当[到来时，直接将当前位置压入栈；当 ] 出现时，弹出它，然后根据磁带跳转或忽略。这样，你甚至不需要递归。

或者，将指令指针而不是 cmd 传递到递归中。

if cmd == "[":
    # remember loop start
    stack.append(cmdslct)
    if tape[tapeslct] == 0:
        # end of loop; find the matching loop end
        loops = 1
        while not (program[cmdslct] == ']' and loops > 0):
            cmdslct += 1
            if program[cmdslct] == '[':
                loops += 1
            elif program[cmdslct] == ']':
                loops -= 1
if cmd == ']':
    if tape[tapeslct] != 0:
        # jump back
        cmdslct = stack[-1]
    else:
        # forget about this loop and move on
        stack.pop()

在 cmp 中超出最大递归深度，Python

Maximum recursion depth exceeded in cmp, Python

python

recursion

interpreter

runtime-error