Course details

Formal Languages and Compilers (in English)

IFJe Acad. year 2023/2024 Winter semester 5 credits

This course discusses formal languages and their models. Based on these models, it explains the construction of compilers. The lectures are organized as follows: (I) Basic notions: formal languages and their models, grammars, automata; compilers. (II) Regular languages and lexical analysis: regular languages and expressions, finite automata, lexical analyzer; symbol table. (III) Context-free languages and syntax analysis: context-free grammars, pushdown automata, deterministic top-down syntax analysis (recursive descent), the essence of deterministic bottom-up syntax analysis. (IV) Semantic analysis and code generation: intermediate code generation, optimization, code generation.


Course coordinator

Language of instruction



Credit+Examination (written)

Time span

  • 39 hrs lectures
  • 13 hrs projects

Assessment points

  • 55 pts final exam (written part)
  • 20 pts mid-term test (written part)
  • 25 pts projects




Course Web Pages

Learning objectives

Familiarity with formal languages and their models. Grasp of compiler construction.
Fundamental familiarity with the theory of formal languages. Ability of a compiler construction.

Recommended prerequisites

Prerequisite knowledge and skills

Discrete mathematics.

Study literature

  • Parsons, T. W.: Introduction to Compiler Construction. Freeman, New York, 1992.
  • Meduna, A.: Elements of Compiler Design. Taylor & Francis, New York, 2008.
  • Nystrom, R.: Crafting Interpreters.‎ Genever Benning, 2021, Available online

Fundamental literature

  • Meduna, A.: Formal Languages and Computation: Models and Their Applications. Taylor & Francis, New York, 2014.

Syllabus of lectures

  • Basics of formal languages: alphabet, strings, languages.
  • Introduction to compiler design: structure of a compiler.
  • Regular languages and their models: regular expressions, finite automata.
  • Variants of finite automata.
  • Lexical analysis: lexical analyzer, symbol table.
  • Context-free languages and their models: context-free grammars, pushdown automata.
  • Pushdown automata and general parsing.
  • Deterministic top-down syntax analysis: recursive descent.
  • Deterministic bottom-up syntax analysis: simple precedence analysis.
  • Chomsky hierarchy and the corresponding models. Remarks and summary.

Syllabus - others, projects and individual work of students

The task is to implement and document a program which, given a composition of functions, transforms it to an equivalent mathematical expression. 

Progress assessment

  • Mid-term exam - 20 points.
  • Project - 25 points.
  • Final exam - 55 points. To be allowed to take the final exam, the student has to obtain 20 points during the semester; out of these 20 points, at least five points have to be obtained from the project.




Exam prerequisites



Tue exam 2023-10-31 M104 12:0014:00 IFJe: Midterm
Tue lecture 1., 2., 3., 4., 6., 8., 9., 11., 12., 13. of lectures M104 M105 12:0014:5041 1EIT 2EIT INTE MITP-EN xx Meduna
Tue lecture 5., 7. of lectures M104 M105 12:0014:5041 1EIT 2EIT INTE MITP-EN xx Havel
Tue lecture 2023-11-21 M104 M105 12:0014:5041 1EIT 2EIT INTE MITP-EN xx Křivka
Wed exam 2024-01-24 A113 13:0014:50 IFJe: 3rd term
Wed exam 2023-12-13 M103 18:0020:00 IFJe: Early term of Final Exam
Thu exam 2024-01-04 E105 10:0011:50 IFJe: 1st term
Fri exam 2024-01-12 D105 08:3010:30 IFJe: 2nd term

Course inclusion in study plans

Back to top