Smallf*ck（简单的 brainfuck 方言）解释器死循环

Question

我正在尝试实现 Smallf*ck 解释器。

Smallfuck 是 Brainfuck 的一种更加简洁的方言，它以位而不是字节为单位进行操作，存储磁带的大小有限，并且没有 I/O 命令。因此，它只剩下 5 个命令：

* : flip the current bit;
> : increment the data pointer (move it to the next cell to the right);
< : decrement the data pointer (move it to the next cell to the left);
[ : “begin loop”:
    if the current bit is 1, increment the instruction pointer
    (move it to the next command to the right), otherwise,
    move it to the next command to the right of the matching ] command;
] : “end loop”:
    if the current bit is 0, increment the instruction pointer,
    otherwise move it to the next command to the right of the matching [ command.
    Can also be interpreted as unconditional jump to the matching [ command,
    since [ performs an extra check itself.

示例输入："*>*>*>*>*>*>*>*", "00101100" 应该 return "11010011"

到目前为止我的实施：

def interpreter(code, tape):
    ptr, cmd_pos = 0, 0
    tape = [int(num) for num in tape]
    while ptr < len(tape) and cmd_pos < len(code):
        if code[cmd_pos] == ">":
            ptr += 1
        elif code[cmd_pos] == "<":
            ptr -= 1
        elif code[cmd_pos] == "*":
            tape[ptr] = 1 if tape[ptr] == 0 else 0
        elif code[cmd_pos] == "[":
            if tape[ptr] == 0:
                found = False
                while not found:
                    cmd_pos += 1
                    if code[cmd_pos] == "]":
                        found = True
        elif code[cmd_pos] == "]":
            found = False
            while not found:
                cmd_pos -= 1
                if code[cmd_pos] == "[":
                    found = True
        cmd_pos += 1
    return ''.join([str(num) for num in tape])

还有一个codewars问题，这就是我这样做的原因：https://www.codewars.com/kata/58678d29dbca9a68d80000d7/train/python

我不知道我的代码有什么问题...基本的东西可以，但循环不行。在 codewars 的一些测试用例中，我创建了一个无限循环，我不知道为什么。

非常感谢您的帮助，也许有人在实现这个方面有很多乐趣：

Answer 1

您还需要考虑嵌套循环。例如，如果您使用代码“[*[>]]”，当您的实现到达外循环的末尾时，它将寻找它左边的第一个“[”并从那里继续。但是因为它是外循环的“]”，所以它应该在同一个外循环的“[”处继续（它在“]”左侧搜索时找到的第二个）。为此，您可以计算向左看时遇到的“]”的数量：

    elif code[cmd_pos] == "]" and tape[ptr]==1:
        found = False
        nestedLoopCounter = 1
        while not found:
            cmd_pos -= 1
            if code[cmd_pos] == "]":
                nestedLoopCounter+=1
            elif code[cmd_pos] == "[":
                nestedLoopCounter-=1
                if nestedLoopCounter==0:
                    found = True
        cmd_pos-=1

另请注意，您需要先检查当前单元格中的值是否为1。 “[”也是如此。如果遇到循环开头，当前单元格值为0，想跳过循环，需要找到匹配的“]”，而不仅仅是遇到的第一个。

Smallf*ck（简单的 brainfuck 方言）解释器死循环

Smallf*ck (simple brainfuck dialect) interpreter endless loop

python

python-3.x

interpreter

brainfuck