Compiler construction
General data
Course ID: | 1000-217bMRJ |
Erasmus code / ISCED: |
11.304
|
Course title: | Compiler construction |
Name in Polish: | Metody realizacji języków programowania |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
Obligatory courses for 1st grade 2nd stage Computer Science |
ECTS credit allocation (and other scores): |
9.00
|
Language: | English |
Type of course: | obligatory courses |
Prerequisites (description): | 1000-216bJPP 1000-214bJAO |
Short description: |
An overview of fundamental problems and techniques of interpreter and compiler construction. The central topics of the course are methods and tools of semantic analysis of programs as well as code generation and optimisation for various platforms (JVM, LLVM, assembly). The course builds upon knnowledge and abilities from the course "Programming Languages and Paradigms" (or an equivalent course). Completing the course should enable students to create a compiler for a simple programming language. |
Full description: |
1. Lexical and syntax analysis (2 weeks): top-down and bottom-up methods; LL(1) grammars and recursive descent parsers; LR(k), SLR and LALR grammars and automata construction for them. 2. Semantic analysis (2 weeks): symbol table, name binding, type control. 3. Run time environment (1-2 weeks): run time structures, memory orgnisation, subroutine implementation. 4. Code generation: intermediate languages: quadruples, JVM, SSA form and LLVM. 5. The Java Virtual Machine and code generation for it. 6. Static Single Assignment and the LLVM. 7. The x86 architecture and assembly. 8. Code optimisation (2 weeks): basick blocks graph, flow analysis; register allocation; code improvement methods: constant folding, common subexpression elimination, dead code elimination, loop optimisation, peephole method. 9. Exception handling: exception semantics, finding exception handlers, stack unwinding. 10. Memory management: allocation and deallocation; garbage collection: reference counting, copying, mark and sweep, synchronous and asynchronous methods, conservative garbage collection. 11. Implementing functional languages: challenges; closures, combinators and supercombinators; graph reduction, the G-machine and its variants; lazy evaluation, lambda-lifting. |
Bibliography: |
K.Cooper, L. Torczon, Engineering a Compiler, A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, Compilers: Principles, Techniques, and Tools, 2/E. http://moodle.mimuw.edu.pl |
Learning outcomes: |
Knowledge Knows problems, techniques and tools related to compiler construction (K_W03), in particular: ● has advanced knowledge of syntax analysis problems and methods , ● has advanced knowledge of semantic analysis problems and methods , ● understands structure and functionality if runtime environments, ● knows examples of intermediate languages , ● knows fundamental problems and techniques of code generation ● knows methods of code optimisation ● has advanced knowledge of memory management techniques, including garbage collection problems and techniques. Skills Is able to implement a compiler for a programming language of medium complexity (K_U03). Social competence Understands the need for systematic work on long-term projects (K_K03). |
Assessment methods and assessment criteria: |
NB: may be overridden by rules for particular learning cycle - check these first. Exam 50%, lab projects 40%, midterm 10%. For main exam admission a minimum of 50% of lab credits and 50% of midterm is required. Fulfilling these requirements is not necessary for reexam admission - a minimum of 30% lab credits is required instead; however lab and midterm credits influence the final mark. |
Classes in period "Winter semester 2023/24" (past)
Time span: | 2023-10-01 - 2024-01-28 |
Navigate to timetable
MO WYK
TU W CW
CW
LAB
LAB
TH CW
CW
LAB
LAB
LAB
FR LAB
CW
LAB
|
Type of class: |
Classes, 30 hours
Lab, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Marcin Benke | |
Group instructors: | Marcin Benke, Jacek Chrząszcz, Konrad Iwanicki, Maciej Matraszek, Łukasz Sznuk, Daria Walukiewicz-Chrząszcz, Artur Zaroda | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Classes in period "Winter semester 2024/25" (future)
Time span: | 2024-10-01 - 2025-01-26 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
Classes, 30 hours
Lab, 30 hours
Lecture, 30 hours
|
|
Coordinators: | Marcin Benke | |
Group instructors: | Marcin Benke, Jacek Chrząszcz, Łukasz Sznuk, Daria Walukiewicz-Chrząszcz, Artur Zaroda | |
Students list: | (inaccessible to you) | |
Examination: | Examination |
Copyright by University of Warsaw.