Inspired by FizzBuzz by Brainfuck, I decided to write an interpreter for Brainfuck. It:Removes all non-command charactersOptimizes commands (removing +- and <> pairs)Executes each command one-by-oneSpeed:FizzBuzz by Brainfuck: about 10 millisecondsCode:BFInterpreter.javaimport java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class BFInterpreter {    public static final int BF_MEMORY_SIZE = 30000;    private static final InputStreamReader INPUT = new InputStreamReader(            System.in);    private static final int BYTE_SIZE = 256;    private static final int HALF_BYTE = BYTE_SIZE / 2;    public static void interpret(BFCode code) {        // Check for errors        if (hasErrors(code.getCode())) {            throw new IllegalArgumentException(                    code has at least one error in it);        }        // -128 = 0, 0 = 128, 127 = 255 etc.        byte[] bfMemory = new byte[BF_MEMORY_SIZE];        Arrays.fill(bfMemory, Byte.MIN_VALUE);        char[] commands = code.getOptimizedCode().toCharArray();        for (int i = 0, pointer = 0, len = commands.length; i < len; i++) {            switch (commands[i]) {            case '+':                bfMemory[pointer]++;                break;            case '-':                bfMemory[pointer]--;                break;            case '<':                if (--pointer == -1) {                    pointer += BF_MEMORY_SIZE;                }                break;            case '>':                if (++pointer == BF_MEMORY_SIZE) {                    pointer = 0;                }                break;            case '.':                System.out.print((char) (bfMemory[pointer] + HALF_BYTE));                break;            case ',':                try {                    bfMemory[pointer] = (byte) (INPUT.read() - HALF_BYTE);                } catch (IOException e) {                    // EOF? no change                }                break;            case '[':                if (bfMemory[pointer] == Byte.MIN_VALUE) { // == 0                    i = indexOfMatchingCloseBracket(commands, i);                }                break;            case ']':                if (bfMemory[pointer] != Byte.MIN_VALUE) { // == 0                    i = indexOfMatchingOpenBracket(commands, i);                }            }        }    }    private static boolean hasErrors(String bfCode) {        // each [ must have a ]        char[] commands = bfCode.toCharArray();        int diff = 0;        for (char command : commands) {            if (command == '[') {                diff++;            } else if (command == ']') {                diff--;            }            if (diff < 0) {                return false;            }        }        return diff != 0;    }    private static int indexOfMatchingCloseBracket(char[] commands, int currentIndex) {        int index = currentIndex;        int numOfOpeningBrackets = 1;        while (numOfOpeningBrackets != 0) {            index++;            if (commands[index] == ']') {                numOfOpeningBrackets--;            } else if (commands[index] == '[') {                numOfOpeningBrackets++;            }        }        return index;    }    private static int indexOfMatchingOpenBracket(char[] commands,            int currentIndex) {        int index = currentIndex;        int numOfClosingBrackets = 1;        while (numOfClosingBrackets != 0) {            index--;            if (commands[index] == ']') {                numOfClosingBrackets++;            } else if (commands[index] == '[') {                numOfClosingBrackets--;            }        }        return index;    }}BFCode.javapublic class BFCode {    private final String code;    public BFCode(String code) {        this.code = code;    }    public String getCode() {        return code;    }    public String getOptimizedCode() {        return BFOptimizer.optimize(code);    }}BFOptimizer.javapublic class BFOptimizer {    public static final String NOT_BF_REGEX = [^\\Q><+-.,[]\\E];    public static final String EMPTY_STRING = ;    public static String optimize(String bfCode) {        bfCode = bfCode.replaceAll(NOT_BF_REGEX, EMPTY_STRING);        while (true) {            String result = bfCode.replaceAll((\\+\\-)|(\\-\\+)|(<>)|(><), EMPTY_STRING);            if (result.equals(bfCode)) {                return result;            }            bfCode = result;        }    }}Concerns:It's really slow executing each command one-by-one. I was thinking of grouping all same commands together, but that will have to wait until the next revision.Naming?Anything?
Brainfuck Interpreter: Slower than a Snail?
java;performance;interpreter;brainfuck
PerformanceIt looks like the biggest performance problem is in        case '[':            if (bfMemory[pointer] == Byte.MIN_VALUE) { // == 0                i = indexOfMatchingCloseBracket(commands, i);            }            break;        case ']':            if (bfMemory[pointer] != Byte.MIN_VALUE) { // == 0                i = indexOfMatchingOpenBracket(commands, i);            }Each time the interpreter hits the bracket, it performs a linear search over the source code. You may want to memoize a target address once the branch is taken.Bug?hasErrors returning false on diff < 0 sounds like a bug. The diff < 0 is an error, no?Missing diagnosticsI'd want to know an exact position of a faulty bracket. In any case, checking for errors prior to execution is questionable. You may consider a interpretation-time exception.