Tobias Heineken

Tobias Heineken, M. Sc.

Department Informatik (INF)
Lehrstuhl für Informatik 2 (Programmiersysteme)

Raum: Raum 05.136
Martensstraße 3
91058 Erlangen

Sprechzeiten

n.V. per E-Mail

Projekte

  • Automatisiertes Testen von Übersetzern

    (Projekt aus Eigenmitteln)

    Übersetzer für Programmiersprachen sind äußerst komplexe Anwendungen, an die hohe Korrektheitsanforderungen gestellt werden: Ist ein Übersetzer fehlerhaft (d.h. weicht sein Verhalten vom dem durch die Sprachspezifikation definierten Verhalten ab), so generiert dieser u.U. fehlerhaften Code oder stürzt bei der Übersetzung mit einer Fehlermeldung ab. Solche Fehler in Übersetzern sind oftmals schwer zu bemerken oder zu umgehen. Nutzer erwarten deshalb i.A. eine (möglichst) fehlerfreie Implementierung des verwendeten Übersetzers.

    Leider lassen sowohl vergangene Forschungsarbeiten als auch Fehlerdatenbanken im Internet vermuten, dass kein real verwendeter Übersetzer fehlerfrei ist. Es wird deshalb an Ansätzen geforscht, mit deren Hilfe die Qualität von Übersetzern gesteigert werden kann. Da die formale Verifikation (also der Beweis der Korrektheit) in der Praxis oftmals nicht möglich oder rentabel ist, zielen viele der Forschungsarbeiten darauf ab, Übersetzer möglichst umfangreich und automatisiert zu testen. In den meisten Fällen erhält der zu testende Übersetzer dabei ein Testprogramm als Eingabe. Anschließend wird das Verhalten des Übersetzers bzw. des von ihm generierten Programms überprüft: Weicht dieses vom erwarteten Verhalten ab (stürzt der Übersetzer also beispielsweise bei einem gültigen Eingabeprogramm mit einer Fehlermeldung ab), so wurde ein Fehler im Übersetzer gefunden. Soll dieser Testvorgang automatisiert stattfinden, ergeben sich drei wesentliche Herausforderungen:

    • Woher kommen die Testprogramme, auf die der Übersetzer angewendet wird?
    • Was ist das erwartete Verhalten des Übersetzers bzw. des von ihm erzeugten Codes? Wie kann bestimmt werden, ob das tatsächliche Verhalten des Übersetzers korrekt ist?
    • Wie können Testprogramme, die einen Fehler im Übersetzer anzeigen, vorbereitet werden, um der Behebung des Fehlers im Übersetzer bestmöglich behilflich zu sein?

    Während die wissenschaftliche Literatur diverse Lösungen für die zweite Herausforderung vorstellt, die auch in der Praxis bereits etabliert sind, stellt die automatisierte Generierung zufälliger Testprogramme noch immer eine große Hürde dar. Damit Testprogramme zur Detektion von Fehlern in allen Teilen des Übersetzers verwendet werden können, müssen diese allen Regeln der jeweiligen Programmiersprache genügen, d.h. die Programme müssen syntaktisch und semantisch korrekt (und damit übersetzbar) sein. Auf Grund der Vielzahl an Regeln "echter" Programmiersprachen stellt die Generierung solcher übersetzbarer Programme eine schwierige Aufgabe dar. Dies wird zusätzlich dadurch erschwert, dass das Programmgenerierungsverfahren möglichst effizient arbeiten muss: Die wissenschaftliche Literatur zeigt, dass die Effizienz eines solchen Verfahrens maßgebliche Auswirkungen auf seine Effektivität hat -- nur wenn in kurzer Zeit viele (und große) Programme generiert werden können, kann das Verfahren sinnvoll zur Detektion von Übersetzerfehlern eingesetzt werden.

    In der Praxis scheitert das automatisierte Testen von Übersetzern deshalb oftmals daran, dass kein zugeschnittener Programmgenerator verfügbar ist und die Entwicklung eines solchen einen zu hohen Aufwand bedeutet. Ziel unseres Forschungsprojekts ist daher die Entwicklung von Verfahren, die den Aufwand für die Implementierung von effizienten Programmgeneratoren reduzieren.

    Weil in der automatische Generierung zufälliger Testprogramme zumeist große Programme generiert werden müssen, um eine effiziente Fehlersuche zu ermöglichen, können diese Programme nur schwer zur Behebung des Fehlers verwendet werden. Üblicherweise ist nur ein sehr kleiner Teil des Programms ursächlich für den Fehler, und möglichst viele anderen Teile müssen automatisch entfernt werden, bevor die Behebung des Fehlers plausibel ist. Diese sogenannte Testfallreduktion nutzt auch die bereits angesprochenen Lösungen für die Erkennung des erwarteten Verhalten und ist für automatisch generierte Programme unerlässlich,
    sodass eine gemeinsame Betrachtung mit den anderen Komponenten sinnvoll ist. Üblicherweise ist die Testfallreduktion so gestaltet, dass fehlerauslösende Programm aus allen Quellen verarbeitet werden können.

    Leider ist oftmals nicht klar, welches der verschiedenen in der wissenschaftlichen Literatur vorgestellten Verfahren sich am besten für welche Situation eignet. Außerdem dauert eine Testfallreduktion in einigen Fällen sehr lange. Ziel unseres Forschungsprojekts ist daher, eine aussagekräftige Testfallsammlung zu schaffen und an dieser bestehende Verfahren zu vergleichen und zu verbessern.

    Im Jahr 2018 haben wir mit der Entwicklung eines entsprechenden Werkzeugs begonnen. Als Eingabe dient eine Spezifikation der syntaktischen und semantischen Regeln der jeweiligen Programmiersprache in Form einer abstrakten Attributgrammatik. Eine solche erlaubt eine knappe Notation der Regeln auf hohem Abstraktionsniveau. Ein von uns neu entwickelter Algorithmus erzeugt dann Testprogramme, die allen spezifizierten Regeln genügen. Der Algorithmus nutzt dabei diverse technische Ideen aus, um eine angemessene Laufzeit zu erreichen. Dies ermöglicht die Generierung großer Testfallmengen in vertretbarer Zeit, auch auf üblichen Arbeitsplatzrechnern. Eine erste Evaluation hat nicht nur gezeigt, dass unser Verfahren sowohl effektiv als auch effizient ist, sondern auch dass es flexibel einsetzbar ist. So haben wir mit Hilfe unseres Verfahrens nicht nur Fehler in den C-Übersetzern gcc und clang entdeckt (unser Verfahren erreicht dabei eine ähnliche Fehleraufdeckungsgüte wie ein sprachspezifischer Programmgenerator aus der wissenschaftlichen Literatur), sondern auch diverse Bugs in mehreren SMT-Entscheidern. Einige der von uns entdeckten Fehler waren den jeweiligen Entwicklern zuvor noch unbekannt.

    Im Jahr 2019 haben wir zusätzliche Features für das Schreiben von Sprachspezifikationen implementiert und die Effizienz des Programmgenerierungsverfahrens gesteigert. Durch die beiden Beiträge konnte der Durchsatz unseres Werkzeugs deutlich gesteigert werden. Des Weiteren haben wir mit Hilfe neuer Sprachspezifikationen Fehler in Übersetzern für die Programmiersprachen Lua und SQL aufgedeckt. Die Ergebnisse unserer Arbeit sind in eine Ende 2019 eingereichte (und inzwischen angenommene) wissenschaftliche Publikation eingeflossen. Neben der Arbeit an unserem Verfahren zur Programmgenerierung haben wir außerdem mit der Arbeit an einem Verfahren zur Testfallreduzierung begonnen. Das Verfahren reduziert die Größe eines zufällig generierten Testprogramms, das einen Fehler in einem Übersetzer auslöst, um die Suche nach der Ursache des Fehlers zu vereinfachen.

    Im Jahr 2020 lag der Fokus des Forschungsprojekts auf sprachunabhängigen Verfahren zur automatischen Testfallreduzierung. Die wissenschaftliche Literatur schlägt unterschiedliche Reduzierungsverfahren vor. Da es bislang allerdings keinen aussagekräftigen Vergleich dieser Verfahren gibt, ist unklar, wie effizient und effektiv die vorgeschlagenen Reduzierungsverfahren tatsächlich sind. Wie wir festgestellt haben, gibt es dafür im Wesentlichen zwei Gründe, die darüber hinaus auch die Entwicklung und Evaluation neuer Verfahren erschweren. Zum einen verwenden die vorhandenen Implementierungen der vorgeschlagenen Reduzierungsverfahren unterschiedliche Implementierungssprachen, Programmrepräsentationen und Eingabegrammatiken. Mit diesen Implementierungen ist ein fairer Vergleich dieser Verfahren deshalb kaum möglich. Zum anderen gibt es keine umfangreiche Sammlung von (noch unreduzierten) Testprogrammen zur Evaluation von Reduzierungsverfahren. Dies hat zur Folge, dass die publizierten Reduzierungsverfahren jeweils nur mit sehr wenigen Testprogrammen evaluiert wurden, was die Aussagekraft der präsentierten Ergebnisse beeinträchtigt. Da in manchen Fällen darüber hinaus nur Testprogramme in einer einzigen Programmiersprache verwendet wurden, ist bislang unklar, wie gut diese Verfahren für Testprogramme in anderen Programmiersprachen funktionieren (wie sprachunabhängig diese Verfahren also tatsächlich sind). Um diese Lücken zu schließen, haben wir im Jahr 2020 mit der Implementierung eines Frameworks begonnen, das die wichtigsten Reduzierungsverfahren beinhaltet und so einen fairen Vergleich dieser Verfahren ermöglicht. Außerdem haben wir mit der Erstellung einer Testfallsammlung begonnen. Diese beinhaltet bereits etwa 300 Testprogramme in den Sprachen C und SMT-LIB 2, die etwa 100 unterschiedliche Fehler in realen Übersetzern auslösen. Diese Testfallsammlung erlaubt nicht nur aussagekräftigere Vergleiche von Reduzierungsverfahren, sondern verringert außerdem den Aufwand für die Evaluation zukünftiger Verfahren. Anhand erster Experimente konnten wir feststellen, dass es bislang kein Reduzierungsverfahren gibt, dass in allen Fällen am besten geeignet ist.

    Außerdem haben wir uns im Jahr 2020 mit der Frage beschäftigt, wie das im Rahmen des Forschungsprojekts entstandene Framework zur Generierung zufälliger Testprogramme erweitert werden kann, um neben funktionalen Fehlern auch Performance-Probleme in Übersetzern finden zu können. Im Rahmen einer Abschlussarbeit ist dabei ein Verfahren entstanden, das eine Menge zufällig generierter Programme mit Hilfe von Optimierungstechniken schrittweise so verändert, dass die resultierenden Programme im getesteten Übersetzer deutlich höhere Laufzeiten als in einer Referenzimplementierung auslösen. Erste Experimente haben gezeigt, dass so tatsächlich Performance-Probleme in Übersetzern gefunden werden können.

    Im Jahr 2021 haben wir die Implementierung der wichtigsten Reduzierungsverfahren aus der wissenschaftlichen Literatur sowie die Erstellung einer Testfallsammlung für deren Evaluation abgeschlossen. Aufbauend darauf haben wir außerdem einen quantitativen Vergleich der Verfahren durchgeführt; soweit wir wissen, handelt es sich dabei um den mit Abstand umfangreichsten und aussagekräftigsten Vergleich bisheriger Reduzierungsverfahren. Unsere Ergebnisse zeigen, dass es bislang kein Verfahren gibt, das in allen Anwendungsfällen am besten geeignet wäre. Außerdem konnten wir feststellen, dass es für alle Verfahren zu deutlichen Ausreißern kommen kann, und zwar sowohl hinsichtlich Effizienz (also wie schnell ein Reduzierungsverfahren ein Eingabeprogramm reduzieren kann) als auch Effektivität (also wie klein das Ergebnis eines Reduzierungsverfahrens ist). Dies deutet darauf hin, dass es noch Potenzial für die Entwicklung weiterer Reduzierungsverfahren in der Zukunft gibt, und unsere Ergebnisse liefern einige Einsichten, was dabei zu beachten ist. So hat sich beispielsweise gezeigt, dass ein Hochziehen von Knoten im Syntaxbaum unabdingbar für die Generierung möglichst kleiner Ergebnisse (und damit eine hohe Effektivität) ist und dass eine effiziente Behandlung von Listenstrukturen im Syntaxbaum notwendig ist. Die Ergebnisse unserer Arbeit sind in eine im Jahr 2021 eingereichte und angenommene Publikation eingeflossen.

    Außerdem haben wir im Jahr 2021 untersucht, ob bzw. wie sich die Effektivität unseres Programmgenerierungsverfahrens steigern lässt, wenn bei der Generierung die Überdeckung der zugrundeliegenden Grammatik berücksichtigt wird. Im Rahmen einer Abschlussarbeit wurden dazu unterschiedliche, aus der wissenschaftlichen Literatur stammende kontextfreie Überdeckungsmetriken für den Anwendungsfall adaptiert sowie implementiert und evaluiert. Dabei hat sich gezeigt, dass die Überdeckung hinsichtlich einer kontextfreien Metrik nur bedingt mit der Fehleraufdeckung korreliert.  In zukünftigen Arbeiten sollte deshalb untersucht werden, ob Überdeckungsmetriken, die auch kontextsensitive, semantische Eigenschaften berücksichtigen, besser für diesen Anwendungsfall geeignet sind.

    Im Jahr 2022 wurde im Rahmen einer Abschlussarbeit mit der Entwicklung eines Rahmenwerks für die Realisierung sprachadaptierter Reduktionsverfahren begonnen. Dieses Rahmenwerk stellt eine domänenspezifische Sprache (DSL) zur Verfügung, mit deren Hilfe sich Reduktionsverfahren auf einfache und knappe Art und Weise beschreiben lassen. Mit diesem Rahmenwerk und der entwickelten DSL soll es möglich sein, bestehende Reduktionsverfahren mit möglichst wenig Aufwand an die Besonderheiten einer bestimmten Programmiersprache anpassen zu können. Die Hoffnung dabei ist, dass solche sprachadaptierten Verfahren noch effizienter und effektiver arbeiten können als die bestehenden, sprachunabhängigen Reduktionsverfahren. Darüber hinaus soll das Rahmenwerk auch den Aufwand für die Entwicklung zukünftiger Reduktionsverfahren verringern und könnte so einen wertvollen Beitrag für die Forschung auf diesem Gebiet leisten.

    In Jahr 2023 lag der Fokus des Forschungsprojekts auf den Listenstrukturen, die bereits in 2021 kurz angesprochen wurden: Nahezu alle seit 2021 untersuchten Verfahren gruppieren Knoten im Syntaxbaum in Listen, um aus diesen dann mittels eines Listenreduktionsverfahrens nur die notwendigen Knoten auszuwählen. Unsere Experimente haben gezeigt, dass teilweise 70% und mehr der Reduktionszeit in Listen mit mehr als 2 Elementen verbracht wird. Diese Listen sind deswegen relevant, weil es in der wissenschaftlichen Literatur verschiedene Listenreduktionsverfahren gibt, diese sich aber für Listen mit 2 oder weniger Elementen nicht unterscheiden. Da der zeitliche Anteil so hoch sein kann, haben wir diese verschiedenen Listenreduktionsverfahren in unsere in 2020/2021 entwickelten Implementierungen der wichtigen Reduktionsverfahren integriert. Dabei haben wir neben den Verfahren aus der Literatur auch solche aufgenommen, die nur auf einer Website beschrieben oder nur in einer frei zugänglichen Implementierung umgesetzt waren.

    Es wurde auch untersucht, wie man eine Listenreduktionen an einer Stelle unterbrechen und später fortsetzen kann. Die Idee war, auf der Basis einer Priorisierung zwischenzeitlich eine andere Liste zu reduzieren, die eine größere Auswirkung auf die Verkleinerung hat. In einigen Fällen trat der erhoffte Geschwindigkeitsgewinn zwar ein, es bleiben aber Fragen offen, die weitere Experimente mit priorisierenden Reduzierern und Listenreduktionsverfahren erfordern.

