Willst du einen Compiler bauen? Dann musst du nur diese zwei Aufsätze lesen (2008)

• Die meisten Compiler-Lehrbücher sind theoriezentriert und sehr umfangreich, was es Einsteigern erschwert, einen tatsächlich funktionierenden Compiler zu implementieren
• Als praktisches Material, das dieses Problem überwindet, wird die Reihe Jack Crenshaws „Let’s Build a Compiler!“ vorgestellt, die einen kompakten Pascal-Compiler mit Single-Pass-Struktur behandelt
• Das Tutorial unterstützt experimentelles Lernen durch die Kombination von Parsing und Codegenerierung, minimale Optimierung sowie Versionen in C und Forth
• Der zweite Text, der Aufsatz „A Nanopass Framework for Compiler Education“, stellt eine modulare Compiler-Architektur vor, die aus zahlreichen einfachen Transformationen (Passes) besteht
• Erst nachdem man mit diesen beiden Materialien praktische Implementierungserfahrung gesammelt hat, kann man bei Bedarf zur Vertiefung auf klassische Lehrbücher (Dragon Book) zurückgreifen

---

Die Realität des Compiler-Lernens und zwei zentrale Aufsätze

• Es wird kritisiert, dass bestehende Compiler-Fachbücher zu umfangreich und schwer zugänglich sind, sodass Anfänger nur schwer einen tatsächlich lauffähigen Compiler schreiben können
  • Die meisten Bücher behandeln riesige Themenfelder wie reguläre Ausdrücke, Grammatiken und Theorie, ohne einen praktischen Einstiegspunkt zu bieten
  • Dadurch entstehen Missverständnisse und Mythen wie „Compiler sind schwierig“
• Als repräsentatives Material, das diese Vorstellung aufbricht, wird die Reihe Jack Crenshaws „Let’s Build a Compiler!“ vorgestellt
  • Dieses 1988 begonnene Tutorial behandelt einen Single-Pass-Compiler auf dem Niveau von Turbo Pascal
  • Die Struktur kombiniert Parsing und Codegenerierung und führt nur minimale Optimierungen durch
  • Ursprünglich wurde es in Pascal geschrieben; später entstanden auch eine C-Version und eine Forth-Übersetzung
  • Die Forth-Version erleichtert aufgrund der interaktiven Spracheigenschaften Experimente und das Verständnis
• Eine Grenze der Crenshaw-Reihe besteht darin, dass es keine interne Programmdarstellung (Abstract Syntax Tree, AST) gibt
  • In Pascal wurde dies ausgelassen, weil die Arbeit mit Bäumen dort kompliziert ist; in Python, Ruby, Erlang, Haskell, Lisp und anderen Hochsprachen lässt es sich jedoch leicht umsetzen
  • Diese Sprachen wurden von Grund auf für die Manipulation von Baumdatenstrukturen entworfen
• Als zweites empfohlenes Material wird der Aufsatz von Sarkar, Waddell und Dybvig genannt: „A Nanopass Framework for Compiler Education“
  • Die Kernidee lautet, dass ein Compiler eine Folge von Prozessen ist, die interne Programmdarstellungen schrittweise transformieren
  • Vorgeschlagen wird eine Struktur aus Dutzenden bis Hunderten einfacher Transformationen (Passes)
  • Jede Transformation soll so einfach wie möglich bleiben und Kopplung zwischen den Transformationen vermeiden
  • Das Framework definiert Ein- und Ausgaben jedes Passes explizit
  • Die Implementierungssprache ist Scheme; die Prüfung erfolgt zur Laufzeit auf Basis dynamischer Typisierung
• Nachdem man mit diesen beiden Materialien tatsächlich einen Compiler geschrieben hat, kann man bei Bedarf mit klassischen Lehrbüchern wie dem Dragon Book weiter vertiefen
  • Doch schon diese beiden Materialien reichen aus, um ausreichend praktische Erfahrung beim Bau von Compilern zu sammeln

