inf409 - Formale Sprachen (Vollständige Modulbeschreibung)

inf409 - Formale Sprachen (Vollständige Modulbeschreibung)

Originalfassung Englisch PDF Download
Modulbezeichnung Formale Sprachen
Modulkürzel inf409
Kreditpunkte 6.0 KP
Workload 180 h
Einrichtungsverzeichnis Department für Informatik
Verwendbarkeit des Moduls
  • Master of Education (Gymnasium) Informatik (Master of Education) > Wahlpflichtmodule (Theoretische Informatik)
  • Zwei-Fächer-Bachelor Informatik (Bachelor) > Wahlpflicht Theoretische Informatik (30 KP)
Zuständige Personen
  • Lehrenden, Die im Modul (Modulverantwortung)
  • Lehrenden, Die im Modul (Prüfungsberechtigt)
Teilnahmevoraussetzungen
Kompetenzziele
Einführung in die Grundlagen der Syntaxanalyse und des Compilerbaus.

Fachkompetenzen
Die Studierenden:
  • benennen die Grundlagen der Syntaxanalyse und des Compilerbaus.
  • beschreiben die Komplexität von grundlegenden Syntaxanalysealgorithmen.
  • konstruieren nicht links-rekursiven Grammatiken und Grammatiken in Normalform
  • testen der LL(k) und LR(k)-Eigenschaft für kontextfreie Grammatiken
  • konstruieren LL(k)-Parsing und LR(k)-Parsing-Action und Goto Tabellen
  • wenden grundlegende Syntaxanalysealgorithmen an


Methodenkompetenzen
Die Studierenden:
  • erkennen Syntaxanalysealgorithmen als ein wichtiges Hilfsmittel in der Informatik


Sozialkompetenzen
Die Studierenden:
  • arbeiten in kleinen Gruppen an Lösungen von Aufgaben
  • präsentieren Lösungen von Aufgaben vor Gruppen


Selbstkompetenzen
Die Studierenden:
  • erlernen Ausdauer bei der Bearbeitung schwieriger Aufgaben
  • erlernen Präzision beim Aufschreiben von Lösungen
Modulinhalte
Die Veranstaltung führt in die Grundlagen der Syntaxanalyse ein und behandelt Backtrack Parsing (Top-Down & Bottom-Up Backtracking), tabellengestützte Parsing-Methoden (Cocke-Younger-Kasami & Earley) und One- Pass No Backtrack Parsing (LL(k) und LR(k)).
Literaturempfehlungen
  • J.E. Hopcroft, J.D Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn, Addison-Wesley (Deutschland), 1996.
  • A.V. Aho, J.D. Ullman: The Theory of Parsing, Translation, and Compiling, Vol. I: Parsing, Prentice-Hall, Englewood-Cliffs, New Jersey, 1972.
Links
Unterrichtssprache Deutsch
Dauer in Semestern 1 Semester
Angebotsrhythmus Modul im 2-Jahres-Zyklus
Aufnahmekapazität Modul unbegrenzt
Modulart je nach Studiengang Pflicht oder Wahlpflicht
Modullevel AS (Akzentsetzung / Accentuation)
Lehr-/Lernform V+Ü
Vorkenntnisse Theoretische Informatik II
Lehrveranstaltungsform Kommentar SWS Angebotsrhythmus Workload Präsenz
Vorlesung 2 SoSe 28
Übung 2 SoSe 28
Präsenzzeit Modul insgesamt 56 h
Prüfung Prüfungszeiten Prüfungsform
Gesamtmodul
Am Ende der Vorlesungszeit
Klausur oder mündliche Prüfung.