Aktuelle Lehrveranstaltungen

Ausgewählte Kapitel aus dem Übersetzerbau

Titel Ausgewählte Kapitel aus dem Übersetzerbau
Kurztext inf2-ueb3
Turnus des Angebots nur im Wintersemester
Semesterwochenstunden 2

Es ist keine Anmeldung erforderlich.

In der Vorlesung werden Aspekte des Übersetzerbaus beleuchtet, die über die Vorlesungen "Grundlagen des Übersetzerbaus" und "Optimierungen in Übersetzern" hinausgehen.

Voraussichtliche Themen sind:
- Übersetzer u. Optimierungen für funktionale Programmiersprachen
- Übersetzung aspektorientierter Programmiersprachen
- Erkennung von Wettlaufsituationen
- Software Watermarking
- Statische Analyse und symbolische Ausführung
- Binden von Objektcode und Unterstützung für dynamische Bibliotheken
- Strategien zur Ausnahmebehandlung
- Just-in-Time-Übersetzer
- Speicherverwaltung und Speicherbereinigung
- LLVM

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt: https://www.studon.fau.de/crs4533480.html

1. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Mi, 08:15 - 09:45 18.10.2023 - 07.02.2024 01.11.2023
27.12.2023
03.01.2024
  • Tobias Heineken
  • Florian Mayer
  • Julian Brandner
  • Prof. Dr. Michael Philippsen
