inf409 - Formal Languages (Complete module description)

inf409 - Formal Languages (Complete module description)

Original version English PDF Download
Module label Formal Languages
Modulkürzel inf409
Credit points 6.0 KP
Workload 180 h
Institute directory Department of Computing Science
Verwendbarkeit des Moduls
  • Dual-Subject Bachelor's Programme Computing Science (Bachelor) >
  • Master of Education Programme (Gymnasium) Computing Science (Master of Education) >
Zuständige Personen
  • Lehrenden, Die im Modul (module responsibility)
  • Lehrenden, Die im Modul (Prüfungsberechtigt)
Prerequisites
Skills to be acquired in this module
Introduction to syntactic analysis and compiler construction.

Professional competence
The students:
  • Know the fundamentals of syntactic analysis and compiler construction
  • Describe the complexity of fundamental syntactic analysis algortihms
  • Construct no-left-recursive-grammars and grammars in normal form
  • Test LL(k) and LR(k) characteristics of context-free grammars
  • Construct LL(k)-Parsing and LR(k)-Parsing-Action and GOTO tables
  • Apply basic syntax analysis algorithms


Methodological competence
The students:
  • Perceive syntax analysis algorithms as a essential tool in computer science


Social competence
The students:
  • Work together in small groups to solve problems
  • Present their solutions to groups of other students


Self-competence
The students:
  • Learn persistence in pursuing difficult tasks
  • Learn precision in writing down solutions
Module contents
The course introduces the fundamentals of syntax analysis and considers backtrack parsing (Top-Down & Bottom-Up Backtracking), tabular parsing methods (Cocke-Younger-Kasami & Earley) und One- Pass No Backtrack Parsing (LL(k) und LR(k)).
Literaturempfehlungen
  • J.E. Hopcroft, R. Motwani, J.D. Ullman: Formal Languages and Their Relation to Automata, Addison-Wesley, Boston, 2001.
  • A.V. Aho, J.D. Ullman: The Theory of Parsing, Translation, and Compiling, Vol. I: Parsing, Prentice-Hall, Englewood-Cliffs, New Jersey, 1972.
Links
Language of instruction German
Duration (semesters) 1 Semester
Module frequency im 2-Jahres-Zyklus
Module capacity unlimited
Form of instruction Comment SWS Frequency Workload of compulsory attendance
Lecture 2 SoSe 28
Exercises 2 SoSe 28
Präsenzzeit Modul insgesamt 56 h
Examination Prüfungszeiten Type of examination
Final exam of module
At the end of the lecture period
Written exam or oral exam