Modul
Sprachtechnologie und Compiler [M-INFO-100806]
Leistungspunkte
8Turnus
Jedes SommersemesterDauer
1 SemesterSprache
DeutschLevel
4Version
1Verantwortung
Einrichtung
- KIT-Fakultät für Informatik
Bestandteil von
Teilleistungen
Identifier | Name | LP |
---|---|---|
T-INFO-101343 | Sprachtechnologie und Compiler | 8 |
Erfolgskontrolle(n)
Siehe Teilleistung.
Qualifikationsziele
Die Teilnehmer beherrschen die theoretischen Grundlagen und praktischen Verfahren, die den Compilerphasen lexikalische Analyse, Syntaxanalyse, semantische Analyse, Codegenerierung, Codeoptimierung zugrunde liegen. Die Teilnehmer haben eine Übersicht über den Stand von Wissenschaft und Technik im Bereich Compilerbau und Programmanalyse. Die Teilnehmer sind in der Lage, dieses Wissen praktisch beim Bau eines Compilers umzusetzen (z.B. im Compilerbau-Praktikum). Die Teilnehmer können die Bedeutung von Sprach- und Compilertechnologie für andere Bereiche der Informatik beurteilen.
Insbesondere können Teilnehmer Automaten zur lexikalischen Analyse aus regulären Ausdrücken erzeugen, minimieren, und implementieren, und beherrschen Generatorsysteme wie Flex. Sie kennen wichtige Eigenschaften kontextfreier Grammatiken, und können die theoretischen Grundlagen und Konstruktionsformeln zu LL(k), LR(k), LALR(k), SLR(K), Earley-Parser ableiten. Studierende beherrschen "Grammar Engineering" (z.B. Linksfaktorisierung) und können zu kleinen Grammatiken LALR(k) Parser bzw Parser mit rekursivem Abstieg konstruieren. Sie kennen Verfahren zur Syntaxfehlerbehandlung (z.B. dynamisch kontextsensitive Ankermengenberechnung).
Studierende können einen abstrakten Syntaxbaum als Teil der Syntaxanalyse spezifizieren, implementieren und konstruieren. Sie beherrschen Generatorsystemen wie Bison. Sie verstehen die grundlegende Bedeutung attributierter Grammatiken zur Beschreibung kontextsensitiver Analysen (z.B. Namensanalyse, Überladungsauflösung).
Studierende beherrschen grundlegende Verfahren zur Zwischencodeerzeugung, insbesondere für Ausdrücke und Kontrollfluss, sowie einfache Zwischencodeoptimierung (z.B. Ershov-Verfahren, Transformation logischer Operationen in Kontrollfluss, Elimination redundanter Operationen). Sie verstehen die Speicherabbildung einfacher und komplexer Datenobjekte. Sie beherrschen die Aufruforganisation mit Activation Records, statischen und dynamischen Links, Displays, sowie Closures für Funktionsparameter.
Studenten kennen ein Portfolio wichtiger Optimierungstechniken. Sie beherrschen die theoretischen Grundlagen von Datenflussframeworks und deren Implementierung, inklusive verbandstheoretischer Grundlagen (z.B. Fixpunkt-Iterationsverfahren, Galois-Verbindungen). Sie können verschiedene Varianten distributiver und nicht distributiver Datenflussverfahren anwenden (z.B. Konstantenpropagation), und verstehen die Bedeutung von Korrektheit, Präzision und konservativer Approximation. Sie können zu einfachen Optimierungsproblemen den abstrakten Verband und die Transferfunktionen konstruieren. Sie können die grundlegende Bedeutung des Dominanzkonzepts sowie der SSA-Darstellung beurteilen, kennen den Zusammenhang zwischen beiden, und können den Dominatorbaum und die SSA-Form von Zwischencode konstruieren. Sie können die Anwendung von Dominanz, Datenflussverfahren und SSA bei Programmabhängigkeitsgraphen und Zwischencode-Graphen (z.B. FIRM) analysieren und die Bedeutung dieser Graphen beurteilen.
Studierende kennen x86 Assembler. Sie können Bottom-Up Rewriting und verwandte Mechanismen zur Codeerzeugung anwenden und entsprechende Erzeugungsregeln entwickeln und beurteilen. Insbesondere können sie den Einsatz verschiedener Adressierungsmodi beurteilen. Sie verstehen Grundlagen des Instruction Scheduling. Sie können wichtige Verfahren zur Registerallokation beurteilen und anwenden (z.B. Linear Scan, Graphfärbung) und verstehen die Rolle der SSA-Form und chordaler Graphen bei der Allokation. Sie können Probleme des Auslagerns und des SSA-Abbaus bei der Registerallokation beurteilen. Sie können grundlegende Verfahren zur Speicherverwaltung (z.B. Copy Collector, Generational Scavenging) beurteilen und anwenden. Studierende kennen die Grundlagen der Softwaresicherheitsanalyse, insbesondere den Begriff der Nichtinterferenz sowie dessen Bedeutung für Software-Integrität und Vertraulichtkeit. Studierende kennen Verfahren zur Nichtinterferenzprüfung durch Typsysteme und Abhängigkeitsgraphen.
Voraussetzungen
Siehe Teilleistung.
Inhalt
- Aufbau eines Compilers
- Lexikalische Analyse
- Syntaktische Analyse
- Semantische Analyse
- Codegenerierung
- Programmanalyse
- Sicherheitsanalyse
- Codeoptimierung
- spezifische Technologien: LL-Parser, LR/LALR-Parser, attributierte Grammatiken, Instruktionsauswahl, Registerzuteilung, Laufzeitmechanismen, Speicherverwaltung, Static Single Assignment Form nebst Anwendungen zur Optimierung, Datenflussverfahren, Information Flow Control, Garbage Collection
- Grundlagen der Software-Sicherheitsanalyse (Information Flow Control)
Empfehlungen
Siehe Teilleistung.
Arbeitsaufwand
Vorlesung 4 SWS und Übung 2 SWS, plus Nachbereitung/Prüfungsvorbereitung, 8 LP.
8 LP entspricht ca. 240 Arbeitsstunden, davon
ca. 60 Std. Vorlesungsbesuch
ca. 30 Std. Nachbearbeitung
ca. 30 Std. Übungsbesuch
ca. 60 Std. Bearbeitung Übungsaufgaben
ca. 0.5 Std mündliche Prüfung
ca. 59 Std. Prüfungsvorbereitung