11302.02.133

Grundlagen des Übersetzerbaus

Titel Grundlagen des Übersetzerbaus
Kurztext inf2-ueb
Turnus des Angebots nur im Wintersemester
Semesterwochenstunden 2

Voraussetzung zur Teilnahme an der Modulprüfung ist die erfolgreiche Bearbeitung der Übungsaufgaben.

*Motivation:*

Auf den ersten Blick erscheint es wenig sinnvoll, sich mit Übersetzerbau zu beschäftigen. Andere Themen scheinen wesentlich näher an der direkten Anwendbarkeit in der industriellen Praxis. Der erste Blick täuscht:
- Übersetzer gehören wohl zu den am gründlichsten studierten mittelgroßen sequentiellen Software-Systemen. Man kann viel aus den Erfahrungen lernen, die im Laufe der Jahre gesammelt wurden.
- In den Übungen, die die Vorlesung begleiten, werden Sie selbst einen (kleinen) Übersetzer entwickeln.
- Für viele Teilnehmer wird dieses Projekt das erste größere Software-Projekt sein. Viele der Algorithmen aus dem Grundstudium werden angewendet.
- Bei jedem von Ihnen verwendeten Übersetzer gehen Sie in der Regel davon aus, dass richtiger Coder erzeugt wird. In der Vorlesung erfahren Sie, wie das geforderte hohe Maß an Korrektheit und Zuverlässigkeit erreicht wird.
- Sie erlangen ein Verständnis für Konzepte von Programmiersprachen und verstehen, welcher Maschinen-Code aus Sprachkonstrukten gemacht wird. Mit diesem Wissen im Hinterkopf verbessern Sie Ihre Fähigkeit, gute und effiziente Programme zu schreiben.
- Übersetzer werden nicht nur für Programmiersprachen benötigt. Spezielle Übersetzer braucht man in vielen Bereichen des täglichen Informatik-Lebens z.B. zur Textformatierung, für Programmtransformationen, für aspektorientiertes Programmieren, für die Verarbeitung von XML, ...
- Es gehört zu einer Ingenieur-Ausbildung, in der Lage zu sein, diejenigen Werkzeuge selbst zu fertigen, die man verwendet. Für Informatiker gehört daher ein Verständnis vom Innenleben eines Übersetzers zum Rüstzeug.

