Weiter zum Inhalt

C) Brainfuck Interpreter

Vielleicht kennen Sie bereits die Esoterische Programmiersprache BrainFuck?! Diese sehr simple Programmiersprache besteht aus lediglich acht Befehlen und ist relativ einfach zu interpretieren. Einen Interpreter für eine solche Sprache ist deshalb der ideale Einstieg um Ihr Verständnis, wie Software und Programmiersprachen funktionieren, zu vertiefen und zu festigen.

Die Sprache BrainFuck

Um einen BrainFuck-Interpreter zu programmieren, müssen Sie zuerst wissen, was die Programmiersprache BrainFuck eigentlich ist, und wie sie sich verhält. Verfügen Sie bereits über dieses Wissen, können Sie dieses Teilkapitel überspringen.

Ein BrainFuck-Programm wird sequenziell abgearbeitet und hat eine Reihe von Byte-Zellen zur Verfügung. Zusätzlich existiert ein Pointer (Zeiger), der auf eine bestimmte Zelle verweist. Mit dem Operator + (Plus) wird der Wert (default = 0), der sich in der Zelle befindet auf die der Pointer zeigt, um den Faktor eins erhöht. Ein - (Minus) verringert den Wert in der aktuellen Zelle um den Faktor eins. Sie können den Zeiger auf die nächste Zelle mit dem Zeichen > (Größer-Als) bzw. auf die vorhergehende Zelle mit dem Zeichen < (Kleiner-Als) verschieben. Mit dem . (Punkt) wird der Wert, der sich in der aktuellen Zelle befindet, als ASCII-Zeichen ausgegeben. Ein , (Komma) ermöglicht das Einlesen eines Zeichens. Der ASCII-Wert dieses Zeichens wird in die aktuelle Zelle geschrieben. Als letzte Zeichen gibt es [ (eckige Klammer auf) und ] (eckige Klammer zu). Diese ermöglichen eine Schleife. Ist am Schleifenanfang ([) der Wert der aktuellen zelle gleich 0, ist die Schleife zu Ende und es wird auf das erste Zeichen im Code nach dem Endzeichen der Schleife (]) gesprungen. Wird das Schleifenende erreicht, wird wieder auf den Schleifenanfang gesprungen.

Ein einfaches HelloWorld in BrainFuck könnte so aussehen:

[-]>[-]< // Verwendete Zellen auf 0 setzen
>++++++++[<+++++++++>-]<.    // H
>+++++[<++++++>-]<-.         // e
+++++++.                     // l
.                            // l
+++.                         // o
>++++++++[<---------->-]<+.  // space
>+++++++[<++++++++>-]<-.     // W
>++++[<++++++>-]<.           // o
+++.                         // r
------.                      // l
--------.                    // d
[-] // aktuelle Zelle wieder auf 0 setzen

Der BrainFuck-Interpreter

Erzeugen Sie zuerst eine einfache Klasse für den Interpreter. Wir könnten diese bspw. BrainFucker nennen. Sie enthält einen InputStream für die Eingabe, einen OutputStream für die Ausgabe und ein int-Array für die einzelnen Byte-Zellen. Die Streams werden im Konstruktor mitgegeben, die Anzahl der verfügbaren Zellen kann optional gesetzt werden. Falls diese nicht gesetzt wird, wird das Array mit einer Standardgröße von 32768 (2^15) initialisiert.

package de.jbb.bf;

import java.io.InputStream;
import java.io.OutputStream;

public class BrainFucker {

  private InputStream inp;
  private OutputStream out;
  private int[] fields;

  public BrainFucker(InputStream input, OutputStream output) {
    this(input, output, 32768);
  }

  public BrainFucker(InputStream input, OutputStream output, int fieldCnt) {

    this.inp = input;
    this.out = output;
    this.fields = new int[fieldCnt];
  }
}

Jetzt fehlt natürlich noch die Methode, die einen gegebenen Quellcode interpretiert. Diese nennen Sie interpret und erhält den Code übergeben als char-Array. Zu Beginn der Methode wird ein Pointer auf die erste Zelle gesetzt. Anschließend wird der Code Zeichen für Zeichen in einer for-Schleife durchlaufen. Diese Schleife ist von einem try-catch-Block umschlossen, der evtl. auftretende Probleme mit den Streams abfängt bzw. sonstige Exceptions als Syntaxfehler interpretiert.

public void interpret(char[] arr) {

  int length = arr.length;
  int pointer = 0;
  try {
    for (int i = 0; i < length; i++) {
    }
  }
  catch (IOException e) {
    throw new RuntimeException("Can't read or write", e);
  }
  catch (Exception e) {
    throw new RuntimeException("Syntaxerror", e);
  }
}

Innerhalb der for-Schleife wird in einem switch-case-Block die durchzuführende Aktion ermittelt. Ungültige Zeichen werden ignoriert.

switch (arr[i]) {
  case '+':
    break;
  case '-':
    break;
  case '<':
    break;
  case '>':
    break;
  case '[':
    break;
  case ']':
    break;
  case '.':
    break;
  case ',':
}

Entspricht das aktuelle Zeichen einem +, wird die Zelle, auf die momentan der Pointer zeigt, um den Faktor eins erhöht. Gleichzeitig muss überprüft werden, ob die aktuelle Zelle den Wert 255 (Wertebereich eines unsigned Bytes) überschritten hat. Ist dies der Fall, wird die Zelle auf 0 gesetzt.

case '+':
  this.fields[pointer] += 1;
  if (this.fields[pointer] > 255) {
    this.fields[pointer] = 0;
  }
  break;

Bei einem - wird der Wert in der aktuellen Zelle um den Faktor eins reduziert. Ist der neue Wert kleiner als 0, wird der Wert (ähnlich wie beim Plus) auf 255 gesetzt.