[GN⁺]

Hacker-News-Kommentare

• Donald Knuths The Art of Computer Programming wird noch immer geschrieben, und inzwischen ist es eher unwahrscheinlich, dass es überhaupt noch das Thema Compiler behandeln wird
  Ich stimme der Behauptung des Autors nicht zu. Kapitel 2 des Dragon Book (von Aho et al.) ist auch für sich allein gelesen ein in sich abgeschlossenes Einführungsbuch in Compiler
  Ein weiteres hervorragendes Einführungsbuch ist Niklaus Wirths Compilers, das auf nicht einmal 100 Seiten den Quellcode eines vollständigen Compilers und klare Erklärungen enthält
  Mit diesen beiden Büchern habe ich in der Oberstufe genug gelernt, um selbst einen Compiler zu bauen

  • Das Dragon Book ist großartig, aber als Einsteigerbuch ungeeignet. Ich wäre wegen dieses Buchs auch fast von Compilern abgeschreckt worden
    Ich finde, ein praxisorientiertes Buch, das den tatsächlichen Bau eines Compilers Schritt für Schritt begleitet, ist viel besser
    Referenzmaterial ist unter diesem Link zusammengestellt
  • Das Dragon Book ist Parsing-zentriert, daher würde ich es nicht empfehlen, wenn man sich für Backend oder Optimierung interessiert
    In der 2. Auflage wurde Datenflussanalyse ergänzt, aber die SSA-Form (Static Single Assignment), ein Kern moderner Compiler wie GCC oder LLVM, wird auf genau einer Seite behandelt
    Wer ein modernes Backend bauen will, muss SSA-Theorie separat lernen
  • Niklaus Wirths Compilers kann man hier lesen
  • Laut Knuths Website ist weiterhin geplant, Compiler-Technik in Volume 7 zu behandeln
    Siehe die offizielle TAOCP-Seite
  • Dass Knuth einen zweiten Vornamen hat, habe ich zum ersten Mal erfahren, aber im Artikel muss man ihn nicht unbedingt nennen

• Abdulaziz Ghuloums Arbeit An Incremental Approach to Compiler Construction
  räumt mit der Vorstellung auf, „Compiler seien so etwas wie Magie“, und zeigt, dass man Compiler genauso leicht wie Interpreter bauen kann
  Sie beschreibt detailliert, wie man schrittweise einen Compiler aufbaut, der große Teile der Sprache Scheme unterstützt und Assembler für Intel x86 erzeugt

  • Ebenfalls sehr gut ist Nora Sandlers Writing a C Compiler, das von dieser Arbeit inspiriert wurde
  • Es gibt auch eine Version mit Tests, in der Nada Amin Aziz’ Ansatz umgesetzt hat

• In jüngerer Zeit hat sich die Compiler-Technik mit Meta-Compilern, Adaptive Compilation und JIT-Compilern stark weiterentwickelt
  Alan Kays Forschungsgruppe VPRI befasst sich mit dem Komplexitätsproblem
  Weiterführendes Material: Ometa-Paper, Video zu Adaptive Compilation, Vortrag von Alan Kay

• Ich habe einmal einen guten Rat zum Lesen von Büchern gehört — Bücher sind wie RAM per Random Access zugänglich
  Wenn man nur die benötigten Teile liest, wirken selbst dicke Bücher weniger abschreckend
  Das funktioniert allerdings nicht, wenn man gar nicht weiß, was man nicht weiß. Deshalb sind leichte Einführungen so wichtig

  • Die meisten Bücher enthalten viel zu viele unnötige Details, die man am Ende überspringt. Fachbücher dagegen sind oft so schwer, dass man für einen Abschnitt Stunden zum Verstehen braucht
  • Ich habe das Gefühl, dass ich wenig aus einem Buch mitnehme, wenn ich es nicht vollständig lese. Heutzutage wandern viele gute Nachschlagewerke ins Internet
  • Einen großen Teil meiner technischen Bücher nutze ich als Referenz für konkrete Fragen

