Stud.IP Uni Oldenburg
University of Oldenburg
31.05.2020 17:22:41
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
Faculty/Institute Department of Computing Science
Used in course of study
  • Bachelor's Programme Computing Science (Bachelor) >
  • Dual-Subject Bachelor's Programme Computing Science (Bachelor) >
  • Master of Education Programme (Gymnasium) Computing Science (Master of Education) >
Contact person
Module responsibility
Authorized examiners
Entry requirements
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 AS (Akzentsetzung / Accentuation)
Modulart je nach Studiengang Pflicht oder Wahlpflicht
Lern-/Lehrform / Type of program V+Ü
Vorkenntnisse / Previous knowledge Theoretische Informatik II
Course type Comment SWS Frequency Workload attendance
Lecture 2.00 SuSe 28 h
Exercises 2.00 SuSe 28 h
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