Wie ich meinen eigenen Compiler schrieb: Ein spannendes Projekt mit ToyBASIC

Stablecoins

Das Schreiben eines Compilers ist seit jeher eine der faszinierendsten Herausforderungen in der Welt der Informatik. Ein Compiler übersetzt Quellcode einer Programmiersprache in eine andere Sprache oder Maschinencode, der von Computern ausgeführt werden kann. Obwohl jeder Informatikstudent im Laufe seines Studiums zumindest theoretisch mit Compilern in Berührung kommt, bedeutet das Verständnis der Grundlagen nicht zwangsläufig, dass man je selbst einen Compiler von Anfang bis Ende geschrieben hat. Genau dieses Abenteuer habe ich an einem regnerischen Wochenende unternommen und einen eigenen Compiler für eine vereinfachte Version von BASIC entwickelt, die ich ToyBASIC nenne. Dieses Projekt war nicht nur eine interessante praktische Übung, sondern auch eine nostalgische Reise zurück zu den Anfängen meiner Programmierkarriere.

Der Ursprung und die Motivation für meinen Compiler lagen in der Faszination für BASIC. Als erste Programmiersprache, die ich als Kind lernte, hat BASIC eine besondere emotionale Bedeutung für mich. Die Entscheidung, keinen neuen, komplizierten Sprachentwurf zu wagen, sondern auf einer bewährten und reduzierten Version von BASIC basierend zu arbeiten, sorgte dafür, dass ich das Projekt in vernünftiger Zeit abschließen konnte. TinyBASIC, eine praktische Variante von BASIC, enthielt einige der grundlegenden Programmierkonstrukte, auf denen mein ToyBASIC basierte. Allerdings kürzte ich die Sprache noch weiter ein, indem ich unter anderem den INPUT-Befehl wegließ.

Das Ergebnis war eine sehr minimalistische Sprache, die dennoch das Schreiben einfacher Programme erlaubte. Für die Umsetzung wählte ich Go als Programmiersprache, da ich damit vertraut bin und Go eine saubere Syntax sowie eingebaute Werkzeuge zur Arbeit mit Lexer und Parser bietet. Der Compiler liest ToyBASIC-Code ein, analysiert die Syntax und generiert daraus Go-Quellcode, der anschließend kompiliert und ausgeführt werden kann. So verwandelt sich das Schreiben eines ToyBASIC-Programms in ein echtes, lauffähiges Go-Programm – eine faszinierende Transformation, die ich aus erster Hand kennenlernen wollte. Der Compiler gliedert sich im Wesentlichen in drei Hauptphasen: Lexer, Parser und Compiler.

Zunächst wandelt der Lexer den Text des ToyBASIC-Quellcodes in einzelne Einheiten um, sogenannte Tokens. Diese Tokens repräsentieren die Schlüsselwörter, Operatoren, Zahlen oder Zeichenketten der Sprache. Anstatt diesen komplexen Teil vollständig von Hand zu schreiben, nutzte ich das Tool "nex", welches für Go ein lex-artiges Verhalten bietet und auf übersichtlichen regulären Ausdrücken basiert. So konnte ich Regeln definieren, wie etwa einen Zahlenblock oder einen String zu erkennen ist, ohne jede Zeichenfolge mühsam zu kodieren. Nex erzeugt aus diesen Regeln einen endlichen Automaten, der zuverlässig und effizient den Quellcode zerlegt.

Die nächste Phase heißt Parser. Der Parser nimmt die Sequenz der Tokens und ordnet sie gemäß einer definierten Grammatik in einem abstrakten Syntaxbaum (AST) an. Hierbei kontrolliert der Parser nicht nur, ob der eingegebene Code syntaktisch korrekt ist, sondern baut zugleich eine Baumstruktur auf, die die Bedeutung und die Beziehungen der Programmelemente repräsentiert. Für diesen Schritt setzte ich goyacc ein, eine Go-Variante des bewährten Yacc-Parsers, der bereits seit den 1970er Jahren erfolgreich eingesetzt wird. Die Grammatik beschreibt alle sprachlichen Konstrukte von ToyBASIC, beispielsweise PRINT-Anweisungen, IF-Bedingungen, GOTO und Variablezuweisungen mit LET.

Interessant ist die Art, wie die Grammatik Regeln mit Go-Code verknüpft. Beim Erkennen einer Regel führt der Parser den dazugehörigen Go-Code aus und generiert Knoten in der Baumstruktur. Das Verständnis der Grammatik und der Verknüpfung mit Code war ein entscheidender Schritt, um zu sehen, wie Sprachelemente real in Datensätze übersetzt werden, die weiterverarbeitet werden können. So verwandelt sich beispielsweise eine SIMPLE PRINT-Anweisung aus BASIC zu einem PrintOp-Knoten, der wiederrum die Ausdrucksliste enthält. Ist der Parser fertig, hält man eine vollständig strukturierte Repräsentation des Programms in Form eines syntaxbasierten Baums in den Händen.

Der nächste Schritt ist der eigentliche Compiler im engeren Sinne: der Code-Generator. Er traversiert den Baum und erzeugt für jede Node den entsprechenden Go-Code. Dabei verwendet jede Art von Knoten (PrintOp, LetOp, IfOp etc.) eine eigene Methode namens Generate, die anhand der typischen Funktionalität das passende Go-Äquivalent ausgibt. Für eine PRINT-Anweisung bedeutet das in Go etwa das Schreiben von fmt.

Println mit den generierten Ausgaben der untergeordneten Ausdrucksknoten. Diese modulare Herangehensweise bringt viele Vorteile mit sich. Zum einen ist der Code übersichtlich und gut wartbar, da jede Node sich selbst um ihre Umwandlung kümmert. Zum anderen kann man so leicht weitere Sprachkonstrukte hinzufügen, indem man neue Node-Typen definiert und deren Generierung implementiert. Für ToyBASIC war die Anzahl der Nodes bewusst klein gehalten, um das Projekt überschaubar zu halten, dennoch entsprach das System schon fast einem echten Compilerbau.

Als Demonstration schrieb ich ein einfaches BASIC-Programm, das in ToyBASIC wie folgt aussah: 10 PRINT "Hello, world." 20 LET x = (3 * 2) + 3 30 LET x = x + 1 40 IF x == 10 THEN PRINT "Ten!" 45 PRINT x 50 IF x >= 15 THEN GOTO 70 60 GOTO 30 70 END Nach dem Einlesen und der Verarbeitung dieses Programms generierte der Compiler Go-Code, der anschließend mit dem go run Befehl ausgeführt wurde. Die Ausgabe entsprach genau dem, was ich von BASIC erwartete: eine Ausgabe von „Hello, world.“, anschließend “Ten!”, gefolgt von einer Zählung der Werte von x von 10 bis 15. Die Arbeit an diesem Projekt zeigte mir eindrucksvoll, wie nah theoretische Algorithmen und abstrakte Beschreibung von Sprachen an praktischen und greifbaren Code herankommen können.

Gerade die Kombination bewährter Tools wie nex und goyacc mit eigenem Go-Code für die Code-Generierung bewies sich als effiziente und äußerst ertragreiche Methode, die Komplexität des Compilerbaus zu bändigen. Darüber hinaus war das Projekt auch eine schöne Gelegenheit, mich noch einmal mit den Grundlagen und Feinheiten von Grundbestandteilen eines Compilers vertraut zu machen. Nicht jedes Kapitel in einem Lehrbuch lässt sich so praxisnah und motivierend bearbeiten wie ein eigenes kleines Projekt, das am Ende sogar funktioniert und Freude bringt. Das Beobachten, wie aus Reihen von einzelnen Zeichen ein zusammenhängendes Programm entsteht, das dann in eine ganz andere Sprache übersetzt wird, war ebenso spannend wie lehrreich. Die Wahl von Go als Ziel- und Sprache für die Implementierung des Compilers stellte sich ebenfalls als Vorteil heraus.

Die klar strukturierte Syntax, die Verfügbarkeit von Parsing-Tools und das einfache Schreiben von Code, der generiert wird, erleichterten die Umsetzung spürbar. Zudem unterstützt Go leistungsstarke Pakete wie fmt, wodurch der generierte Code lesbar und wartbar bleibt. Insgesamt war das Projekt mehr als nur ein technisches Experiment. Es war eine Erinnerung daran, dass sich auch in bekannten und scheinbar ausgetretenen Pfaden neue Erfahrungen und Freude entdecken lassen. Man braucht keine riesigen Sprachen oder umfassenden Systeme, um tief in die Welt der Compiler einzutauchen und die essenziellen Mechanismen nachzuempfinden.

Wer selbst mit dem Gedanken spielt, einen Compiler zu schreiben, dem sei geraten, klein anzufangen und sich bewährter Werkzeuge zu bedienen. ToyBASIC ist ein tolles Übungsfeld, da es eine einfache Grammatik hat und dennoch genügend Variation bietet, um das Parsing, die Analyse und Code-Erzeugung auszuprobieren. Dieser Ausflug in den Compilerbau hat meine Wertschätzung für diese fundamentale Disziplin der Informatik auf jeden Fall wiederbelebt. So zeigt sich, dass selbst ein regnerischer Samstag zu einem produktiven und erfreulichen Tag werden kann – nur mit einer guten Idee, etwas Zeit und den richtigen Werkzeugen. Das Lernen hört nie auf, und manchmal macht es am meisten Spaß, wenn man etwas selber schafft.

ToyBASIC lebt nun als einfaches, kleines Projekt auf GitHub weiter, zugänglich für jeden, der sehen möchte, wie ein Compiler in der Praxis funktioniert.