(V2+Ü2)
Termin: Mi 10-12 h/D 406 (V), Mi 14-16 Uhr/G 420 (Ü)
Doz.: Torsten Grust (V), André Seifert (Ü)
Adressaten:
Studierende des Information Engineering im Bachelor-Vertiefungsstudium/im Masterprogramm
Themengebiet:
Informatik der Systeme / Grundlagen der Informatik
Angebot im Lehrexport:
Mathematik, Nebenfach oder Schwerpunkt Informatik
Informatik in einem Magisterstudiengang
Voraussetzungen:
Kenntnisse in C (oder C++)
(bspw. aus A. Pasettis C/C++-Kurs im SS 2002)
oder gute Kenntnisse einer anderen
prozeduralen/objekt-orientierten Programmiersprache
und Bereitschaft, sich mit C vertraut zu machen
Interesse an Programmiersprachen an sich und Spass
an formalen Methoden
Inhalt:
Diese Vorlesung führt die Teilnehmer in eines der
``klassischen'' Gebiete der Informatik ein: dem Bau von
Übersetzern für Programmiersprachen (Compilerbau).
Während des Semesters werden wir einen Compiler für eine
nicht-triviale Programmiersprache - Tiger - konstruieren und
dabei alle Phasen der Übersetzung kennenlernen. Unter
anderem unterstützt Tiger Arrays, Records und genestete
Funktionen.
Die wichtigsten Phasen sind dabei:
1.Erkennen von Programmstrukturen in Quelltexten
[Syntaxanalyse]
2.Analyse der Bedeutung eines (Tiger-)Progammes
[Semantische Analyse]
3.Übersetzung von Programmen in einen einfachen
Zwischen-Code
[Compilation]
4.Abbildung des Zwischen-Codes auf den
Maschinen-Code (Assembler) einer tatsächlichen CPU,
in diesem Kurs wahrscheinlich MIPS RISC CPUs, aber
Studenten erhalten auch Unterstützung bei der
Portierung auf Intel CPUs
[Code-Generierung]
Schritt für Schritt werden wir in dieser Vorlesung also die
Transformation von Tiger-Programmen in Assembler
verfolgen und - ganz wichtig - auch selber implementieren:
die Teilnehmer an dieser Vorlesung werden größere Teile
eines Tiger-Compilers selbst bauen lernen. Bitte
entsprechenden Zeitaufwand während des Semesters
einplanen. Es lohnt sich!
Die Vorlesung wird versuchen, einen interessanten Mix aus
theoretischen und praktischen Aspekten des Compilerbaus
zu vermitteln. Auch in der Vorlesung (und natürlich in der
Übung) werden wir konkrete Programmiertechniken
besprechen, die im Compilerbau Anwendung finden. Also:
Ärmel hochkrempeln!
Als Implementierungssprache für den Tiger-Compiler
werden wir C einsetzen. Teilnehmer, die C++ oder Java
kennen, sollten mit C eigentlich gut zurechtkommen (wir
erwarten von diesen Teilnehmern die Bereitschaft, sich
Kenntnisse in C anzueignen).
Literatur:
Weitere Materialien zum Kurs finden sich auf der
kursbegleitenden Seite. Ansonsten:
Quelltextfragmente eines Tiger-Compilers (die von den
Studierenden im Laufe des Semesters ergänzt werden)
Buch zur Vorlesung:
Modern Compiler Implementation in C
Andrew W. Appel, Maia Ginsburg
Cambridge University Press, 1998
ISBN 052158390-X
Achtung: Dieses Buch ist weitgehend vergriffen und
wird vom Verlag auch nicht mehr produziert. Den
Teilnehmern wird deshalb ein Auszug aus den
relevanten Kapiteln des Buches zur Verfügung gestellt.
Für die Bearbeitung der praktischen Übungsaufgaben
ist die eigenständige Arbeit mit diesen Kapitelauszügen
wichtig.
Outline:
1.Einführung
2.Lexical Analysis
3.Parsing
4.Abstract Syntax
5.Semantic Analysis (Bindings, Type Checking)
6.Activation Records
7.Translation to Intermediate Code
8.Basic Block and Traces
9.Instruction Selection
10.Liveness Analysis
11.Register Allocation
Leistungsnachweis:
Mündliche Prüfung (30 min. Kolloquium) zum
Semesterende
Erfolgreiche Mitarbeit an den praktischen Übungen
(Konstruktion eines Compilers für die Sprache ``Tiger'')
Leistungspunkte:
Es können bei erfolgreicher Teilnahme 6 Punkte angerechnet werden.
