Compilerbau lernen: von der Grammatik zum Codegenerator

Compilerbau lernen heißt die Pipeline verstehen: Lexer, Parser, Semantik, Zwischencode und Codegenerierung — plus ein Plan für das Praktikum.

Compilerbau lernen: von der Grammatik zum Codegenerator

"Ein Compiler, der eine Sprachkonstruktion vollständig übersetzt, ist mehr wert als sechs halbfertige Phasen."

Du kennst die Phasen aus der Vorlesung: Lexer, Parser, semantische Analyse, Codegenerierung. Und trotzdem sitzt du im Praktikum vor einem Parsergenerator, der einen Shift/Reduce-Konflikt meldet, und weißt nicht, ob das Problem in deiner Grammatik oder in deinem Verständnis liegt. Compilerbau lernen heißt deshalb, zwei Prüfungsformen gleichzeitig zu bedienen: eine Klausur über Theorie und ein Implementierungsprojekt, das keine Teilpunkte für gute Absichten vergibt. Dieser Guide ordnet die Phasen zu einer Pipeline, die du als Ganzes liest, und zeigt dir, wie du das Praktikum neben der Vorlesung planst statt in der letzten Woche.

Die Pipeline als Ganzes: was in welcher Phase passiert

Der häufigste Denkfehler ist, die Phasen als sechs unabhängige Kapitel zu lernen. Sie sind eine Kette: jede Phase bekommt eine Datenstruktur, reichert sie an und gibt sie weiter. Wenn du für jede Phase sagen kannst, was hineingeht und was herauskommt, hast du die halbe Klausur verstanden.

PhaseEingabeAusgabeTypische Fehlermeldung
Lexikalische Analyse (Lexer/Scanner)ZeichenstromTokenstromUnbekanntes Zeichen
Syntaxanalyse (Parser)TokenstromSyntaxbaum (AST)Unerwartetes Token
Semantische AnalyseASTAST + Symboltabelle, typgeprüftUnbekannter Bezeichner, Typfehler
Zwischencode-Erzeugunggeprüfter ASTZwischendarstellung (IR)selten sichtbar
OptimierungIRbesseres IRselten sichtbar
CodegenerierungIRZielcodeRegister erschöpft

Diese Reihenfolge findest du in jedem Standardcurriculum wieder — die Themenliste der Stanford-Veranstaltung CS143 nennt genau diese Kette von der lexikalischen Analyse über Parsing-Theorie, Symboltabellen und Typsysteme bis zu Zwischendarstellungen, Codegenerierung und Optimierung. Lerne die Kette einmal in dieser Richtung und einmal rückwärts: „Woher kommt dieser Registerzugriff?" ist die Frage, mit der mündliche Prüfungen gern anfangen.

Die eine Übung, die sich am meisten lohnt

Nimm einen Ausdruck wie a = b * 2 + c und schreib ihn durch alle sechs Phasen von Hand auf: Tokenliste, Syntaxbaum, Symboltabelleneintrag, Drei-Adress-Code, optimierte Fassung, Zielcode. Eine Seite Papier, eine Stunde Arbeit — und du hast ein Gerüst, an dem du jede spätere Vorlesung aufhängst. Wenn du anschließend merkst, dass dir die Baumstrukturen dahinter fehlen, hol dir die Grundlagen über Bäume und Rekursion aus Algorithmen und Datenstrukturen zurück, bevor du weitermachst.

Grammatiken lesen lernen: LL, LR und warum dein Parser meckert

Hier trennt sich das Modul von der Theoretischen Informatik. Dort beweist du, was eine Sprache ist und was entscheidbar bleibt; hier baust du eine Übersetzung. Die formalen Sprachen sind dasselbe Werkzeug, die Frage ist eine andere: nicht „geht das prinzipiell?", sondern „kann mein Parser das mit einem Token Vorausschau entscheiden?". Wenn dir die Automaten-Grundlagen fehlen, arbeite parallel den Ratgeber zu Beweisen und Automaten in der Theoretischen Informatik durch — die beiden Module stützen sich gegenseitig.

Der praktische Unterschied in zwei Zeilen:

LL (Top-down)LR / LALR (Bottom-up)
Richtungvon der Wurzel zu den Blätternvon den Blättern zur Wurzel
Typische Umsetzungrekursiver Abstieg, oft handgeschriebenTabellen, meist generiert
Stärkelesbarer Code, gute Fehlermeldungenakzeptiert deutlich mehr Grammatiken
SchwächeLinksrekursion muss rausKonflikte sind schwer zu lesen

Shift/Reduce-Konflikte sind eine Aussage, keine Panne

