MIF 1.5: Concepts of Programming Languages (Winter 2025/26)

Kursbeschreibung

Der Compiler ist das wichtigste Werkzeug in der Informatik. In der Königsdisziplin der Informatik schließt sich der Kreis, hier kommen die unterschiedlichen Algorithmen und Datenstrukturen und Programmiersprachenkonzepte zur Anwendung.

In diesem Modul geht es um ein fortgeschrittenes Verständnis für interessante Konzepte im Compilerbau sowie um grundlegende Konzepte von Programmiersprachen und -paradigmen. Wir schauen uns dazu relevante aktuelle Tools und Frameworks an und setzen diese bei der Erstellung eines Bytecode-Compilers für unterschiedliche Programmiersprachen für die Java-VM oder WASM ein.

Überblick Modulinhalte

1. Lexikalische Analyse: Scanner/Lexer
   • Reguläre Sprachen
   • Klassisches Vorgehen: RegExp nach NFA (Thompson’s Construction), NFA nach DFA (Subset Construction), DFA nach Minimal DFA (Hopcroft’s Algorithm)
   • Manuelle Implementierung, Generierung mit ANTLR oder Flex
2. Syntaxanalyse: Parser
   • Kontextfreie Grammatiken (CFG), Chomsky
   • LL-Parser (Top-Down-Parser)
     • FIRST, FOLLOW
     • Tabellenbasierte Verfahren, rekursiver Abstieg
     • LL(1), LL(k), LL(*)
     • Umgang mit Vorrang-Regeln, Assoziativität und linksrekursiven Grammatiken
   • LR-Parser (Bottom-Up-Parser)
     • Shift-Reduce
     • LR(0), SLR(1), LR(1), LALR
   • Generierung mit ANTLR oder Bison
3. Semantische Analyse und Optimierungen
   • Symboltabellen
     • Namen und Scopes
     • Typen, Klassen, Polymorphie
   • Attributierte Grammatiken: L-attributed vs. R-attributed grammars
   • Typen, Typ-Inferenz, Type Checking
   • Datenfluss- und Kontrollfluss-Analyse
   • Optimierungen: Peephole u.a.
4. Zwischencode: Intermediate Representation (IR), LLVM-IR
5. Interpreter
   • AST-Traversierung
   • Read-Eval-Schleife
   • Resolver: Beschleunigung der Interpretation
6. Code-Generierung, Bytecode/VM
   • Speicherlayout
   • Erzeugen von Bytecode
   • Ausführen in einer Virtuellen Maschine
   • Garbage Collection
7. Programmiersprachen: Ruby, Prolog, Haskell, Lisp und die Auswirkungen der Konzepte auf den Compiler/Interpreter und die Laufzeitumgebung

Team

• BC George
• Carsten Gips (Sprechstunde nach Vereinbarung)

Kursformat

| Seminaristischer Unterricht (2 SWS) | Praktikum (3 SWS) | |:------------------------------------|:-----------------------------| | Di, 09:45 - 11:15 Uhr (Zoom) | Di, 11:30 - 13:45 Uhr (Zoom) |

Durchführung des seminaristischen Unterrichts als Flipped Classroom (Carsten) bzw. als reguläre Vorlesung (BC). Zugangsdaten Zoom siehe ILIAS.

Fahrplan

Hier finden Sie einen abonnierbaren Google Kalender mit allen Terminen der Veranstaltung zum Einbinden in Ihre Kalender-App.

| Woche | Sem. Unterricht: Selbststudium (Vorbereitung) | Sem. Unterricht: Gemeinsame Sitzung | Praktikum | Edmonton/Minden-Meetings | |:---|:---|:---|:---|:---| | W01 / KW41 | Überblick | Sprachen | Anwendungen | Orga (Zoom) | | | | W02 / KW42 | | Reguläre Sprachen | CFG | | | W03 / KW43 | Lexer (Implementierung) | LL-Parser | LL-Parser (Implementierung) | | | W04 / KW44 | | LR-Parser | Vortrag/Diskussion Compiler: Parsergeneratoren (ANTLR, Treesitter, Flex&Bison, …) | | | W05 / KW45 | Symboltabellen: Überblick | Scopes | Funktionen | Klassen | Vortrag/Diskussion Compiler: LALR, PEG, Pratt, Combinators | | | W06 / KW46 | | Vortrag/Diskussion Compiler: Type Checking, Hindley-Milner | Kurzvortrag/Diskussion PL-Feature: OOP (Gabbrielli & Martini, Kap. 10) | | | W07 / KW47 | Syntaxgesteuerte Interpreter | AST-basierte Interpreter 1 | AST-basierte Interpreter 2 | Kurzvortrag/Diskussion PL-Feature: FP (Gabbrielli & Martini, Kap. 11) | | | W08 / KW48 | | Vortrag/Diskussion Compiler: VM & Bytecode | Kurzvortrag/Diskussion PL-Feature: LP (Gabbrielli & Martini, Kap. 12) | | | W09 / KW49 | | Sprechstunde | Kurzvortrag/Diskussion PL-Feature: CP (Gabbrielli & Martini, Kap. 13) | Vortrag/Diskussion Compiler: Garbage Collection | Vortrag/Diskussion Compiler: JIT | Mo, 01.12., 18:00 - 19:00 Uhr (online): Edmonton/Minden: Minden Presentations | | W10 / KW50 | | Optimierung und Datenfluss- und Kontrollflussanalyse | Meilenstein 0: Kick-Off | Mo, 08.12., 18:00 - 19:00 Uhr (online): Edmonton/Minden: Edmonton Presentations | | W11 / KW51 | | Sprechstunde | Freies Arbeiten | | | - / KW52 | | Weihnachtspause | | | | - / KW01 | | Weihnachtspause | | | | W12 / KW02 | | Sprechstunde | Meilenstein 1: DSL | | | W13 / KW03 | | Sprechstunde | Freies Arbeiten | | | W14 / KW04 | | Meilenstein 2: Vorträge | Meilenstein 2: Vorträge DSL-Projekt | |