.

*Fokus der Lehrveranstaltung:*

Es werden Konzepte und Techniken der Übersetzerkonstruktion aus Sicht
eines Übersetzerbauers und entlang der wesentlichen Arbeitsschritte
eines Übersetzers (Frontend; Mittelschicht; Backend)
vorgestellt. Übungen und Praxisaufgaben ergänzen die Vorlesung. Hier
entwickeln die Studierenden auf der Basis eines vorgegebenen
Programmrahmens einen eigenen Übersetzer für die Programmiersprache
e2, die speziell für den Übersetzerbau-Vorlesungszyklus entworfen
wurde.

*Behandelte Themenfelder:*

- Prinzipien der Übersetzung imperativer Programmiersprachen
- Struktur eines Übersetzers
- Symbolentschlüssler (Scanner) und Zerteiler (Parser)
- Abstrakter Syntaxbaum (AST)
- Besuchermuster
- AST-Transformationen, Entzuckerung
- Symboltabellen und Sichtbarkeitsbereiche
- Semantische Analyse: Namensanalyse, Typprüfung
- Übersetzung von arithmetischen Ausdrücken und Kontrollflusskonstrukten in registerbasierte oder stapelbasierte Zwischensprachen
- Übersetzung von Methoden und Methodenaufrufen; Methodenschachteln
- Übersetzung objektorientierter Sprachen mit Einfachvererbung, Schnittstellen und Mehrfachvererbung
- Methodenauswahl in Java (überladene und überschriebene Methoden)
- Code-Generierung nach Sethi-Ullmann, Graham-Glanville, per Baumtransformation sowie mit Hilfe dynamischer Programmierung
- Registerallokation mit lokalen Techniken und mit Graphfärbung
- Instruktionsanordnung mit "list scheduling"
- Debugger