case '-':
  this.fields[pointer] -= 1;
  if (this.fields[pointer] < 0) {
    this.fields[pointer] = 255;
  }
  break;

Mit den Zeichen < und > wird der Pointer verschoben. Dabei muss darauf geachtet werden, dass sich der Pointer weiterhin im Wertebereich des Zellen-Arrays befindet.

case '<':
  pointer--;
  if (pointer < 0) {
    pointer = this.fields.length - 1;
  }
  break;
case '>':
  pointer++;
  if (pointer == this.fields.length) {
    pointer = 0;
  }
  break;

Die Zeichen . und , sind auch noch sehr einfach zu interpretieren. Es wird das Zeichen in der aktuellen Zelle an den OutputStream geschickt, bzw. aus dem InputStream ein Zeichen ausgelesen und in die aktuelle Zelle geschrieben. Anschließend muss die Zelle noch dahingehend überprüft werden, ob sich in ihr ein gültiger Wert befindet (siehe Plus und Minus).

case '.':
  this.out.write(this.fields[pointer]);
  break;
case ',':
  this.fields[pointer] = this.inp.read();
  if (this.fields[pointer] > 255) {
    this.fields[pointer] = 255;
  }
  else if (this.fields[pointer] < 0) {
    this.fields[pointer] = 0;
  }

Die Interpretation einer Schleife ist ein bisschen komplexer. Falls der Wert in der aktuellen Zelle gleich 0 ist, wird in einer weiteren for-Schleife nach dem Ende der BrainFuck-Schleife gesucht. Ist dieses gefunden, wird die Abarbeitungsposition des Codes auf die Stelle gesetzt, an welcher sich das Endzeichen befindet. Dabei ist zu beachten, dass sich auch weitere Schleifen in dieser Schleife befinden können. Es muss also mitgezählt werden, wie viele Schleifen sich anschließend öffnen und wieder schließen, damit zur richtigen Stelle gesprungen werden kann.

case '[':
  if (this.fields[pointer] == 0) {
    i++;
    for (int cnt = 1;; i++) {
      if (arr[i] == ']') {
        cnt--;
      }
      else if (arr[i] == '[') {
        cnt++;
      }
      if (cnt == 0) {
        break;
      }
    }
  }

Zeigt der Pointer auf keine 0, wird ganz normal mit dem nächsten Zeichen fortgefahren. Zusätzlich sollte man sich jedoch noch die Position des Schleifenanfangs merken, damit am Ende der Schleife nicht erst nach diesem Anfang gesucht werden muss, sondern einfach auf die Stelle gesprungen werden kann. Da es wie gesagt auch verschachtelte Schleifen geben kann, empfiehlt sich der Einsatz einer LinkedList, bei welcher immer an erster Stelle die aktuelle Position der zuletzt geöffneten Schleife eingetragen wird. Diese Liste muss natürlich auch vorher deklariert und initialisiert werden, weshalb sich der Quellcode wie folgt ändert (gekürzt):

public class BrainFucker {

  // ... LinkdedList deklarieren
  private LinkedList<Integer> openedLoops;
  // ...

  public BrainFucker(InputStream input, OutputStream output, int fieldCnt) {

    this.inp = input;
    this.out = output;
    this.fields = new int[fieldCnt];
    // LinkedList initialisieren
    this.openedLoops = new LinkedList<Integer>();
  }

  public void interpret(char[] arr) {

    // ... LinkedList leeren
    this.openedLoops.clear();
    // ... in der for-Schleife
          case '[':
            if (this.fields[pointer] == 0) {
              i++;
              for (int cnt = 1;; i++) {
                if (arr[i] == ']') {
                  cnt--;
                }
                else if (arr[i] == '[') {
                  cnt++;
                }
                if (cnt == 0) {
                  break;
                }
              }
            }
            // Neuer Code
            else {
              this.openedLoops.offerFirst(i);
            }
            break;
    // restlicher Code
}

Beim Abschluss einer Schleife wird nun einfach auf die Stelle, die als letztes in die LinkedList eingefügt wurde gesprungen. Von dieser Position muss jedoch noch eins abgezogen werden, da sich die Position ja beim nächsten Durchlauf wieder um eben diesen Faktor erhöht, und somit die 0-Überprüfung am Anfang der Schleife übergangen werden würde.

case ']':
  i = this.openedLoops.pollFirst() - 1;
  break;

Bitte beachten Sie, bevor Sie sich der Zusammenfassung widmen, noch folgende Punkte:

  • Der Code ist nicht perfekt optimiert sondern möglichst verständlich gehalten.
  • Da die Integer Repräsentation der Character Zeichen nur bis zur Zahl 127 mit dem ASCII-Code übereinstimmt, entspricht die Ausgabe des Interpreters den Java-Zeichen, die den auszugebenden Werten zugeordnet sind. Um dies zu umgehen, müsste bspw. ein separierter Java2ASCIIOutputStream eingesetzt werden, der die Java-Repräsentationen in die entsprechenden ASCII-Zeichen umwandelt. Aber dies soll nicht Inhalt dieses Kapitels sein.

Auf der nächsten Seite finden Sie eine Zusammenfassung mitsamt Main-Methode und BrainFuck-Beispiel.


{ 1 } Trackback

  1. Newsletter KW 41 / 2010 | 11. Oktober 2010 um 00:35 | Permalink

    [...] Wer immer mal wissen wollte, wie die Sprache Brainfuck funktioniert, kann diese Lücke selbstverständlich bei uns [...]

Kommentar verfassen

Dein E-Mail wird nicht veröffentlicht oder weitergegeben. Pflichtfelder sind mit * markiert.
*