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

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?

CodePudding user response：

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)

CodePudding user response：

The best way to do this is to compute matches for all the brackets once, and store them in a separate array of jump targets. You do this on an initial scan of the program, and you do use a stack; each time you encounter a '[' you push its location on the stack, and each time you encounter a ']' you pop the matching '[' off the stack, and store those brackets' locations as each other's match. Then when executing a '[' or ']' you can jump directly to its match; this is much faster than having to scan through a bunch of code looking for the matching bracket every time a bracket gets executed. A simple example written in C is at http://brainfuck.org/sbi.c in case that helps.

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!