.

*Themen der Vorlesungseinheiten:*

1. Einführung (Überblick, modulare Struktur von Übersetzern, Frontend,
Mittelschicht, Backend), Bootstrapping)

2. Symbolentschlüssler (Lexer) und Zerteiler (Parser), (Token,
Literale, Symboltabelle, Grammatikklassen (LK(k), LL(k), ...),
konkreter Syntaxbaum, Shift-Reduce-Parser)

3. AST und semantische Analyse (abstrakter Syntaxbaum, Besuchermuster,
Double Dispatch, Sichtbarkeitsbereiche, Definitionstabelle)

4. Typkonsistenz (Typsicherheit, Typsystem, Typüberprüfung,
Typberechnung, Typkonvertierung, attributierte Grammatiken)

5. AST-Transformationen (Transformationsschablonen für Ausdrücke,
Transformation innerer und generischer Klassen)

6. Transformation in Zwischensprache (registerbasiert versus
stapelbasiert, Übersetzung von arithmetischen Ausdrücken, Zuweisungen,
mehrdimensionalen Feldern, struct-Datentypen und
Kontrollflussstrukturen (einschließlich Kurzschlussauswertung))

7. Methodenschachteln und Kellerrahmen (relative Adressen, call by
value/reference/name, geschachtelte Funktionen, Funktionszeiger,
Stack- und Framepointer, Funktionsaufruf, Prolog, Epilog)