• Heutzutage wird oft Crafting Interpreters empfohlen
  Der Nanopass-Paper-Link ist kaputt

  • Selbst bei „Compiler-Büchern“ ist die behandelte Bandbreite sehr unterschiedlich, sodass sie oft nicht zu dem passt, was ich eigentlich suche
    Deshalb habe ich einen Spickzettel erstellt, der die Kernaussagen von Crafting Interpreters zusammenfasst
    Das Buch ist nicht bloß ein Handbuch, sondern ein erfahrungsorientiertes Lehrbuch, in dem auch der Spaß des Autors an Dingen wie dem Visitor-Pattern steckt
  • Crafting Interpreters ist hervorragend, aber mit einem Begleitband zu Typsystemen, Optimierung und Linking wäre es perfekt
  • Es ist wirklich ein großartiges Buch fürs Selbststudium
  • Ich habe es während des Studiums komplett gelesen, während ich auf Vorlesungen gewartet habe. Nanopass habe ich noch nicht ausprobiert, will es aber über einen anderen Link versuchen
  • Das Nanopass-Paper ist in diesem GitHub-Repository archiviert

• In letzter Zeit baue ich zum Spaß einen Toy-Compiler
  Statt komplexer Parsing-Theorie oder DSLs verwende ich den Megaparsec Parser-Combiner
  Die Parsing-Logik ist klar, leicht wiederverwendbar, und der Aufwand der traditionellen Trennung von Lexer und Parser entfällt

  • Ich halte rekursive Abstiegparser für praktischer als LL/LR-Parsergeneratoren
    Sie haben weniger Bugs, liefern bessere Fehlermeldungen, und die meisten Sprachen wie C# oder Rust nutzen diesen Ansatz ebenfalls
    Tree-sitter ist auch großartig, bringt aber viele Abhängigkeiten mit. Rekursiver Abstieg erlaubt dagegen eine kompakte Implementierung ohne Abhängigkeiten
  • Trotzdem finde ich es besser, die Trennung von Lexer und Parser beizubehalten
    Der Vorteil des Parser-Combiner-Ansatzes ist, dass sowohl Lexer als auch Parser als derselbe Parser-Typ behandelt werden können
    Damit lassen sich Whitespace-Behandlung und Tokenisierungsprobleme sauber lösen

• Das früher tote Nanopass-Paper ist hier zu finden

  • Im Cambridge Journal of Functional Programming gibt es ebenfalls einschlägige Arbeiten
  • Die offizielle Website ist nanopass.org

• Mir hat ein Artikel über den Tiny-Pascal-Compiler im BYTE Magazine von 1978 Compiler beigebracht
  Optimierung habe ich in einem Sommerkurs von Ullman und Hennessy in Stanford gelernt
  Der Codegenerator war ein eigener, selbst entwickelter Ansatz
  Das Dragon Book besitze ich, habe es aber nie wirklich gelesen

  • Das betreffende BYTE Magazine kann man auf archive.org lesen

• Der Kern des Nanopass-Ansatzes ist nicht die Anzahl der Passes, sondern dass für jeden Pass explizite Ein- und Ausgabesprachen definiert werden
  Dieses strukturierte Denken hilft dabei, viele Bugs schon vor der Ausführung zu erkennen
  Crenshaws Tutorial ist ebenfalls hervorragend, aber dieses Management sprachlicher Invarianten macht den Unterschied aus, wenn man wirklich skalierbare Compiler bauen will

• Aus meiner Zeit an der UC Irvine erinnere ich mich daran, im Kurs CS241 von Professor Michael Franz, einem Schüler von Niklaus Wirth, einen optimierenden Compiler implementiert zu haben
  Die Aufgabe bestand darin, Bytecode für eine virtuelle Maschine namens DLX zu erzeugen
  Verwandtes Material findet sich in dieser Beschreibung der DLX-Architektur sowie in dieser Referenzgrafik zum Registerallokationsalgorithmus