如何在 Python 中构建 Brainfuck 解释器？

Question

我一直在研究 BF 解释器，试图确保它不使用外部库，并且在单个函数中工作。

我运行遇到的问题是有些程序运行良好，而有些则不然。这使得调试和弄清楚出了什么问题变得困难。

共同的因素似乎是它不能处理多于一组括号的 BF 程序（虽然有一些例外，但随后程序工作，只是不完全）。

代码：

def interpret(code):
    array = [0]
    pointerLocation = 0
    i = 0
    c = 0
    print(code)
    while i < len(code):
        if code[i] == '<':
            if pointerLocation > 0:
                pointerLocation -= 1
        elif code[i] == '>':
            pointerLocation += 1
            if len(array) <= pointerLocation:
                array.append(0)
        elif code[i] == '+':
            array[pointerLocation] += 1
        elif code[i] == '-':
            if array[pointerLocation] > 0:
                array[pointerLocation] -= 1
        elif code[i] == '.':
            print(array[pointerLocation], chr(array[pointerLocation]))
        elif code[i] == ',':
            x = input("Input:")
            try:
                y = int(x)
            except ValueError:
                y = ord(x)
            array[pointerLocation] = y
        elif code[i] == '[':
            if array[pointerLocation] == 0:
                while code[i] != ']':
                    i += 1
        elif code[i] == ']':
            if array[pointerLocation] != 0:
                while code[i] != '[':
                    i -= 1
        i += 1
interpret("""
                     #This is where the BF code goes
""")

我知道这不是最好的 Python 代码，我只是想试一试。

有效的程序：

,----------[----------------------.,----------]

- 将小写字母转换为大写字母

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

- 世界您好！

我目前正在尝试运行的程序是：

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

它被设计用来输出带*s的谢尔宾斯基三角。

我没有得到任何输出，但如果我输出数组，它似乎创建了几乎无穷无尽的序列 0、1、0、1..... 等数组。等等

从运行通过适当的解释器我知道数组的长度应该只有 120，而我在几秒钟内就达到了数千。

如有任何帮助，我们将不胜感激。

谢谢。

Answer 1

您的代码在处理 [ 和 ] 时存在错误：它们不匹配正确的大括号，而是匹配最接近的大括号可以 fit if everything between are ignored including other braces!!! 这意味着你不能嵌套你的循环。我还在 python 中编写了一个 bf 解释器，我使用了一个计数器变量 open_braces，它从 1 开始，随着大括号向搜索方向打开而递增，并随着大括号向搜索方向关闭而递减。按如下方式修复您的代码：

elif code[i] == '[':
    if array[pointerLocation] == 0:
        open_braces = 1
        while open_braces > 0:
            i += 1
            if code[i] == '[':
                open_braces += 1
            elif code[i] == ']':
                open_braces -= 1
elif code[i] == ']':
    # you don't need to check array[pointerLocation] because the matching '[' will skip behind this instruction if array[pointerLocation] is zero
    open_braces = 1
    while open_braces > 0:
        i -= 1
        if code[i] == '[':
            open_braces -= 1
        elif code[i] == ']':
            open_braces += 1
    # i still gets incremented in your main while loop
    i -= 1

请注意，如果您关心性能，可以将 if array[pointerLocation] == 0 保留在 elif code[i] == ']': 块中。如果这样做，则不需要在最后一行中递减 i。

如何在 Python 中构建 Brainfuck 解释器？

How to build a Brainfuck Interpreter in Python?

python

interpreter

brainfuck