Prüfungsform, Note und Credits

Mündliche Prüfung plus Studienleistung, 10 ECTS

• Studienleistung: “Portfolio”

Kriterien je Team (2 Personen):

1. Aktive Teilnahme an beiden Edmonton/Minden-Terminen (zus. mit 4.)
2. 1x Kurzvortrag plus Diskussionsleitung “PL Features” (Gabbrielli & Martini) a 20 Minuten
3. 1x Vortrag “Compiler” (Parser Generatoren, Parser, Type Checking, VM/Bytecode) a 60 Minuten
4. 1x Vortrag Edmonton (20 Minuten pro Team)
5. Durchführung DSL-Projekt und Einhaltung der Meilensteine
6. Vortrag pro Team am Ende (W14) a 30 Minuten

Je Kriterium: Erstellen eines Post Mortems pro Studienleistung und Abgabe als Lerntagebuch im ILIAS^1

• Gesamtnote: Mündliche Prüfung (einzeln, ca. 45 Minuten)

Materialien

1. “Compilers: Principles, Techniques, and Tools”. Aho, A. V. und Lam, M. S. und Sethi, R. und Ullman, J. D. and Bansal, S., Pearson India, 2023. ISBN 978-9-3570-5488-1. Online über die O’Reilly-Lernplattform.
2. “Crafting Interpreters”. Nystrom, R., Genever Benning, 2021. ISBN 978-0-9905829-3-9. Online.
3. “Engineering a Compiler”. Torczon, L. und Cooper, K., Morgan Kaufmann, 2012. ISBN 978-0-1208-8478-0. Online über die O’Reilly-Lernplattform.
4. “Introduction to Compilers and Language Design”. Thain, D., 2023. ISBN 979-8-655-18026-0. Online.
5. “Writing a C Compiler”. Sandler, N., No Starch Press, 2024. ISBN 978-1-0981-8222-9. Online über die O’Reilly-Lernplattform.
6. “Seven Languages in Seven Weeks”. Tate, B.A., Pragmatic Bookshelf, 2010. ISBN 978-1-93435-659-3. Online über die O’Reilly-Lernplattform.

Förderungen und Kooperationen

Kooperation mit University of Alberta, Edmonton (Kanada)

Über das Projekt “We CAN virtuOWL” der Fachhochschule Bielefeld ist im Frühjahr 2021 eine Kooperation mit der University of Alberta (Edmonton/Alberta, Kanada) im Modul “Compilerbau” gestartet.

Wir freuen uns, auch in diesem Semester wieder drei gemeinsame Sitzungen für beide Hochschulen anbieten zu können. (Diese Termine werden in englischer Sprache durchgeführt.)

LICENSE

Unless otherwise noted, this work by BC George, Carsten Gips and contributors is licensed under CC BY-SA 4.0. See the credits for a detailed list of contributing projects.

^{_{Last modified: 459b108 (orga: improve wording towards Post Mortem, 2025-09-09)}}

[^1]: Post Mortem: Jede Person beschreibt individuell(!) für jede selbst durchgeführte Studienleistung die Bearbeitung des jeweiligen Kriteriums bzw. die Teilnahme am Edmonton/Minden-Meeting zurückblickend mit jeweils mind. 200 bis max. 400 Wörtern (Nutzlast; Überschriften und Links zählen nicht mit). Gehen Sie dabei aussagekräftig und nachvollziehbar auf folgende Punkte ein:

1.  Zusammenfassung: Was wurde gemacht?
2.  Details: Kurze Beschreibung besonders interessanter Aspekte.
3.  Reflexion: Was war der schwierigste Teil? Wie haben Sie dieses
    Problem gelöst?
4.  Reflexion: Was haben Sie gelernt oder (besser) verstanden?
5.  Team: Mit wem haben Sie zusammengearbeitet?
6.  Link zu Ihrem Repo mit den relevanten Artefakten (Lösung, Slides
    für den Vortrag, …).

Für die Edmonton/Minden-Meetings passen Sie bitte die Punkte (1) bis
(4) und (5) entsprechend inhaltlich an, (6) entfällt.

Die Post Mortems geben Sie bitte zusammengefasst als Lerntagebuch
bis spätestens zur letzten gemeinsamen Sitzung im
[ILIAS](https://www.hsbi.de/elearning/goto.php?target=exc_1421692&client_id=FH-Bielefeld)
ab.

Siehe auch
https://github.com/Compiler-CampusMinden/CPL-Vorlesung-Master-W25/discussions/2.