University of Warsaw - Central Authentication System
Strona główna

Compiler construction

General data

Course ID: 1000-217bMRJ
Erasmus code / ISCED: 11.304 The subject classification code consists of three to five digits, where the first three represent the classification of the discipline according to the Discipline code list applicable to the Socrates/Erasmus program, the fourth (usually 0) - possible further specification of discipline information, the fifth - the degree of subject determined based on the year of study for which the subject is intended. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title: Compiler construction
Name in Polish: Metody realizacji języków programowania
Organizational unit: Faculty of Mathematics, Informatics, and Mechanics
Course groups: (in Polish) Grupa fundamentalnych przedmiotów systemowych dla informatyki magisterskiej
(in Polish) Grupa przedmiotów obowiązkowych dla informatyki magisterskiej-specjalność Języki programowania
Elective courses for Computer Science and Machine Learning
Obligatory courses for 1st grade 2nd stage Computer Science
ECTS credit allocation (and other scores): 9.00 Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.

view allocation of credits
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 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.

Classes in period "Winter semester 2024/25" (past)

Time span: 2024-10-01 - 2025-01-26
Selected timetable range:
Go to timetable
Type of class:
Classes, 30 hours more information
Lab, 30 hours more information
Lecture, 30 hours more information
Coordinators: Marcin Benke
Group instructors: Marcin Benke, Jacek Chrząszcz, Maciej Matraszek, Łukasz Sznuk, Daria Walukiewicz-Chrząszcz, Artur Zaroda
Students list: (inaccessible to you)
Credit: Examination

Classes in period "Winter semester 2025/26" (future)

Time span: 2025-10-01 - 2026-01-25

Selected timetable range:
Go to timetable
Type of class:
Classes, 30 hours more information
Lab, 30 hours more information
Lecture, 30 hours more information
Coordinators: Marcin Benke
Group instructors: Marcin Benke, Jacek Chrząszcz, Łukasz Sznuk, Daria Walukiewicz-Chrząszcz
Students list: (inaccessible to you)
Credit: Course - Examination
Lecture - Examination
Course descriptions are protected by copyright.
Copyright by University of Warsaw.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
contact accessibility statement site map USOSweb 7.1.2.0-bc9fa12b9 (2025-06-25)