How do I implement the looping functionality in my BrainFuck Interpreter?

Question

There's multiple questions here already, but I'll still proceed. This is a simple BrainFuck interpreter. I figured out all the other symbols, but I can't figure out how to implement loops. Can anyone help?

package com.lang.bfinterpreter;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;


import com.lang.exceptions.TapeSizeExceededException;


public class Interpreter {

    private Interpreter() {
        super();
    }

    private static String getCode(final String inputFile) throws IOException {
        String code = "";
        
        // store the entire code
        final BufferedReader br = new BufferedReader(new FileReader(inputFile));
        for (String line = br.readLine(); line != null; line = br.readLine()) {
            code += line;
        }
        br.close();

        return code;
    }
    
    public static void interpret(final String inputFile) throws IOException,TapeSizeExceededException,IndexOutOfBoundsException {
        // get the program as a string
        final String code = getCode(inputFile);

        // create the Turing tape (static size)
        Character[] tape = new Character[12000];
        Integer indexPointer = 0;
        for (int i = 0; i != 12000; i++) {
            switch (code.toCharArray()[i]) {
                case ',':
                    tape[indexPointer] = (char) System.in.read();
                    break;
                
                case '.':
                    System.out.println(tape[indexPointer]);
                    break;

                case '+':
                    tape[indexPointer]++;
                    break;

                case '-':
                    tape[indexPointer]--;
                    break;

                case '>':
                    if (indexPointer == 11999) {
                        throw new IndexOutOfBoundsException();
                    }
                    else {
                        indexPointer++;
                    }
                    break;

                case '<':
                    if (indexPointer == 0) {
                        throw new IndexOutOfBoundsException();
                    }
                    else {
                        indexPointer--;
                    }
                    break;
                    
                case '[':
                    // I have a feeling I'll need stack to store nested loops   
                    break;
                    
                    case ']':
                    // I have a feeling I'll need stack to store nested loops   
                    break;
                    
                default:
                    break;
            }
        }

    } 
}

I have a feeling that I will need to use Stack, but I just can't seem to figure out how. I have constructed expression evaluators before... will this require the same logic?

Answer 1

The most challenging part, I suppose, is finding the matching brackets. After you find where the matching bracket is, you can just check tape[indexPointer]'s value, and set i to the position after it, which should be rather easy to do.

Given an opening bracket at index i in code, to find its matching close bracket, you just need to go to the right of i in code. You start with an stack with a single [ in it - this is the [ at i. Every time you encounter a new [, you push it onto the stack. Every time you encounter a ], you pop a [ from the stack - this ] you encountered matches the [ you popped! When you popped the last [ from the stack (i.e. when the stack becomes empty), you know you have found the matching close bracket of the open bracket at i.

In code, you don't even need a Stack. You can just use an int to encode how many elements are in the stack - increment it when you push, decrement it when you pop.

private static int findMatchingCloseBracketAfterOpenBracket(char[] code, int openBracketIndex) {
    // parameter validations omitted
    int stack = 1;
    for (int i = openBracketIndex + 1; i < code.length ; i++) {
        if (code[i] == '[') {
            stack++;
        } else if (code[i] == ']') {
            stack--;
        }
        if (stack == 0) {
            return i;
        }
    }
    return -1; // brackets not balanced!
}

To find the matching [ of a ], the idea is same, except you go the other direction, and reverse the push and pop actions.

private static int findMatchingOpenBracketBeforeCloseBracket(char[] code, int closeBracketIndex) {
    // parameter validations omitted
    int stack = 1;
    for (int i = closeBracketIndex - 1; i >= 0 ; i--) {
        if (code[i] == '[') {
            stack--;
        } else if (code[i] == ']') {
            stack++;
        }
        if (stack == 0) {
            return i;
        }
    }
    return -1; // brackets not balanced!
}

(Refactoring the code duplication here is left as an exercise for the reader)

Answer 2

Updated: here's example code. Before the main execution loop you scan the whole program for matches and store them in an array:

    Stack<Integer> stack = new Stack<>();
    int[] targets = new int[code.length];
    for (int i = 0, j; i < code.length; i++) {
        if (code[i] == '[') {
            stack.push(i);
        } else if (code[i] == ']') {
            if (stack.empty()) {
                System.err.println("Unmatched ']' at byte " + (i + 1) + ".");
                System.exit(1);
            } else {
                j = stack.pop();
                targets[i]=j;
                targets[j]=i;
            }
        }
    }
    if (!stack.empty()) {
        System.err.println("Unmatched '[' at byte " + (stack.peek() + 1) + ".");
        System.exit(1);
    }

And then inside the main execution loop you just jump to the precomputed location:

            case '[':
                if (tape[indexPointer] == 0) {
                    i = targets[i];
                }
                break;
                
            case ']':
                if (tape[indexPointer] != 0) {
                    i = targets[i];
                }
                break;

(Note, we jump to the matching bracket, but the for loop will still autoincrement i as usual, so the next instruction that gets executed is the one after the matching bracket, as it should be.)

This is much faster than having to scan through a bunch of code looking for the matching bracket every time a bracket gets executed.

I notice also: you probably want to convert code into an array once, and not once per instruction you execute. You probably want to run your "for" loop while i < codelength, not 12000, and you also probably want to compute codelength only once.

Definitely '.' should output only one character, not add a newline as well. Also, 12000 bytes of array is too small. 30000 is the minimum, and much larger is better.

Good luck!