Compiler Construction (in English)
VYPa Acad. year 2022/2023 Winter semester 5 credits
This course discusses the construction of compilers in detail. This discussion concentrates on the following three topics: (I) Advanced topics of classical compilers: LR-table construction, general precedence analysis, general methods of syntax analysis, advanced methods of optimization. (II) Principles of parallel compilers: parallel compiler structure, fundamental methods of parallel syntax analysis, basic models of parallel translation. (III) Formal translation models and their properties: transducers, translation grammars, properties of syntax directed translation, formal language properties relevant to compilers, modern translation models.
Language of instruction
- 39 hrs lectures
- 13 hrs projects
- 55 pts final exam (written part)
- 15 pts mid-term test (written part)
- 30 pts projects
Course Web Pages
Subject specific learning outcomes and competences
Ability of an advanced compiler construction including parallel compiler. Deep familiarity with the theory and practice of programming language translation.
General knowledge of formal models for translation and their applications.
Thorough grasp of compiler construction, including modern parallel compiler construction. Deep familiarity with the theory behind the translation of programming languages.
Why is the course taught
Maintaining a balance between a theoretical and practical approach to this important subject, VYPa represents a master-level class about compiler writing. From a theoretical viewpoint, it introduces mathematical models, such as automata and grammars, which underlie compilation and its phases. Based on these models, the class details the concepts, methods, and techniques employed in compiler design in a clear and easy-to-follow way.
From a practical point of view, the class describes how compilation techniques are implemented. While discussing various compilation techniques, the class demonstrates their implementation in a step-by-step way. In addition, the class presents many detailed examples and computer programs to emphasize the applications of the compiler algorithms.
After taking this class, students should understand the compilation process, be able to write a real compiler, and easily follow advanced books on the subject.
Prerequisite knowledge and skills
Basic knowledge of discrete mathematics.
- D. Grune: Modern Compiler Design, 2nd edition. Springer, 2016.
- R. Wilhelm, H. Seidl: Compiler Design: Virtual Machines. Springer, 2010.
- C.L. Jeffery: Build Your Own Programming Language: A programmer's guide to designing compilers, interpreters, and DSLs for solving modern computing problems. Packt Publishing, 2021.
- J. I. Moore: Introduction to Compiler Design: An Object-Oriented Approach Using Java, 2nd edition. SoftMoore Consulting, 2020.
- D. Thain: Introduction to Compilers and Language Design, 2nd edition. Independently published, 2020.
- T.Æ. Mogensen: Introduction to Compiler Design, 2nd edition. Springer, 2017.
- D. Watson: A Practical Approach to Compiler Construction. Springer, 2017.
- A. Meduna, P. Zemek: Regulated Grammars and Automata. Springer, 2014.
- A. Meduna: Elements of Compiler Design. Taylor & Francis, 2008.
- K.D. Cooper, L. Torczon: Engineering a Compiler, 3rd edition. Morgan Kaufmann, 2022.
A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools, 2nd edition. Pearson Education, 2006.
Syllabus of lectures
- Introduction: compiler structure.
- Deterministic bottom-up syntax analysis: LR table construction.
- Deterministic bottom-up syntax analysis: general precedence analysis.
- General syntax analysis: important backtrack parsing methods.
- Advanced optimization.
- Parallel compilers: parallel compiler structure.
- Parallel syntax analysis: principles.
- Deterministic methods of parallel top-down syntax analysis.
- Deterministic methods of parallel bottom-up syntax analysis.
- Parallel code generation.
- Modern formal tools for language specification: regulated and parallel models.
- Formal tools for language translation: transducers and translation grammars.
- Expected future trends; summary; conclusion.
Syllabus - others, projects and individual work of students
- Making an advanced compiler.
- Preparation and presentation of a selected topic about compilers.
- Mid-term exam in written form - 15 points
- Evaluated project(s) - 30 points
- Final written examination - 55 points
In case of illness or another serious obstacle, the student should inform the faculty about that and subsequently provide the evidence of such an obstacle. Then, it can be taken into account within evaluation:
- The student can ask the responsible teacher to extend the time for the project assignment.
- If a student cannot attend the mid-term exam, (s)he can ask to derive points from the evaluation of his/her first attempt of the final exam.
- If a student cannot attend the defense of the project and the other team members agree with that (s)he can earn the same points from the project defence as for present members.
|Mon||lecture||1., 2., 3., 4., 5., 8., 10., 11. of lectures||A112||11:00||13:50||9999||1EIT 1MIT 2EIT 2MIT INTE||NMAT xx||Meduna|
|Mon||lecture||6., 9., 12. of lectures||A112||11:00||13:50||9999||1EIT 1MIT 2EIT 2MIT INTE||NMAT xx||Křivka|
|Mon||lecture||7., 13. of lectures||A112||11:00||13:50||9999||1EIT 1MIT 2EIT 2MIT INTE||NMAT xx||Křivka, Meduna|
|Mon||exam||2022-12-19||C228||12:50||14:50||VYPa: Early Term of Exam|
|Thu||exam||2023-01-26||A113||12:00||14:00||VYPa: 1. oprava|
|Thu||exam||2023-01-12||E104||13:00||14:50||VYPa: Regular Term|
|Fri||exam||2023-02-03||C229||09:00||11:00||VYPa: 2. oprava|
Course inclusion in study plans
- Programme IT-MGR-2, field MBI, MBS, MGM, MIN, MPV, MSK, any year of study, Elective
- Programme IT-MGR-2, field MIS, any year of study, Compulsory-Elective group F
- Programme IT-MGR-2, field MMM, any year of study, Compulsory
- Programme IT-MGR-2 (in English), field MGMe, any year of study, Compulsory-Elective group I
- Programme MIT-EN (in English), any year of study, Compulsory
- Programme MITAI, field NADE, NBIO, NCPS, NEMB, NEMB up to 2021/22, NGRI, NHPC, NIDE, NISD, NISY, NISY up to 2020/21, NMAL, NNET, NSEC, NSEN, NSPE, NVER, NVIZ, any year of study, Elective
- Programme MITAI, field NMAT, any year of study, Compulsory