Ein Shift/Reduce-Konflikt bedeutet: in diesem Zustand wären beide Aktionen erlaubt — weiterlesen oder zusammenfassen. Das Standardbeispiel ist das dangling else: Bei verschachtelten if-Anweisungen ohne Klammern ist nicht festgelegt, zu welchem if das else gehört. GNU Bison löst solche Konflikte per Voreinstellung durch Shift auf, was das else an das nähere if bindet — genau die Konvention, die man erwartet. Praktisch heißt das:

  • Lies die Konfliktmeldung, statt sie wegzudrücken. Bison kann Gegenbeispiele erzeugen, die eine Eingabe mit zwei möglichen Ableitungen zeigen. Das ist der schnellste Weg zur Ursache.
  • Unterscheide Ambiguität von Grammatikfehler. Ein Reduce/Reduce-Konflikt deutet oft darauf hin, dass die Grammatik nicht LALR(1) ist — nicht darauf, dass du dich vertippt hast.
  • Erkläre Konflikte, bevor du sie unterdrückst. Eine Deklaration wie %expect schweigt über eine erwartete Anzahl Konflikte. Das ist legitim, wenn du weißt, welche — und riskant, wenn nicht.

Für die Klausur heißt das: Du musst Tabellen von Hand aufbauen können. Dafür sind Karteikarten das passende Werkzeug, weil es um sicheren Abruf geht, nicht um Verstehen: First- und Follow-Mengen, die Bedingung für LL(1), die Auflösungsregeln bei Konflikten. Wenn du deine Vorlesungsfolien dafür nutzt, kannst du daraus mit mit Learnboost Karteikarten aus dem Skript erstellen und die Mengen so lange abfragen, bis sie sitzen.

Semantische Analyse: Symboltabelle und Typprüfung

Die Phase, die in Klausuren unterschätzt wird, weil sie unspektakulär aussieht. Der Parser hat nur geprüft, ob die Form stimmt. Jetzt geht es um Bedeutung: Ist x überhaupt deklariert? In welchem Block? Passt der Typ auf beiden Seiten der Zuweisung?

Drei Dinge musst du sauber können:

  1. Gültigkeitsbereiche als Stapel. Beim Betreten eines Blocks legst du einen Bereich auf den Stapel, beim Verlassen nimmst du ihn herunter. Namensauflösung heißt: von oben nach unten suchen, der erste Treffer gewinnt. Damit erklärst du Verschattung in einem Satz.
  2. Symboltabelle als Vertrag. Zu jedem Bezeichner gehören Typ, Art (Variable, Funktion, Parameter), Gültigkeitsbereich und bei Funktionen die Signatur. Vergisst du ein Feld, merkst du es erst in der Codegenerierung — und suchst dann an der falschen Stelle.
  3. Typregeln als Herleitung. Typprüfung ist Bottom-up am Baum: Die Typen der Kinder bestimmen den Typ des Knotens. Schreib die Regeln für Zuweisung, Operator und Funktionsaufruf einmal als Herleitungsbaum auf — damit beantwortest du einen ganzen Aufgabentyp.

Zwischencode und Optimierung: so viel, wie die Klausur verlangt

Zwischencode löst ein Entkopplungsproblem: Vorne hängt die Quellsprache, hinten die Zielarchitektur, und du willst nicht für jede Kombination einen eigenen Übersetzer bauen. Deshalb übersetzt du erst in eine neutrale Darstellung — klassisch Drei-Adress-Code, in realen Systemen etwa LLVM IR — und erst von dort in Maschinencode.

Bei Optimierungen lohnt sich Beschränkung. Für die Klausur reichen in der Regel die lokalen Verfahren, die du an einem Grundblock von Hand durchführen kannst:

  • Konstantenfaltung: 2 * 3 wird zur Compilezeit zu 6.
  • Gemeinsame Teilausdrücke: derselbe Ausdruck wird einmal berechnet und wiederverwendet.
  • Entfernen toten Codes: was niemand liest, wird nicht berechnet.

Dass die Codegenerierung nicht der schwerste Teil ist, sagt die offizielle LLVM-Einführung selbst: Lexer und Parser zu schreiben sei deutlich mehr Arbeit, als daraus IR zu erzeugen. Nimm das als Planungshinweis — der Aufwand liegt vorn in der Pipeline, nicht hinten. Wie aus dem Zielcode am Ende Takte werden, gehört in die Nachbarveranstaltung; die Brücke dorthin baut der Ratgeber zu Befehlssatz und Pipeline in der Rechnerarchitektur.

Das Praktikum parallel zur Vorlesung planen

Der eigentliche Fehler im Modul ist zeitlich, nicht inhaltlich: Das Implementierungsprojekt wird angefangen, wenn die Vorlesung schon bei der Codegenerierung ist. Dann debuggst du einen Parser, während du Registerzuteilung lernen solltest.

