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

"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.
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.
| Phase | Eingabe | Ausgabe | Typische Fehlermeldung |
|---|---|---|---|
| Lexikalische Analyse (Lexer/Scanner) | Zeichenstrom | Tokenstrom | Unbekanntes Zeichen |
| Syntaxanalyse (Parser) | Tokenstrom | Syntaxbaum (AST) | Unerwartetes Token |
| Semantische Analyse | AST | AST + Symboltabelle, typgeprüft | Unbekannter Bezeichner, Typfehler |
| Zwischencode-Erzeugung | geprüfter AST | Zwischendarstellung (IR) | selten sichtbar |
| Optimierung | IR | besseres IR | selten sichtbar |
| Codegenerierung | IR | Zielcode | Register 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.
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.
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) | |
|---|---|---|
| Richtung | von der Wurzel zu den Blättern | von den Blättern zur Wurzel |
| Typische Umsetzung | rekursiver Abstieg, oft handgeschrieben | Tabellen, meist generiert |
| Stärke | lesbarer Code, gute Fehlermeldungen | akzeptiert deutlich mehr Grammatiken |
| Schwäche | Linksrekursion muss raus | Konflikte sind schwer zu lesen |
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:
%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.
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:
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:
2 * 3 wird zur Compilezeit zu 6.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.
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:
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.
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.
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.
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.
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.
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.
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.