Brainfuck-Compiler in Brainfuck

[oreissig]

Vorweg: wers nicht kennt: Brainfuck ? Wikipedia (one programming language to rule em all!!!!!111)

So, um mal das Niveau in ungeahnte Höhen zu katapultieren, dachte ich mir, dass ich doch mein tolles Brainfuck-Projekt von vor kurzem mal präsentieren könnte. Der Titel ist etwas verwirrend, es ist kein echter compiler, sondern nur ein to-C-Converter. hatte mal überlegt, zumindest x86-assembercode zu erzeugen, aber eigentlich find ich das ganz praktisch, da meine Hauptentwicklungsmaschine der Jornada 720 ist und ich von ARM-Assembler absolut 0 ahnung hab (x86 hab ich zumindest vor urzeiten mal ein helloworld gemacht).

Also here we go:

Spoiler anzeigen

Code:

header

# >+++++[<+++++++>-]<.
i >>>++++++++++[<++++++++++>-]<+++++.
n +++++.
c >+++[<--->-]<--.
l >+++[<+++>-]<.
u >+++[<+++>-]<.
d >++++[<---->-]<-.
e +.
  <<---.
( >++++[<+++++++>-]<.
s >>>+++[<++++>-]<++.
t +.
d >++++[<---->-]<.
i +++++.
o ++++++.
_ <+++[<---->-]<--.
h >>-------.
) <++++[<++++>-]<.
_ >>>>>+++[<+++>-]<+.

pointer
i <<+.
n +++++.
t ++++++.
  <++++[<------->-]<--.
p >>----.
; <++++[<+++++++>-]<-.
_ >>>>.

array
c <+++[<---->-]<-.
h +++++.
a -------.
r >++++[<++++>-]<+.
  <+++++[<----->-]<--.
a >>>++++[<---->-]<-.
( ------.
4 <++++[<+++++>-]<.
0 ----.
9 >+++[<+++>-]<.
6 ---.
) >>++.
; <<+++++.
_ >>>>.

main
i <+++[<++++>-]<.
n +++++.
t ++++++.
  <+++++[<----->-]<--.
m >>-------.
a >+++[<---->-]<.
i ++++++++.
n +++++.
( <<++++++++.
) +.
{ >>>+++[<++++>-]<+.
_ >>.



befehlsdecodierung

flags setzen
>>>>>>>>>>>>>+ (endflag)

große Schleife
[
<+<+<+<+<+<+<+<+<+<<<
,

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

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

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

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

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

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

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

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

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



assemblierung

plus
>>[<<<<<<[-]
a >++++++++[<++++++++++++>-]<+.
( ------.
p >++++[<+++++>-]<+.
) >+++[<------>-]<-.
_ >+++++++[<------->-]<-.
_ .
; >++++[<++++>-]<.
_ >>.
>>>>-]

minus
>[<<<<<<<[-]
a >++++++++[<++++++++++++>-]<+.
( ------.
p >++++[<+++++>-]<+.
) >+++[<------>-]<-.
_ >++++++[<-------->-]<.
_ .
; >+++[<++++>-]<++.
_ >>.
>>>>>-]

right
>[<<<<<<<<[-]
p >++++++++++[<+++++++++++>-]<++.
_ >++++++++[<-------->-]<-----.
_ .
; >++++[<++++>-]<.
_ >>.
>>>>>>-]

left
>[<<<<<<<<<[-]
p >++++++++++[<+++++++++++>-]<++.
_ >++++++++[<-------->-]<---.
_ .
; >+++[<++++>-]<++.
_ >>.
>>>>>>>-]

open
>[<<<<<<<<<<[-]
w >+++++++++[<+++++++++++++>-]<++.
h >+++[<----->-]<.
i +.
l +++.
e -------.
( >++++++[<---------->-]<-.
a >+++++++[<++++++++>-]<+.
( ------.
p >++++[<+++++>-]<+.
) >+++[<------>-]<-.
) >+++++++[<------->-]<---.
( >++++++++[<++++++++++>-]<++.
_ >>.
>>>>>>>>-]

close
>[<<<<<<<<<<<[-]
} >+++++++++++[<+++++++++++>-]<++++.
_ >>.
>>>>>>>>>-]

output
>[<<<<<<<<<<<<[-]
p >++++++++++[<+++++++++++>-]<++.
u +++++.
t -.
c >++++[<---->-]<-.
h +++++.
a -------.
r >++++[<++++>-]<+.
( >++++++++[<--------->-]<--.
a >+++++++[<++++++++>-]<+.
( ------.
p >++++[<+++++>-]<+.
) >++++[<---->-]<---.
) >+++++++[<------->-]<---.
; >+++[<++++++>-]<.
_ >>.
>>>>>>>>>>-]

input
>[<<<<<<<<<<<<<[-]
a >++++++++[<++++++++++++>-]<+.
( ------.
p >++++[<+++++>-]<+.
) >+++[<------>-]<-.
= >++++[<-------->-]<.
g >++++++[<+++++++>-]<.
e --.
t >+++[<+++++>-]<.
c >++++[<---->-]<-.
h +++++.
a -------.
r >++++[<++++>-]<+.
( >++++++++[<--------->-]<--.
) +.
; >+++[<++++++>-]<.
_ >>.
>>>>>>>>>>>-]

ende
>[<<<<<<<<<<<<<<[-]
r >++++++++++[<+++++++++++>-]<++++.
e >+++[<---->-]<-.
t >+++[<+++++>-]<.
u +.
r ---.
n ----.
  >+++++++[<----------->-]<-.
a >++++++++[<++++++++>-]<+.
( ------.
p >++++[<+++++>-]<+.
) >+++[<------>-]<-.
; >++++[<-------->-]<--.
_ >>.
} <++++++[<+++++++++++>-]<.
_ >>.
>>>>>>>>>>>>>-<-]

>]

