Sprungmarken

Servicenavigation

Hauptnavigation


You are here:

Home Teaching Courses WS 2009/2010 Compilerbau (Lehrauftrag TU Dresden)

Bereichsnavigation

Hauptinhalt

Compilerbau (WS 2009/2010 - TU Dresden)

There are no translations available.

Aktuelles

Datum Nachricht
19.04.2010 Die Ergebnisse der studentischen Evaluation der Vorlesung für das WS 2009/2010 sind hier verfügbar.
26.03.2010 Klausureinsicht
04.02.2010 Informationen zur Klausur jetzt online.
25.01.2010 Der Compilerbau-Pentacast des Chaos Computer Club Dresden.
23.11.2009 BISON-Demo zur Syntaktischen Analyse online.
10.11.2009 FLEX-Demo zur Lexikalischen Analyse online.
07.10.2009 Raumänderungen: Beide Vorlesungstermine finden im Raum INF/E009 statt!
23.09.2009 Vorlesung "Compilerbau" startet am Dienstag, 13.10.2009 um 13:00 in BAR/I-53.


Termine der Vorlesung

Wichtig: Diese Vorlesung wird nicht in Dortmund angeboten, sondern an der TU Dresden!

Dienstags, 13.00 - 14.30
INF/E009

Dienstags, 14.50 - 16.20
INF/E009

Alle zwei Wochen an folgenden Tagen:

  • 13. Oktober 2009
  • 27. Oktober 2009
  • 10. November 2009
  • 24. November 2009
  • 8. Dezember 2009
  • 5. Januar 2010
  • 19. Januar 2010
  • 2. Februar 2010 (An diesem Tag Vorlesung nur von 13.00 - 14.30 Uhr)


Kontakt

Dr. Heiko Falk
Lehrstuhl Informatik 12
Entwurfsautomatisierung für Eingebettete Systeme
Technische Universität Dortmund


Über die Vorlesung

Compiler spielen in der Informatik eine zentrale Rolle. Zum einen ist in den vergangenen Jahrzehnten zu beobachten gewesen, dass das Abstraktionsniveau, auf dem Computer programmiert werden, kontinuierlich angestiegen ist: wurden Rechner zunächst auf Maschinen- oder Assemblercode-Niveau programmiert, setzten sich anschliessend interpretierte Sprachen wie z.B. Basic durch. Diese wurden letztlich von übersetzten Sprachen wie z.B. C oder Pascal abgelöst. Heute wird im wesentlichen objektorientiert in C++ oder Java programmiert.

Zum anderen ist in den vergangenen Jahrzehnten zu beobachten gewesen, dass programmierbare Prozessoren bedeutend komplexer, mächtiger und auf Spezialzwecke ausgerichtet wurden. Beispiele dieser Entwicklung sind Befehlssatzerweiterungen für Gleitkommazahlen oder zur Beschleunigung von Multimedia-Anwendungen (bspw. Intel MMX).

Diese beiden Trends des steigenden Abstraktionsniveaus von Programmiersprachen und der zunehmenden Spezialisierung von Prozessoren divergieren. D.h., zwischen den Programmiersprachen, die heutzutage eingesetzt werden, und den Befehlssätzen moderner Prozessoren klafft eine semantische Lücke, welche stetig wächst. Diese Lücke ist durch Compiler zu schließen, die die Programmiersprache in Maschinencode übersetzen sollen. Zudem soll ein Compiler nicht nur irgend eine funktionierende Übersetzung vornehmen, sondern der erzeugte Maschinencode soll auch noch sehr effizient sein. Dies bedeutet, dass die Aufgaben eines Compilers einerseits aus der Code-Übersetzung und andererseits aus der Code-Optimierung bestehen.