8. Objektorientierte Sprachen I: Einfachvererbung (Symbol- und
Typanalyse, Methodenauswahl mit Überschreiben und Überladen, virtuelle
Methodenaufrufe, Klassendeskriptoren, dynamische Typprüfung und
-wandlung)

9. Objektorientierte Sprachen II: Schnittstellen und Mehrfachvererbung
(Interface v-Tables, dynamische Typprüfung und -wandlung mit
Interfaces, Interfaces mit Default-Implementierung, Diamantenproblem)

10. Einfache Code-Erzeugung (Code-Selektion nach Sethi-Ullman,
Register-Allokation, Instruktionsreihenfolge, optimale Code-Erzeugung
für Ausdrucksbäume)

11. Fortgeschrittene Code-Erzeugung (Baumtransformation,
Graham-Glanville, dynamisches Programmieren)

12. Registerallokation (Leistungsabschätzung, Lebendigkeitsintervalle,
Kollisions- und Interferenzgraph, Spilling, Färbungsheuristiken,
Aufteilung von Lebendigkeitsintervallen, 2nd Chance Bin Packing,
Registerverschmelzung)

13. Parallelismus auf Instruktionsebene, Instruktionsreihenfolge,
Debugger (Konflikte im Instruktionsfließband, List Scheduling,
Delay-Slots, Sprungzielvorhersage, ptrace, Unterbrechungs- und
Beobachtungspunkte, DWARF)