@

(ob das Forum auch Syntax-Highlightning für Brainfuck könnte? )

Hier mal, um das ding erstmalig zu Compilieren, mein Compiler in C davon. Danach ist der Brainfuck-Compiler (das war mein Ziel) self-hosting

Spoiler anzeigen

Code:

#include <stdio.h>

int main() {
    //header:
    printf("#include <stdio.h>\n");
    printf("int p;\n");
    printf("char a[4096];\n");
    printf("int main(){\n");
    
    //code:
    int c=0;
    while (c != '@') {
        c = getchar();
        switch (c) {
            case '+': printf("a[p]++;\n");
                  break;
            case '-': printf("a[p]--;\n");
                  break;
            case '>': printf("p++;\n");
                  break;
            case '<': printf("p--;\n");
                  break;
            case '[': printf("while(a[p]){\n");
                  break;
            case ']': printf("}\n");
                  break;
            case '.': printf("putchar(a[p]);\n");
                  break;
            case ',': printf("a[p]=getchar();\n");
                  break;
            case '@': printf("return a[p];\n}\n");
        }
    }
}

ich werd mal bisschen kommentieren:
Das Programm besteht aus 3 großen Blöcken:

1. Header erzeugen (also #include blabla...)
2. Befehlskodierung
3. Assemblierung
   

Die letzten beiden sind etwas tricky, hatte als allererste Version (und zur verifikation meines C-Codes) das gleiche in C geschrieben, was einfach nur die 8 instruktionen switcht, problem dabei ist, dass es unter Brainfuck kein "if x=FOO then ..." gibt. die einzige möglichkeit verzweigungen zu machen ist mit den Schleifen, welche quasi "while a != 0 { ... }" sind. Damit könnte man zwar leicht ein "if a != FOO then ..." machen, aber um damit ein "=" erzeugen zu können müsste man 255 solcher abfragen schachteln

Ich habs so gelöst, dass ich ne große Herde Flags gemacht hab, ich sag pro-forma, dass alle befehle abzubilden sind (jeweils eine Zelle aufm Band, 1 dort heißt "der aktuelle Befehl ist +/-/...", 0 eben nicht) und geh dann der reihe nach alle möglichkeiten durch und entferne die flags, deren befehle nicht zutreffen, quasi "if x != '+' then entferne_flag('+')".
Diese If-Abfrage ist etwas overkill, aber eigentlich zu verstehen. pro befehl kopiert er den Wert der aktuellen Zelle erst in die Zelle rechts davon (zuerst verschiebt ers in die beiden zellen rechts von sich, dann verschiebt ers von der 2. in die ursprüngliche zurück. anders kann man nicht kopieren), dann zieht er den FOO-wert von der kopie ab und schaut dann, ob das ergebnis 0 ist (d.h. x=FOO), wenn das nicht so ist wird die Schleife ausgeführt und das Flag entfernt

Das war die Befehlskodierung, Assemblierung war dann easy, musste nur eben auf den Flags langgehen und die entsprechenden Ausgaben in nen Schleifenblock setzen

Am Ende das "@" hat übrigens eine wichtige Funktion, nämlich zeigt es das Programmende an. Diese "Befehlserweiterung" musste ich vornehmen, da Brainfuck ja nicht merkt, wenn das Programm zuende ist. Wenn man einfach nur Quellcode reinpiped und der zuende ist wird er sonst einfach warten, bis mehr Zeichen kommen (die aber ja nicht kommen, da die datei zuende ist).

Also, ihr seid herzlich aufgerufen, dran rumzubasteln, macht mit dem Quellcode was ihr wollt, aber ich würde mich freuen, wenn ihr mir davon berichtet.
Wer möchte könnte ja das Ding so modifizieren, dass er x86-Assemblercode erzeugt oder so, fänd ich jedenfalls cool.


Anmerkungen:

• zum Compilieren einfach folgendes machen (c-basierter compiler genauso)
  Code:
  

  ./bfc < $1.bf > $1.c
gcc $1.c -o $1 -Os
• irgendwie muss man die erzeugten Programme zumindest mit -O1 compilieren lassen, ohne optimierung lief zumindest der Compiler irgendwie nicht (keine große einschränkung, aber mal genannt werden sollte es)
• hatte überlegt, wie man das ding weiter optimieren kann und mir kamen spontan 2 Ideen:
  

1. sobald man einen Befehl "erkannt" hat, kann man die Dekodierung theoretisch abbrechen und direkt zur assemblierung springen. Ganz ehrlich: Wär cool, aber ich hab keinen Dunst wie man das annähernd gut umsetzen könnte, das würde das Programm wahrscheinlich doppelt so lang machen!
2. man könnte von allen ASCII-Werten der Befehle den kleinsten nehmen, und diesen direkt nach dem Einlesen "," schon abziehen, damit würde man später bei der Dekodierung sparen 8x diesen immer gleichen Wert subtrahieren zu müssen. Das wäre umsetzbar, hab ich aber nicht gemacht, denn:
   

• Man mags kaum glauben, das programm ist overkill und reduntantes rechnen³ (allein pro stelle 9x den wert kopieren und die befehlsoffsets abziehen, und der compiler selbst hat 3877 stellen!), aber er ist echt schnell! Ich habs ja bei mir aufm 206MHz StrongARM laufen (laut nbench etwas schneller alsn 90er P1) und das self-hosten des compilers dauert keine sekunde, gcc danach dauert um ein vielfaches länger
  

EDIT: hier mal noch ein kleines Programm zum testen, gibt alle ASCII-Zeichen und danach einen Zeilenumbruch aus:

Code:

+[.+]
++++++++++.@

[gandro]

Wow!

Das rockt ja mal derbe
Habs jetzt noch nicht all zu genau angeschaut, fürn Hirnfick ist es mir noch zu früh, aber werd ich noch. Respekt!

[Dirk]

Jetzt meien ich mal das wir das schon mal hatten... und ihr beiden habt daran schon teilgenommen:
http://www.winhistory-forum.net/coding/1...lcode.html

Aber das wars irgendwie nicht. ich kenne brainfuck. nen dozent hat das mal vorgestellt. ist einfach abartig...

[klemmi]

coole Aktion. ich habs mir nun selbst auch noch nicht so genau angeschaut, aber sieht echt nteressant aus!

Ich werde in nem blauen Moment drauf zurückkommen!

[huttERic]

Ich missbrauche den Thread hier mal
(Wenns nicht passt, soll ein Mod den Beitrag ausgliedern)

Ich habe mal kurz einen Brainfuck to .NET 2.0 Compiler geschrieben. Ist eigentlich selbsterklärend das Teil.
bsc quelldatei zieldatei[.exe wird angehängt]
bsc.exe (20,48 KB)
Vielleicht hat ja jemand Interesse dran...