Stud.IP Uni Oldenburg
University of Oldenburg
25.05.2022 20:32:10
inf409 - Formal Languages (Complete module description)
Original version English Download as PDF
Module label Formal Languages
Module code inf409
Credit points 6.0 KP
Workload 180 h
Institute directory Department of Computing Science
Applicability of the module
  • Bachelor's Programme Computing Science (Bachelor) > Akzentsetzungsbereich - Wahlbereich Informatik
  • Dual-Subject Bachelor's Programme Computing Science (Bachelor) > Wahlpflicht Theoretische Informatik (30 KP)
  • Master of Education Programme (Gymnasium) Computing Science (Master of Education) > Wahlpflichtmodule (Theoretische Informatik)
Responsible persons
Lehrenden, Die im Modul (Authorized examiners)
Lehrenden, Die im Modul (Module responsibility)
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

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)).
Reader's advisory
  • 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.
Language of instruction German
Duration (semesters) 1 Semester
Module frequency im 2-Jahres-Zyklus
Module capacity unlimited
Modullevel / module level AS (Akzentsetzung / Accentuation)
Modulart / typ of module je nach Studiengang Pflicht oder Wahlpflicht
Lehr-/Lernform / Teaching/Learning method V+Ü
Vorkenntnisse / Previous knowledge Theoretische Informatik II
Course type Comment SWS Frequency Workload of compulsory attendance
2 SuSe 28
2 SuSe 28
Total time of attendance for the module 56 h
Examination Time of examination Type of examination
Final exam of module
At the end of the lecture period
Written exam or oral exam