*Meilensteine der Übungsbetriebs:*

Im Rahmen der Übungen (separater UnivIS-Eintrag) werden die in der
Vorlesung vorgestellten Konzepte und Techniken zur Implementierung
eines Übersetzers in die Praxis umgesetzt. Ziel der Übungen ist es,
bis zum Ende des Semesters einen funktionsfähigen Übersetzer für die
Beispiel-Programmiersprache e2 zu implementieren. Ein Rahmenprogramm
ist gegeben, das in fünf Meilensteinen um selbstentwickelte
Schlüsselkomponenten zu erweitern ist.

Folgende Meilensteine sind zu erreichen:

Meilenstein 1: Grammatik, AST-Konstruktion: Antlr-Produktionen,
AST-Besucherschnittschelle, generischer AST-Besucher für return und
Schleifen, AST-Besucher zur Visualisierung.

Meilenstein 2: Symbolanalyse, Symboltabelle, Standardfunktionen,
AST-Besucher für die Symbolanalyse.

Meilenstein 3: Konstantenfaltung per AST-Transformation, Typanalyse
mit bottom-up AST-Besuch, der implizite Typwandlungen bei Bedarf
ergänzt.

Meilenstein 4: AST-Besucher zur Erzeugung der
Zwischensprachrepräsentation, Übersetzung von arithmetischen
Ausdrücken, return, Zuweisungen, logischen Ausdrücken, Bedingungen und
Schleifen.

Meilenstein 5.0: Speicherzuteilung: Festlegung und Umsetzung der ABI
Aufrufkonvention, Zuweisung von Speicheradressen zu Variablen;
Kellerrahmenallokation; caller-save und callee-save Register.

Meilenstein 5.1: Code-Erzeugung: Implementierung der e2
Standardbibliothek; IR-Besucher zur Erzeugung von Assembly-Code.

Für die Meilensteine 1-3 soll der Übersetzer sowohl Integer- als auch
Gleitkomma-Arithmetik unterstützen. Für die nachfolgenden Meilensteine
reicht Integer-Arithmetik.

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt: https://www.studon.fau.de/crs4533479.html

1. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Do, 08:15 - 09:45 19.10.2023 - 08.02.2024 28.12.2023
04.01.2024
  • Prof. Dr. Michael Philippsen
11301.00.005

Übungen zu Ausgewählte Kapitel aus dem Übersetzerbau

Titel Übungen zu Ausgewählte Kapitel aus dem Übersetzerbau
Kurztext inf2-ueb3-ex
Turnus des Angebots nur im Wintersemester
Semesterwochenstunden 2

Blockveranstaltung n.V. nach der Vorlesungszeit.

