Compiler construction

obligatory courses

1000-216bJPP

1000-214bJAO

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.

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.

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

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).

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.