How to build a Brainfuck Interpreter in Python?

I have been working on a BF interpreter, trying to ensure it uses no external libraries, and works in a single function.

The issue I am running into is that some programs work perfectly well, and others don't. This is making it hard to debug and figure and what's going wrong.

The common factor seems to be it cannot handle a BF program with more then one set of brackets (although there are some exceptions, but then the programs work, just not completely).

The Code:

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
""")

I know this is not the best Python code, I just thought I'd give it a go.

The programs that work:

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

- Converts lowercase to uppercase

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

- Hello World!

The program I am currently trying to make work is:

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

It's designed to output a Sierpinski Triangle with *s.

I get no output, but if I output the array it appears to create and almost endless array of sequenced 0, 1, 0, 1.....etc. etc.

From running it through a proper interpreter I know that the array should only end up with a length of 120, and I am getting into the thousands within seconds.

Any help would be appreciated.

Thanks.

Solution

There's a bug in your code at handling [ and ]: They don't match the correct braces, instead they match the closest brace which could fit if everything between is ignored including other braces!!! This means you cant nest your loops. I also wrote a bf interpreter in python and I used a counter variable open_braces which starts at 1 and gets incremented by braces open to the search direction and gets decremented by braces closed to the search direction. Fix your code as followed:

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

Please notice that you may keep the if array[pointerLocation] == 0 in the elif code[i] == ']':-block if you care about performance. If you do so, you don't need to decrement i in the last line.