BF Interpreter



  • Hallo,

    Ich möchte einen Interpreter für eine ziemlich leichte Sprache schreiben namens Brainf**k. Sie besteht aus 8 Kommandos : <>+-.,[]

    Wenn der Benutzer jetzt seinen Quellcode eingibt soll je nach command ja etwas ausgeführt werden. Wie könnte ich jetzt einen Algorithmus schreiben welcher je nach command eine Aktion ausführt?

    Ein switch Statement erscheint mir als zu leistungsfressend da BF Programme dazu neigen sehr lang zu sein (Hello World 106 Kommandos (chars)).



  • Wenn es dir auf Geschwindigkeit ankommt, solltest du einen Compiler schreiben. Ansonsten spricht nichts gegen switch. Probiers doch einfach aus, so ein Intepreter ist in 10 Minuten geschrieben.


  • Mod

    Warum machst Du Dir Gedanken über die Geschwindigkeit eines Switch stateents wenn Brainf. sowieso extrem lahm ist als Sprache. Wen interessiert, dass Hello World 106 Zeichen lang ist?

    Als Consolen Programm ist so etwas in 15 Minuten geschrieben.

    Gehe genauso vor wie es die Sprache beschreibt...
    Steht alles in Wikipedia inkl. Links auf Sourcen.

    http://de.wikipedia.org/wiki/Brainfuck



  • Ceno schrieb:

    Ein switch Statement erscheint mir als zu leistungsfressend da BF Programme dazu neigen sehr lang zu sein (Hello World 106 Kommandos (chars)).

    Das ist vollkommen wurst.

    Wenn Du Speed haben willst, musst Du weiter oben ansetzen und den Quellcode optimieren.
    Aus +++++++ wird *p+=7;


    Aus [->+<] wird *(p+1)+=*p;*p=0;
    und so weiter…



  • Irgendwie doof, volkard nur noch als Mitglied zu sehen.



  • EOP schrieb:

    Irgendwie doof, volkard nur noch als Mitglied zu sehen.

    *thx* (und doppelt, daß Du nur dafür die schöne 1000 geopfert hast)
    Das Forum ist nicht mehr so technisch ausgerichtet und geht mit der Zeit. Paßt schon. Ich werde es nicht aufhalten.

    Zur Sache auch wenn nicht für den TO:
    Ich schreibe BF-Programme, die sich wie Forth anfühlen: p sehe ich als Stack und links p sind Daten von aufrufenden Funktionen (die mich nix angehen) und rechts vom p sind Funktionsparameter und jenseits derer nur Nullen. Funktionen fressen ihre Parameter (also nullen sie) und geben dort zurück (legen Ergebnisse auf den Stack). Würde man da mitführen, wo die Nullengrenze ist, könnte man ein

    +++++ zu ++p;*p=5 statt ++p;*p+=5
    machen und es einem Kumpel wie GCC oder clang mal zeigen. Denke, der würde sich mächtig freuen.



  • Ceno schrieb:

    Ein switch Statement erscheint mir als zu leistungsfressend da BF Programme dazu neigen sehr lang zu sein (Hello World 106 Kommandos (chars)).

    Wenn Du einen Interpreter schreiben willst, musst Du ja zwangsläufig den Quellcode Zeichen für Zeichen verarbeiten und den jeweiligen Befehle für das aktuelle Zeichen ausführen. Da wirst Du um eine Fallunterscheidung nicht umher kommen! Und ich würde sagen, dass da ein** switch nicht unbedingt langsamer ist als eine Kaskade von if 's oder gar irgendeine goto **-Konstruktion. Der resultierende Assembler-Code dürfte im Prinzip auf das selbe hinauslaufen.

    Eventuell könnte man auch versuchen, den ASCII-Code des aktuellen BF-Zeichens direkt als Offset in ein Array zu interpretieren. Das Array müsste dann 256 Elemente groß sein (da ein** char **ja einen Wert zwischen 0 und 255 annehmen kann) und Funktions-Zeiger enthalten, die jeweils auf eine Unterfunktion verweisen, welche den entsprechenden BF-Befehl umsetzt. Da BF nur 8 Befehle kennt, wären natürlich nur 8 Elemnte des Arrays wirklich besetzt. Der Rest würde als NOP bzw. "ungültiger Befehl" interpretiert. Die Frage ist bei diesem Ansatz allerdings, ob es sich bei den sehr einfachen BF-Befehlen überhaupt lohnt, da jeweils einen Funktionsaufruf durchzuführen 😕

    typedef void (*op_t)(void);
    static op_t OPERATIONS[256];
    
    void func_inc(void) { /* ... */ }
    void func_dec(void) { /* ... */ }
    
    void init(void)
    {
       OPERATIONS['+'] = &func_inc;
       OPERATIONS['-'] = &func_dec;
       /* ... */
    }
    
    void exec(char *bf_program)
    {
       int pos = 0;
       while(bf_program[pos])
       {
          OPERATIONS[bf_program[pos]]();
          pos++;
       }
    }
    

    Ein anderer Ansatz wäre, den Quellcode zunächst komplett zu parsen und in einen "Zwischencode" zu übersetzten. Anschließend wird dann nur der Zwischencode ausgeführt bzw. interpretiert. Wie der Zwischencode aussieht, kannst Du Dir selbst überlegen. So könnte, zum Beispiel, eine lange Sequenz von** + Zeichen in eine einzige inkrementieren Operation (plus Operand, der angibt, um wie viel inkrementiert werden soll) übersetzt werden. Dann kann der Befehl später bei der Ausführung mit einer einzigen Addition abgehandelt werden - anstatt für jedes + **Zeichen eine separate Addition ausführen zu müssen. Allerdings ist das dann schon eher ein "Just-In-Time Compiler" (JIT) als ein reiner Interpreter 😉


Log in to reply