Course details
Formal Languages and Compilers (in English)
IFJe Acad. year 2022/2023 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.
Guarantor
Course coordinator
Language of instruction
Completion
Time span
- 26 hrs lectures
- 13 hrs exercises
- 13 hrs projects
Assessment points
- 55 pts final exam (written part)
- 20 pts mid-term test (written part)
- 25 pts projects
Department
Lecturer
Instructor
Course Web Pages
Subject specific learning outcomes and competences
Fundamental familiarity with the theory of formal languages. Ability of a compiler construction.
Learning objectives
Familiarity with formal languages and their models. Grasp of compiler construction.
Recommended prerequisites
- Discrete Mathematics (IDM)
Prerequisite knowledge and skills
Discrete mathematics. Basic programming skills.
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 http://craftinginterpreters.com.
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 of numerical exercises
- 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 a program which, given a composition of functions,transforms it to an equivalentmathematical 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.
Controlled instruction
Exam prerequisites
Student must have at least 20 points that she/he can achieve during the semester and at least 5 points must be from project implementation assessment.
Course inclusion in study plans
- Programme MIT-EN (in English), 1st year of study, Compulsory