Plane rückwärts vom Abgabetermin, in Phasen statt in Wochen:

  1. Lexer zuerst, und zwar vollständig. Er ist klein, gut testbar und blockiert alles Weitere. Lege dir von Anfang an Testeingaben an.
  2. Grammatik vor Parsercode. Schreib die Grammatik auf, beseitige Linksrekursion und Mehrdeutigkeiten auf dem Papier. Jeder Konflikt, den du hier findest, kostet dich später Stunden weniger.
  3. AST früh festlegen. Die Knotentypen sind die Schnittstelle zu allen späteren Phasen. Änderungen daran strahlen durch das ganze Projekt.
  4. Semantik und Codegenerierung an einem Minimalprogramm. Erst ein Programm mit einer Zuweisung und einer Ausgabe komplett durch die Pipeline bringen, dann die Sprache erweitern. Ein Compiler, der eine Sprachkonstruktion vollständig übersetzt, ist mehr wert als sechs halbfertige Phasen.
  5. Regressionstests ab Tag eins. Jede Beispieleingabe, die einmal funktioniert hat, bleibt im Testordner.

Wenn du die Vorlesung begleitend aufarbeiten willst, hilft es, aus den Folien jeder Woche eine knappe Zusammenfassung und ein paar Prüffragen zu ziehen, statt den Stoff am Semesterende als Block zu lesen. Genau dafür ist Learnboost gebaut: Unterlagen hochladen, Zusammenfassung und Übungsfragen daraus erzeugen, Lücken früh sehen. Und wenn du im ersten Projekt noch mit der Sprache selbst kämpfst, lohnt vorher ein Blick in den Ratgeber zu Programmieren lernen in den ersten zwei Semestern.

Ein Buchtipp, der das Modul greifbar macht

Wenn dir die Vorlesung zu abstrakt bleibt, arbeite parallel ein Kapitel aus „Crafting Interpreters" von Robert Nystrom durch — die vollständige Webausgabe ist kostenlos lesbar. Das Buch baut zwei Implementierungen derselben Sprache: einen baumlaufenden Interpreter in Java und eine Bytecode-Maschine in C. Der zweite Teil zeigt dir die Übersetzung in Bytecode an einem Projekt, das klein genug bleibt, um es komplett zu verstehen.

Compilerbau belohnt genau eine Haltung: ein kleines System vollständig durchziehen, statt sechs Phasen halb zu kennen. Nimm dir die eine Seite Papier mit a = b * 2 + c, arbeite sie durch alle Phasen — und starte das Praktikum in der Woche, in der es ausgegeben wird. Mit Learnboost machst du aus deinem Compilerbau-Skript Karteikarten und Übungsfragen und gehst mit abgefragtem Wissen in die Klausur statt mit gelesenen Folien.

Häufig gestellte Fragen (FAQ):

Warum gilt Compilerbau als so anspruchsvolles Modul?

Weil zwei Prüfungsformen gleichzeitig laufen: eine Theorieklausur über Grammatiken, Parsing und Codeerzeugung und ein Implementierungsprojekt, das nur zählt, wenn es läuft. Wer beides getrennt angeht, lernt zweimal. Wer die Phasen als eine Pipeline versteht, nutzt denselben Stoff für Klausur und Praktikum.

Reicht es, LL(1) zu verstehen, oder brauche ich auch LR?

Für das Praktikum kommst du mit rekursivem Abstieg und damit LL(1) oft durch. Für die Klausur brauchst du beide Richtungen, weil LR und LALR deutlich mehr Grammatiken akzeptieren und Konfliktaufgaben ein Standardformat sind. Baue die Tabellen mindestens einmal von Hand auf.

Handgeschriebener Parser oder Parsergenerator im Praktikum?

Das gibt in der Regel die Aufgabenstellung vor. Ist es dir freigestellt, ist ein handgeschriebener rekursiver Abstieg leichter zu debuggen und liefert bessere Fehlermeldungen, ein Generator nimmt dir die Tabellenarbeit ab. Entscheide früh und bleibe dabei — ein Wechsel mitten im Projekt kostet die meiste Zeit.

Was bedeutet ein Shift/Reduce-Konflikt konkret?

Der Parser könnte in diesem Zustand sowohl weiterlesen als auch die bisherigen Symbole zu einer Regel zusammenfassen — beides wäre erlaubt. Das klassische Beispiel ist das dangling else bei verschachtelten if-Anweisungen. GNU Bison entscheidet sich per Voreinstellung für Shift und bindet das else damit an das nähere if.

Wie viel Optimierung muss ich für die Klausur beherrschen?

Meist die lokalen Verfahren, die du an einem Grundblock von Hand durchrechnen kannst: Konstantenfaltung, gemeinsame Teilausdrücke und das Entfernen toten Codes. Globale Analysen und Registerzuteilung werden häufig nur im Prinzip geprüft. Richte dich nach den Altklausuren deines Lehrstuhls.