Compiler construction 1000-217bMRJ
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.
Type of course
Prerequisites (description)
Course coordinators
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 criteria
NB: may be overridden by rules for particular learning cycle - check these first.
Exam 50%, lab projects 34%, midterm+quizzes 16%. For main exam admission a minimum of 50% from lab projects and 50% of (midterm+quizzes) is required.
Fulfilling these requirements is not necessary for reexam admission - a minimum of 33% lab credits is required instead; lab and midterm credits influence the final mark.
Achieving 60% from lab+midterm+quizzes provides the right to get the final grade before the exam session, based on the sum of these points multiplied by a factor of 1.8.
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
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: