Let’s Build a Compiler im Rückblick

• Jack Crenshaws „Let’s Build a Compiler“-Tutorial, das zwischen 1988 und 1995 veröffentlicht wurde, wurde in Python und WebAssembly nachgebaut.
• Das Original nutzte Pascal und Motorola 68000-Assembler, doch diese Umsetzung überführt es in Code, der in einer modernen Umgebung ausführbar ist.
• Kern des Tutorials ist es, einen rekursiven Abwärts-Parser (recursive-descent parser) selbst zu implementieren und schon in frühen Phasen echten Assembler-Code zu erzeugen.
• Crenshaws Ansatz nutzt syntax-direktierte Übersetzung (syntax-directed translation), zeigt dabei aber Grenzen bei der Typverarbeitung.
• Diese Neuimplementierung ist deshalb bedeutsam, weil das klassische Tutorial in einer Form neu aufgebaut wurde, in der moderne Entwickler es selbst ausführen und ausprobieren können.

---

Hintergrund des klassischen Tutorials

• Jack Crenshaws „Let’s Build a Compiler“ ist ein Einsteiger-Tutorial zur Compiler-Entwicklung, das zwischen 1988 und 1995 erschien und bis heute häufig genannt wird.
  • Die Originalfassung war in Pascal verfasst und erzeugte Motorola 68000-Assemblercode.
  • Auch 2025 wird es, 35 Jahre später, weiterhin regelmäßig auf Plattformen wie Hacker News diskutiert.
• Der Autor ist diesem Tutorial erstmals 2003 begegnet und wurde stark beeindruckt; 2025 hat er es auf Python und WebAssembly übertragen.

Neuimplementierung mit Python und WebAssembly

• Er beschränkte sich nicht aufs Lesen, sondern implementierte den Tutorial-Compiler in Python und so, dass er WebAssembly (WASM) ausgibt.
• Das Ergebnis ist im GitHub-Repository (eliben/letsbuildacompiler) veröffentlicht.
  • In der Datei TUTORIAL.md wird erklärt, wie jeder Teil des Originals auf Python-Code abgebildet wird.
  • Leser können den Original-Tutorialtext verfolgen und dabei direkt lauffähigen Code ausprobieren.

KISS-Sprachbeispiel und WASM-Ausgabe

• Es werden die Ergebnisse der Kompilierung eines Beispielprogramms in der von Crenshaw entworfenen KISS-Sprache mit dem Python-Compiler gezeigt.
  • Das Beispiel enthält procedure, while-Schleifen sowie Wert- und Referenzübergabe.
• Der ausgegebene WASM-Text enthält Logik zur Behandlung von by-reference Parameters, wobei kaum Optimierungen durchgeführt wurden.
• Der Teil, in dem die globale Variable X implizit aus main zurückgegeben wird, dient der Testbequemlichkeit.
• Der erzeugte WASM-Code wird für Tests eingesetzt, bei denen erwartete Ergebnisse durch tatsächliche Ausführung verifiziert werden.

Stärken des Tutorials

• Crenshaws Tutorial baut schrittweise einen rekursiven Abwärts-Parser auf und legt den Fokus auf eine funktionierende Codeerzeugung statt auf komplexe Theorie.
  • Damals galten lex und yacc als Standard, doch die Schlichtheit und Klarheit eines selbstgeschriebenen Parsers hatten großen Einfluss.
  • In den folgenden 20 Jahren entwickelte der Autor eine Vorliebe für handgeschriebene rekursive Abwärts-Parser.
• Während die meisten Lehrinhalte seinerzeit auf Parsing fokussiert waren, behandelt Crenshaw bereits früh die Codeerzeugung in den ersten Phasen.

Grenzen und Verbesserungspotenzial

• Das Tutorial verwendet syntax-direktierte Übersetzung und erzeugt Code direkt während des Parsings.
  • Dieser Ansatz ist für das Lernen nützlich, hat aber die Grenze, dass Typinformationen vorher nicht bekannt sind und dadurch Optimierung schwierig wird.
• Besonders ab dem 14. Teil mit der Einführung von Typen wird deutlich, dass ein strukturierterer Ansatz mit Zwischencode (IR) oder AST notwendig ist.
• Warum Crenshaw das Tutorial nach Teil 14 abbrach, ist nicht dokumentiert, doch es wird die Möglichkeit erwähnt, dass dies mit dieser Grenze zusammenhängt.
• Der Autor hält es für sinnvoller, ab diesem Wendepunkt erst einen AST zu erzeugen und danach eine Typprüfung sowie Codegenerierung vorzunehmen.

Fazit

• Das Original-Tutorial bleibt ein exzellenter Einstieg in den Compilerbau mit ausgezeichneter Lesbarkeit und Praxisnähe.
• Diese Python- und WASM-Version ergänzt es so, dass heutige Entwickler ohne veraltete Technik lernen können.
• Über das GitHub-Repository ist es für alle erprobbarkeit und stellt eine moderne Neuinterpretation dar, die ein direktes Erleben der Compilerstruktur ermöglicht.

[GN⁺]

Hacker-News-Kommentare

• Mir gefällt das Tutorial, weil es sich nicht in Frontend-Details verliert und von Anfang an direkt funktionierenden Assembler-Code erzeugt.
  Besonders reizvoll ist der Ansatz wie bei Ghuloum, bei dem man von einem sehr kleinen Teil der Sprache ausgeht, das Ganze aufbaut und schrittweise erweitert.
  Ein gutes Buch, das ich kürzlich entdeckt habe, ist dieser Link; auch wenn C und x86 für Einsteiger nicht unbedingt die optimalen Ziele sind, war es großartiges Material für den ersten Compiler.
  Zur Referenz: Ghuloums Paper gibt es hier.

  • Das ist ein seltener Fall, aber ich finde, dass ein akademischer Ansatz hier tatsächlich ein Beispiel dafür ist, was nicht zur Praxis passt.
    Früher war Parsing der wichtigste Teil, deshalb waren Curricula entsprechend aufgebaut, aber heute ist wichtiger, wie man Sprachfeatures implementiert.
    Selbst wenn man einen Compiler selbst baut, leben wir inzwischen in einer Zeit, in der „Claude, schreib mir einen Recursive-Descent-Parser für diese Grammatik“ fast im ersten Versuch ein brauchbares Ergebnis liefert.
  • Hier spürt man den Unterschied zwischen akademischen Forschern und Entwicklern in der Praxis.
    Die akademische Welt denkt eher in Schichten (layers), Praktiker eher in Pipelines (pipes).
    Der Schichten-Ansatz liefert baubaren Code, ist aber schwer auszuführen; der Pipeline-Ansatz lässt sich leicht ausführen, ist dafür schwächer strukturiert.
    Entscheidend ist letztlich, die Entwicklung in minimal ausführbare Einheiten zu zerlegen.

• Ich finde, dieser Text trifft den Kern wirklich sehr gut.
  Ich interessierte mich schon vor dem Studium für Compiler, und dieses Material war die zugänglichste Einführung, die ich gefunden habe.
  Als ich mit 17 selbst einen Recursive-Descent-Parser gebaut habe, wurde mir klar, dass selbst komplex wirkende Probleme einfach werden, wenn man sie in die richtigen Primitiven zerlegt.

  • „Ein Problem in die richtigen Primitiven zu zerlegen“ ist der eigentliche Kern des Programmierens.
    Es gibt viel Material zu Algorithmen, aber wenig dazu, wie man Probleme über geeignete Primitiven angeht.
  • Recursive Descent ist nicht nur eine Methode, Parser zu bauen, sondern auch eine Lehre für Programmdesign.
    Früher waren tabellengesteuerte Parser wie yacc verbreitet, heute ist Recursive Descent praktischer und flexibler.
    Durch LLM-basierte Codegenerierung ist dieser Ansatz noch einfacher geworden.
    Bei Toy-Compilern zum Lernen kann man AST, IR und Optimierungen weglassen und direkt zur Codegenerierung gehen; das ist immer noch sehr lehrreich.
    Als wir früher im Unternehmen ein Testwerkzeug gebaut haben, das eine Teilmenge von C unterstützte, ließ der Parser statt Code zu erzeugen ausführbare Datenstrukturen zurückgeben.
    Eine ForLoopStatement-Klasse enthielt zum Beispiel testExpression und rief diese dann direkt in einer Execute()-Methode auf.
  • Niklaus Wirths Paper von 1971, Program Development by Stepwise Refinement, ist ein klassischer Text, der diese Denkweise sehr früh formuliert hat.
    Es ist auch ein wichtiges Paper, das in Fred Brooks’ The Mythical Man-Month erwähnt wird.
  • Wenn ich heute Parsing brauche, greife ich fast immer zu Parser Combinators.
    Das ist konzeptionell einfach sehr natürlich und elegant.

• Die Erklärung, dass Jack Crenshaws Tutorial den Ansatz der syntax-directed translation verwendet, fand ich interessant.
  Ich frage mich, ob das einfach nur einen Single-Pass-Compiler meint oder ob es etwas Spezifischeres ist.
  Bei statisch typisierten Sprachen verstehe ich, dass typbasierte Optimierung schwierig ist, aber ich würde gern wissen, ob es auch Einschränkungen bei der Typprüfung selbst gibt.

  • Wenn die Zielsprache einer Define-before-use-Regel folgt und keine komplexe Typinferenz hat, sind typbasierte Optimierungen oder Constant Folding durchaus möglich.
    Aber ohne IR sind fortgeschrittene Optimierungen wie LICM, CSE oder GVN unmöglich.
    Persönlich bevorzuge ich eine 2-Pass-Kompilierung auf Funktionsebene — im ersten Durchlauf wird IR erzeugt, danach sofort Code generiert und der Zustand verworfen, was schnelle und effiziente Ergebnisse liefert.
  • syntax-directed translation ist ein etwas konkreterer Begriff und bedeutet, dass beim Lesen des Quellcodes unmittelbar Code erzeugt wird.
    Auch ein Single-Pass-Compiler kann die Phasen trennen und die Codegenerierung erst ganz am Ende ausführen.

• Crenshaws Tutorial reicht nicht bis zu einem wirklich praktischen Niveau, aber wenn man es um die Technik des precedence climbing erweitert, wird es deutlich nützlicher.
  Ein guter Artikel dazu ist dieser Link.

• Ich habe mir den Thread zu „Let’s Build a Compiler“ noch einmal angesehen.
  Von 2007 bis 2023 gab es mehrere Einträge auf HN.
  Besonders das Interview mit Jack Crenshaw war sehr lesenswert, auch wenn es dort keine Kommentare gab.

  • Der vierte Link ist nicht Crenshaws Text, sondern ein anderer Artikel mit demselben Titel.
  • Das Crenshaw-Interview war wirklich gut.

• Kleine Eigenwerbung für ein eigenes Projekt: cwerg.org
  Es verwendet Python und Recursive-Descent-Parsing und trennt Frontend und Backend über ein IR.
  Es erzeugt ELF-Binaries für x86 und ARM und zielt auf reale Nutzbarkeit ab.
  Allerdings ist es komplex und nicht im Tutorial-Stil gehalten.

• Ich erinnere mich noch daran, wie ich Jack Crenshaws Tutorial damals in der USENET-Newsgroup comp.compilers kennengelernt habe.
  Übrigens ist die Gruppe noch immer aktiv.

• Für einen modernen Compiler-Ansatz empfehle ich diesen Blogpost von Cornell.

  • Dank LLVM ist Compilerbau erstaunlich einfach geworden.
    Jedes Mal, wenn ich es benutze, fühlt es sich an, als würde ich nur noch ein paar Steine oben auf eine Pyramide legen.
  • Aber LLVM ist ein indirekter Ansatz und hat Grenzen.
    Sprachen, die LLVM als Backend verwenden, haben gemeinsam, dass sie langsam kompilieren.
    Zig hat das erkannt und entwickelt ein eigenes Backend, während Rust weiterhin an langsame Kompilierung gebunden ist.
    LLVM vermittelt die Illusion, Komplexität garantiere Qualität, und ich halte es für eine Technologie, die die Autonomie von Entwicklern schwächt.
    Das erinnert mich an eine andere populäre Technologie mit ähnlichen Initialen.

• Aus ähnlichen Gründen habe ich auch ein Tutorial namens tiny-optimizing-compiler geschrieben.
  Es ist ein kompaktes Beispiel, das sich nur mit den Zwischenstufen und dem Backend eines Compilers beschäftigt.
  GitHub-Link

  • Das in Lean umzusetzen, wäre wahrscheinlich interessant.

• Als Kind habe ich dieses Tutorial ausgedruckt und überall mit mir herumgetragen, um es zu lesen.
  Es war einfach großartig zu sehen, wie in kurzer Zeit ein Compiler fertig wird.
  Solche Materialien wie Beej’s Guide gehören zu den wertvollsten Dokumenten in der CS-Ausbildung, bekommen aber nicht die Anerkennung, die sie verdienen.