Dieser Vortrag bietet eine technische Einführung in die Implementierung eines Compilers unter Verwendung von C++, Flex und Bison. Der Prozess wird in die Phasen Frontend (Lexikalische Analyse, Parsing, Semantische Prüfung) und Backend (Codegenerierung) unterteilt. Es wird erläutert, wie ein Abstract Syntax Tree (AST) und eine Symboltabelle als zentrale Datenstrukturen dienen, um Quellcode in eine logische Repräsentation zu überführen. Ein besonderer Schwerpunkt liegt auf der Nutzung von LLVM als Backend-Infrastruktur, um plattformunabhängige Intermediate Representation (IR) zu erzeugen und diese mittels Clang in ausführbare Binärdateien zu kompilieren. Der Fokus liegt auf der praktischen Verknüpfung von generiertem Code aus Compiler-Generatoren mit manuell geschriebenen C++-Logiken.
Key Highlights & Timestamps
0:00 Struktur eines Compilers: Aufteilung in Frontend (Analyse des Quellcodes) und Backend (Synthese des Zielcodes). Das Frontend umfasst Lexer, Parser und semantische Analysen.
1:57 Logikrepräsentation: Einsatz eines AST (Abstract Syntax Tree) zur Abbildung der Programmlogik und einer Symboltabelle zur Verwaltung von Variablen, Konstanten, Typen und Gültigkeitsbereichen (Scopes).
4:06 Lexikalische Analyse (Lexer): Transformation des Zeichenstroms in Tokens mittels regulärer Ausdrücke (Regex). Identifikation von Bezeichnern, Literalen und Operatoren.
6:38 Compiler-Generatoren (Flex): Automatisierte Erzeugung von C/C++-Lexern aus Definitionsdateien. Nutzung der Variable yylval zur Übergabe von Token-Attributen an den Parser.
10:05 Manuelle Lexer-Implementierung: Aufbau eines objektorientierten Lexers in C++ unter Verwendung von Enums und ASCII-Werten zur Token-Klassifizierung.
12:51 Syntaktische Analyse (Parser): Definition der Sprachgrammatik durch Produktionsregeln. Überprüfung der Token-Reihenfolge auf Konformität mit der Sprachdefinition.
15:30 Parser-Generatoren (Bison): Implementierung von LALR-Parsern. Bevorzugung von Links-Rekursion in der Grammatikdefinition zur effizienten Baumkonstruktion.
20:21 AST-Konstruktion: Aufbau der Baumstruktur innerhalb der Parser-Aktionen. Jedes Non-Terminal im Parser korrespondiert mit einer Node-Klasse im AST.
22:48 Semantische Prüfungen: Validierung der Logik nach dem Parsing, einschließlich Typenprüfung (Type Checking) und Verifizierung von Variablendeklarationen. Transformation des AST durch automatische Typkonvertierungen.
26:21 Backend & LLVM: Nutzung der LLVM Intermediate Representation (IR) als Zielformat. Vorteil: Zugriff auf hochoptimierte Backends für diverse Hardware-Architekturen.
28:53 LLVM API: Verwendung der C++-Library von LLVM zur programmatischen Erzeugung von IR-Code direkt aus den AST-Knoten heraus via codegen()-Funktionen.
33:17 Integration: Verknüpfung der generierten Funktion yyparse() mit der main-Routine zur Initialisierung des Analyse- und Kompilierungsprozesses.
Glossar
AST (Abstract Syntax Tree): Eine Baumstruktur, die die hierarchische syntaktische Struktur von Quellcode repräsentiert, wobei abstrakte Operationen statt konkreter Syntaxzeichen im Fokus stehen.
Backend: Der Teil des Compilers, der die interne Repräsentation des Programms in die Zielsprache (z. B. Maschinencode) übersetzt.
Bison: Ein Parser-Generator, der eine formale Grammatik (meist in BNF) in C/C++-Code übersetzt.
Flex (Fast Lexical Analyzer): Ein Werkzeug zum Erzeugen von Scannern (Lexern), die Textmuster in Tokens zerlegen.
Frontend: Die Phase des Compilers, die den Quellcode liest, auf Fehler prüft und in eine interne Datenstruktur (AST) überführt.
Intermediate Representation (IR): Eine maschinenunabhängige Zwischensprache, die innerhalb eines Compilers zur Optimierung und Analyse verwendet wird.
LALR (Look-Ahead Left-to-Right): Ein spezifischer Algorithmus für Parser-Generatoren wie Bison zur effizienten Analyse kontextfreier Grammatiken.
Lexer (Scanner): Eine Komponente, die den Eingabetext in eine Sequenz von logischen Einheiten, sogenannte Tokens, zerlegt.
Links-Rekursion: Ein Grammatikmuster, bei dem das am weitesten links stehende Symbol einer Regel das Regel-Symbol selbst ist (wichtig für die Arbeitsweise von Bison).
LLVM: Eine Compiler-Infrastruktur, die Tools zur Optimierung und Generierung von Maschinencode für verschiedene Architekturen bietet.
Parser: Eine Komponente, die die Token-Sequenz des Lexers analysiert und prüft, ob sie den Regeln der Grammatik entspricht.
Scope: Der Gültigkeitsbereich eines Bezeichners (z. B. einer Variable) innerhalb des Programmcodes.
Symbol Table: Eine Datenstruktur (oft eine Hash-Map oder ein Baum), die Informationen über alle im Programm vorkommenden Bezeichner speichert.
Token: Die kleinste syntaktische Einheit einer Programmiersprache, z. B. ein Schlüsselwort wie int oder ein Operator wie +.
Transpiler: Ein Compiler, der Quellcode einer Hochsprache in eine andere Hochsprache übersetzt (statt in Maschinencode).