Die Übungen zu Übersetzerbau 3 stellen eine Ergänzung zur
Vorlesung dar. In der Vorlesung wird unter anderem die
Architektur und Funktionsweise einer virtuellen Maschine
beleuchtet. In den Übungen soll dies praktisch umgesetzt werden.
Hierzu sollen die Studenten in einer Blockveranstaltung eine
kleine virtuelle Maschine selbst implementieren. Den Anfang
bildet das Einlesen des Byte-Codes und am Ende soll ein
funktionsfähiger optimierender Just-in-Time-Übersetzer entstehen.

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt: https://www.studon.fau.de/crs4533480.html

1. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
Blockveranstaltung Mo, 09:00 - 18:00 04.03.2024 - 08.03.2024
  • Tobias Heineken
  • Julian Brandner
  • Florian Mayer
11302.02.135

Übungen zu Grundlagen des Übersetzerbaus

Titel Übungen zu Grundlagen des Übersetzerbaus
Kurztext inf2-ueb-ex
Turnus des Angebots nur im Wintersemester
Semesterwochenstunden 2

Im Rahmen der Übungen werden die in der Vorlesung vorgestellten Konzepte und Techniken zur Implementierung eines Übersetzers in die Praxis umgesetzt. Ziel der Übungen ist es, bis zum Ende des Semesters einen funktionsfähigen Übersetzer für die Beispiel-Programmiersprache e2 zu implementieren.

Die hierfür nötigen zusätzlichen Kenntnisse (z.B. Grundlagen des Assemblers für x86-64) werden in den Tafelübungen vermittelt.

Die im Laufe des Semesters zu erreichenden Meilensteine sind im UnivIS-Eintrag der Vorlesung aufgelistet.

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt: https://www.studon.fau.de/crs4533479.html

1. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Mo, 14:15 - 15:45 16.10.2023 - 05.02.2024 01.01.2024
25.12.2023
  • Florian Mayer
11302.02.133

Im Rahmen der Übungen werden die in der Vorlesung vorgestellten Konzepte und Techniken zur Implementierung eines Übersetzers in die Praxis umgesetzt. Ziel der Übungen ist es, bis zum Ende des Semesters einen funktionsfähigen Übersetzer für die Beispiel-Programmiersprache e2 zu implementieren.

Die hierfür nötigen zusätzlichen Kenntnisse (z.B. Grundlagen des Assemblers für x86-64) werden in den Tafelübungen vermittelt.

Die im Laufe des Semesters zu erreichenden Meilensteine sind im UnivIS-Eintrag der Vorlesung aufgelistet.

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt: https://www.studon.fau.de/crs4533479.html

2. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Fr, 08:15 - 09:45 20.10.2023 - 09.02.2024 29.12.2023
05.01.2024
  • Sascha Hofmann
11302.02.133

Im Rahmen der Übungen werden die in der Vorlesung vorgestellten Konzepte und Techniken zur Implementierung eines Übersetzers in die Praxis umgesetzt. Ziel der Übungen ist es, bis zum Ende des Semesters einen funktionsfähigen Übersetzer für die Beispiel-Programmiersprache e2 zu implementieren.

Die hierfür nötigen zusätzlichen Kenntnisse (z.B. Grundlagen des Assemblers für x86-64) werden in den Tafelübungen vermittelt.

Die im Laufe des Semesters zu erreichenden Meilensteine sind im UnivIS-Eintrag der Vorlesung aufgelistet.

Die Materialien zur Lehrveranstaltung werden über StudOn bereitgestellt: https://www.studon.fau.de/crs4533479.html

3. Parallelgruppe

Zeitpunkt Startdatum - Enddatum Ausfalltermin Durchführende/-r Bemerkung Raum
wöchentlich Fr, 10:15 - 11:45 20.10.2023 - 09.02.2024 29.12.2023
05.01.2024
  • Tobias Heineken
11302.02.133

Betreute Examensarbeiten

Alphabetisch sortiert im UnivIS