How to make a fully functional brainf*ck interpreter?

I have tried to implement a BF interpreter in Javascript. It works for many programs like printing Hello world, looping, etc.

Here is link to a sample interpreter that I use for comparing outputs: https://sange.fi/esoteric/brainfuck/impl/interp/i.html

But when I try to run a BF to C program, it gets stuck like it is in an infinite loop. It however does work in the sample interpreter above. What am I doing wrong?

Here is a BF code that converts an input BF code to C.

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

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

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

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

,[>>+++[<+++++++>-]<[<[-[-<]]>>[>]<-]<[<+++++>-[<+++>-[<-->-[<+++>-
[<++++[>[->>]<[>>]<<-]>[<+++>-[<--->-[<++++>-[<+++[>[-[-[-[->>]]]]<[>>]<<-]
>[<+>-[<->-[<++>-[<[-]>-]]]]]]]]]]]]]

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

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

Here is my implementation:

class Node {
    constructor() {
        this.value = 0;
        this.next = null;
        this.prev = null;
    }

    increment() {
        this.value++;
    }

    decrement() {
        this.value--;
    }
}


class Memory {
  constructor() {
    this.current = new Node();
    this.outputBuffer = [];
  }

  moveRight() {
    if (this.current.next === null) {
        const rightNode = new Node();
        rightNode.prev = this.current
      this.current.next = rightNode;
    }
    this.current = this.current.next;
  }

  moveLeft() {
    if (this.current.prev === null) {
        const leftNode = new Node()
        leftNode.next = this.current;
      this.current.prev = leftNode;
    }
    this.current = this.current.prev;
  }

  increment() {
    this.current.increment();
  }

  decrement() {
    this.current.decrement();
  }

  print() {
    this.outputBuffer.push(String.fromCharCode(this.current.value));
  }

  input(ch) {
    this.current.value = ch.charCodeAt(0);
  }
}

class Interpreter {
  reset() {
    this.memory = new Memory();
    this.instructionPointer = 0;
    this.inputPointer = 0;
      this.openingToClosingBrackets = new Map();
      this.closingToOpeningBrackets = new Map();
  }

  interpret(code, input = "") {
    this.reset();
    this.code = code;
    this.matchSquareBrackets();
    this.input = input;

    while (!this.reachedEOF()) {
      const instruction = this.code[this.instructionPointer];

      switch (instruction) {
        case "+": this.memory.increment(); break;
        case "-": this.memory.decrement(); break;
        case ">": this.memory.moveRight(); break;
        case "<": this.memory.moveLeft(); break;
        case ".": this.memory.print(); break;
        case ",": this.memory.input(this.getNextCharacter()); break;
        case "[": this.loopStart(); break;
        case "]": this.loopEnd(); break;
      }
      this.instructionPointer++;
    }
    return this.memory.outputBuffer.join("");
  }

  reachedEOF() {
    return this.instructionPointer >= this.code.length;
  }

  getNextCharacter() {
    if (this.inputPointer >= this.input.length) {
      throw new Error("EOF. Expected more input characters.");
    }
    return this.input[this.inputPointer];
  }

  loopStart() {
    if (this.memory.current.value !== 0) {
      return;
    }
    this.instructionPointer = this.openingToClosingBrackets.get(
      this.instructionPointer
    );
  }

  loopEnd() {
    if (this.memory.current.value === 0) {
        return;
      }
      this.instructionPointer = this.closingToOpeningBrackets.get(
          this.instructionPointer
      );
  }

  matchSquareBrackets() {
    const openingStack = [];
    for (let i = 0; i < this.code.length; i++) {
      const ch = this.code[i];
      if (ch === "[") {
        openingStack.push(i);
      }
      if (ch === "]") {
        if (openingStack.length === 0) {
          throw new Error("No matching '[' for ']' at index: " + i);
        }
        const openingMatch = openingStack.pop();
        this.openingToClosingBrackets.set(openingMatch, i);
        this.closingToOpeningBrackets.set(i, openingMatch);
      }
    }
    if (openingStack.length > 0) {
      throw new Error(
        "No matching ']' for '[' at indices: " + openingStack.join(", ")
      );
    }
  }
}

Answer

Your getNextCharacter doesn’t work correctly: if there’s at least one character of input, it will return that character each time it’s called – it never increments the input index. Since the bf2c program keeps reading input until there is no more input, this causes your infinite loop.

Another problem with your code is that you throw an exception when , is used and there is no more input, causing the bf2c to abort with an exception when it reaches the end of the input. So you’ll either need to explicitly terminate the input with a , so that the bf2c program knows when to stop reading or change getNextCharacter to return '' at the end of input instead of throwing an exception.

Advertisement

Answer