Diese Vorlesung führt auf praxisnahe und algorithmische Weise in sämtliche Teilbereiche des Compilerbaus ein. Im Gegensatz zu klassischen Vorlesungen über Compilerbau wird das Schwergewicht hier nicht nur auf lexikalische, syntaktische und semantische Analyse gelegt. Vielmehr werden forschungsnahe Fragestellungen aus den Bereichen der Instruktionsauswahl, Register-Allokation und Code-Optimierung aufgegriffen. Die Vorlesung soll

  • Aufgaben von und Anforderungen an Compiler für konventionelle Desktop- bzw. Eingebettete Systeme motivieren,
  • Struktur und Aufbau derartiger Compiler aufzeigen,
  • interne Zwischendarstellungen auf verschiedenen Abstraktionsniveaus einführen,
  • die Grundlagen der Übersetzung von Hoch- in Maschinensprachen behandeln, und hauptsächlich
  • Problemstellungen und Optimierungstechniken vor allem im Backend des Compilers erläutern.

Das Schwergewicht der Veranstaltung liegt klar auf dem letzten obigen Punkt. Da Compiler oft verschiedene Zielfunktionen optimieren sollen (z.B. durchschnittliche oder worst-case Laufzeit, Energieverbrauch, Code-Größe), soll der Einfluß von Optimierungstechniken auf diese verschiedenen Zielfunktionen deutlich gemacht werden.


Gliederung der Vorlesung


  • Kapitel 0: Einordnung & Motivation der Vorlesung
  • Kapitel 1: Compiler - Abhängigkeiten und Anforderungen
    • Werkzeuge zur Code-Generierung
    • Quellsprachen für Compiler
    • Prozessor-Architekturen
    • Anforderungen an Compiler
  • Kapitel 2: Interner Aufbau von Compilern
    • Compilerphasen
    • Strukturen Optimierender Compiler
    • Zielfunktionen von Code-Optimierungen
  • Kapitel 3: Lexikalische Analyse (Scanner)
    • Von Regulären Ausdrücken zu Nichtdeterministischen Automaten
    • Von Nichtdeterministischen zu Deterministischen Automaten
    • Automaten-Minimierung
    • Praktische Umsetzung: FLEX
  • Kapitel 4: Syntaktische Analyse (Parser)
    • Einführung
    • Top-Down Syntax-Analyse
    • Bottom-Up Syntax-Analyse
    • Praktische Umsetzung: BISON
  • Kapitel 5: Semantische Analyse
    • Einführung
    • Interne Zwischendarstellungen
    • Semantische Analyse mittels Symboltabellen und BISON
  • Kapitel 6: Instruktionsauswahl
    • Einführung
    • Baum-Überdeckung mit Dynamischer Programmierung
    • Diskussion
  • Kapitel 7: Register-Allokation
    • Einführung
    • Lebendigkeitsanalyse
    • Register-Allokation durch Graph-Färbung
  • Kapitel 8: Code-Optimierung
    • HIR: Parallelisierung für Homogene Multi-DSPs
    • LIR: Generierung von Bit-Paket Operationen für NPUs
    • LIR: Optimierungen für Scratchpad-Speicher
  • Kapitel 9: Ausblick
    • Instruktionsanordnung
    • Retargierbarkeit


Klausur


  • Zeit und Ort: Dienstag, 23. Februar 2010, 09.20 Uhr s.t., Andreas Schubert Bau, Raum 120
  • Dauer: 90 Minuten
  • Anmeldung:
    • Für IST-Studierende: wie üblich über das Prüfungsamt ET.
    • Für Nicht-ISTler: per Email an den Veranstalter unter Angabe von Vorname, Nachname, Matrikelnummer und Studiengang.

      Wichtig: Wenn Sie die in der Klausur "Compilerbau" erworbene Note als Teilprüfungsleistung in eine Komplexprüfung einbringen möchten, so müssen Sie dies unbedingt selbständig vor der Klausur "Compilerbau" mit dem Hauptprüfer Ihrer Komplexprüfung klären!

  • Klausureinsicht: Freitag, 9. April 2010, 10.00 - 12.00 Uhr, Raum INF 1040.