⚙️ Compiler-Pipeline

Ein Lexer (auch Tokenizer oder Scanner genannt) liest die rohen Quellzeichen einzeln ein und gruppiert sie zu Tokens — den kleinsten bedeutungstragenden Einheiten der Sprache. Für einen einfachen arithmetischen Ausdruck wie „3 + 4 * x“ sind die Tokens NUMBER(3), PLUS, NUMBER(4), STAR, IDENT(x). Jedes Token hat einen Typ und oft einen Wert, und Leerzeichen werden in dieser Phase meist verworfen. Lexer werden üblicherweise als endliche Automaten implementiert, die aus regulären Ausdrücken abgeleitet sind.

Ein AST ist eine Baumstruktur, die die grammatische Struktur von Quellcode darstellt: Jeder innere Knoten repräsentiert einen Operator oder eine Konstruktion, jedes Blatt einen Operanden oder ein Literal. Im Gegensatz zu einem konkreten Parse-Baum lässt der AST syntaktisches Rauschen wie Klammern und Semikolons weg und behält nur die für die weitere Analyse nötige semantische Struktur. Compiler, Interpreter, Linter und Code-Formatter arbeiten größtenteils auf dem AST statt auf dem rohen Quelltext.

Ein rekursiver Abstiegsparser implementiert die Grammatik als eine Menge gegenseitig rekursiver Funktionen, eine pro Grammatikregel. Um einen Ausdruck zu parsen, ruft er die Ausdrucksfunktion auf, die die Termfunktion für Multiplikation aufruft, die wiederum die Faktorfunktion für Atome aufruft — die Operator-Präzedenz-Hierarchie spiegelt sich direkt im Aufrufstapel wider. Rekursive Abstiegsparser lassen sich leicht von Hand schreiben, liefern hervorragende Fehlermeldungen und werden in Produktionscompilern wie GCC (C-Frontend) und Clang eingesetzt.

Drei-Adress-Code (TAC) ist eine Zwischendarstellung, bei der jede Anweisung höchstens einen Operator und drei Operanden hat (zwei Quellen und ein Ziel), z. B. t1 = a * b; t2 = t1 + c. Diese einfache, einheitliche Struktur erleichtert die Datenflussanalyse — jede temporäre Variable wird nur einmal definiert, was die Static-Single-Assignment-Form (SSA) begünstigt. Die meisten modernen Compiler (GCC, LLVM) verwenden intern eine Form von TAC, bevor sie in Assembler übersetzen; LLVMs IR ist ein bekanntes, gut lesbares Beispiel.

Konstantenfaltung ist eine Optimierung, die konstante Teilausdrücke bereits zur Kompilierzeit auswertet, statt Code zu erzeugen, der sie zur Laufzeit berechnet. Zum Beispiel wird 2 * 3 + 1 zu 7 ohne jegliche Laufzeitkosten. Moderne Compiler propagieren Konstanten auch durch Variablenzuweisungen (Konstantenpropagation), ermöglichen weitere Vereinfachungen wie das Entfernen von totem Code und werten sogar reine Funktionsaufrufe aus, deren Argumente alle konstant sind. Der kombinierte Effekt kann die Anzahl der Instruktionen in Code mit vielen literalen Berechnungen drastisch reduzieren.

Ein Compiler übersetzt Quellcode vorab (Ahead-of-Time, AOT) in eine Zieldarstellung und erzeugt ein Artefakt — eine Binärdatei, Bytecode oder IR —, das unabhängig vom Compiler ausgeführt werden kann. Ein Interpreter liest Quellcode (oder Bytecode) und führt ihn direkt zur Laufzeit Anweisung für Anweisung aus. Viele moderne Systeme kombinieren beides: Python kompiliert zu Bytecode (.pyc), den der CPython-Interpreter dann ausführt, und JavaScript-Engines kompilieren mittels Just-in-Time-Kompilierung (JIT) häufig ausgeführten Code in Maschinencode.

Eine formale Grammatik ist eine Menge von Produktionsregeln, die festlegen, welche Token-Ketten in einer Sprache gültig sind. Kontextfreie Grammatiken (CFGs), beschrieben in Backus-Naur-Form (BNF) oder erweiterter BNF, werden für die meisten Programmiersprachen verwendet. Ein Parser prüft, ob die Eingabe der Grammatik entspricht, und baut den AST auf. Die berühmte Chomsky-Hierarchie ordnet Grammatiken nach Ausdruckskraft; kontextfreie Grammatiken sind mächtig genug, um verschachtelte Strukturen wie ausgeglichene Klammern zu beschreiben, was reguläre Ausdrücke nicht können.

Die semantische Analyse prüft Bedingungen, die die Grammatik nicht ausdrücken kann: Typprüfung (wird eine Ganzzahl zu einer Zeichenkette addiert?), Gültigkeitsbereichsauflösung (ist diese Variable vor ihrer Verwendung deklariert?) und Erkennung von Verwendung vor Initialisierung. In statisch typisierten Sprachen baut diese Phase eine Symboltabelle auf, die Bezeichner ihren Typen zuordnet, und fügt Typannotationen in den AST ein. Fehler hier erzeugen die bekannten Meldungen „Typkonflikt“ oder „nicht deklarierte Variable“, die nach erfolgreichem Parsen auftreten.

Moderne Compiler wenden Dutzende Optimierungsdurchläufe an: Dead-Code-Elimination entfernt Anweisungen, deren Ergebnisse nie verwendet werden; Loop-Unrolling reduziert den Sprung-Overhead; Inlining ersetzt Funktionsaufrufstellen durch den Funktionsrumpf, um Aufrufkosten zu vermeiden; Common-Subexpression-Elimination (CSE) verhindert die Neuberechnung identischer Ausdrücke; und Auto-Vektorisierung wandelt skalare Schleifen in SIMD-Instruktionen um. Die LLVM-Optimierungspipeline wendet bei -O2 rund 60 Durchläufe an, wobei die erzielten Beschleunigungen üblicherweise zwischen dem 2- und 10-fachen gegenüber unoptimiertem Code liegen.

Ein JIT-Compiler kompiliert Code zur Laufzeit, typischerweise nachdem beobachtet wurde, dass er häufig ausgeführt wird („Hot Paths“). Die V8-Engine (verwendet in Chrome und Node.js) interpretiert JavaScript-Bytecode zunächst, ermittelt per Profiling, welche Funktionen am häufigsten aufgerufen werden, und kompiliert diese dann zu optimiertem nativem Maschinencode. Wird eine zuvor getroffene Annahme später verletzt, „deoptimiert“ V8 und fällt auf interpretierte Ausführung zurück. JIT-kompiliertes JavaScript kann für viele Arbeitslasten innerhalb des 2- bis 3-fachen der Geschwindigkeit von äquivalentem C-Code laufen.