Implementing Brainfuck loops in an interpreter
I want to build a Brainfuck (Damn that name) interpreter in my freshly created programming language to prove it's turing-completeness.
Now, everything is clear so far (<>+-,.) - except one thing: The loops ([]).
I assume that you know the (extremely hard) BF syntax from here on:
- How do I implement the BF loops in my interpreter?
How could the pseudocode look like? What should I do when the interpreter reaches a loop beginning ([) or a loop end (])?
Checking if the loop should continue or stop is not the problem (current cell==0), but:
- When and where do I have to check?
- How to know where the loop beginning is located?
- How to handle nested loops?
As loops can be nested I suppose that I can't just use a variable containing the starting position of the current loop.
I've seen very small BF interpreters implemented in various languages, I wonder how they managed to get the loops working but can't figure it out.
Answer
When you reach [, you test the data pointer.
If it's false, you can scan for the next matched ] character, counting up how many [ you see and making sure you mark them off as you see each ].
If it's true, you need to keep track of its position so you can jump back to it later. I suggest using a stack. Push the current program position onto the stack, then when you reach ], test the data pointer. If it's true, go to the topmost program position on the stack. If it's false, pop the position off the stack and continue.
As you nest into inner loops, the stack will cleanly record the context of each loop.
See stack (wikipedia). This is analogous to how assembly programs deal with function calls.