Introduction

Welcome to the course in Compilers and Execution Environments!

In this course, you will learn how a compiler works. You will learn about compiler theory, for instance regular expressions, parsing theory, optimization algorithms, code generation strategies, garbage collection, and more. Moreover, you will gain significant practical experience in designing and implementing a complete compiler from scratch.

Learning Outcomes

The complete syllabus can be found here. In summary, the learning outcomes are as follows.

After passing the course, the student should be able to

use methods for lexical, syntactic and semantic analysis
use methods for generation of machine code
use methods for optimizing programs
give an account of common components in execution environments

in order to

obtain an understanding of how a programming language is implemented as well as for the general theories that are used and how these can be applied.

Modules

The course is divided into three modules. Each module is two weeks long and covers a specific area:

Module 1 (weeks 45 and 46): Lexical analysis, syntax analysis, and semantic analysis.
The goal of module 1 is to comprehend, design, and implement the front end of a compiler, including lexing, parsing, and interpretation.
Module 2 (weeks 47 and 48): Code generation and runtime environments.
The goal of module 2 is to compile complete unoptimized Cigrid programs to x86 machine code.
Module 3 (weeks 49 and 50): Program analysis and optimizations.
The goal of module 3 is to perform various optimizations of your compiler, including intermediate code optimization and register allocation.

The first week (week 44) will be a "getting started week", where the student gets familiar with the environments, gets an overview of compilers, and takes a crash course in typed functional programming.

Learning Activities and Examination

Each module consists of the following learning activities (marked with LA) and formative examination tasks (marked with ET):

Lectures (LA). Each module starts with a number of lectures. All lectures will be given physically at KTH, either in Kista or on Campus (please see the schedule), but they will also be live streamed using Zoom. The lectures will not be recorded. We highly recommend that you attend the lectures in person.
Videos (LA). There will be short videos available that explain certain specific areas of the course. The videos are not lecture recordings, but short videos dedicated to specific topics. This includes both theoretical concepts (algorithms, formalisms etc.) and practical aspects (programming etc.). Additional videos will be added on request.
Hacking sessions (LA). Each week, there are two in-person hacking sessions (please see the schedule). During these in-person sessions (not online), you will be able to chat with fellow students and to pose questions to teaching assistants.
Online office hours (LA). Each week, we will have online office hour possibilities, where students can contact teaching assistants, and get help over Zoom.
Assignments (LA/ET). During the two weeks modules, you will work independently (not in groups) on different design and implementation tasks. You will submit your tasks continuously to the course Git system. The deadlines for submitting all tasks are shown on the page "Important Deadlines".
Peer reviewing (LA/ET). During the beginning of the week after a module, you will be given the task to peer review the code and the solutions of another fellow student. As part of this peer reviewing, you provide comments and written questions about the other student's work.
Seminars (LA/ET). The week after each module, after the peer reviewing task, you will participate in a seminar, where you will present your tasks and answer questions from a teaching assistant and the peer reviewing student. There will be two to three students presenting during each seminar. The seminars will take place over Zoom and there will be individual bookings of these time slots.

There will be extra retake opportunities after Christmas.

Grading

According to the syllabus, there is one course part that is reported into LADOK.

DAT1 - Computer based exam, 7.5 credits, Grading scale: A, B, C, D, E, FX, F

All examination will be done using: (i) the assignments (ii) peer reviewing, and (iii) seminars. Hence, there is no written exam at the end of the course.

Each of the three modules are graded with one of the following grades:

Satisfactory (S): The student has fulfilled the following for the module:
- All assignments marked as (S) have been submitted to the Git correction system and all automatic tests pass.
- A teaching assistant has corrected tasks for (S) that cannot be automatically corrected and the results are pass.
- The student has sent in a peer reviewing assessment that has been given the grade pass by a teaching assistant (if applicable).
- The student has participated in a complete seminar, where they have acted as an opponent and asked questions based on the peer review.
- The student has presented their solution on a seminar, defended the implementation, and explained the solution in a satisfactory manner. The teaching assistant for the seminar has given the student pass on the oral presentation.
Good (G): The student has fulfilled all criteria for (S) as well as submitted solutions to all assignments marked as (G). For all the tasks at level (G), the student has received a pass by either the automatic grading system or manually by a teaching assistant, or both.
Very Good (VG): The student fulfilled all criteria for (S) and (G), as well as submitted solutions to all assignments marked as (VG). For all the tasks at level (VG), the student has received a pass by either the automatic grading system or manually by a teaching assistant, or both.

Complementary work needed (C): The criteria for satisfactory (S) have not been fulfilled. The student need to do complementary work to pass.

The final grade (A, B, C, D, E, FX, F) is based on the overall grades of the three modules.

A student receives the deadline bonus if:

The student submits a solution to each module before its corresponding module deadline (i.e., deadlines before Christmas, both theory and code submissions), with only one exception: missing at most one deadline for one module (out of the four modules 0, 1, 2, and 3).
All four modules have a solution submitted by the final catch-up deadline in January (see the Important Dates page for the exact deadline).
The submitted solutions must be complete (all tests pass for the coding exercises, and the student has tried to answer all theory exercises), at least at level S.

Note that the deadline bonus is valid until the last deadline in May; that is, you can use this deadline bonus until the deadline in May to improve your grade. However, the deadline bonus cannot be used for coming course editions.

The final grade is computed as follows:

Grade A if received VG on all three modules. With a deadline bonus, only two VGs and one G is needed.
Grade B if received two VGs and one G. With a deadline bonus, only one VG and two Gs are needed.
Grade C if received one VG and two G. With a deadline bonus, only three Gs are needed.
Grade D if received at least two Gs and one S. With a deadline bonus, only at least one G and two Ss are needed.
Grade E if received at least three S.
Grade F or FX otherwise.

In practice, you cannot get F or FX, just a new deadline to do complementary work on a certain module.

After Christmas, the students have the possibility to complement their solutions for all three modules, and to receive higher grades on the different modules.

Note also that the teacher may ask for individual examination and presentation of exercises, if there are unclarities in submitted solutions, unclarities during seminar presentations, or indications of cheating attempts.

Teachers

Examiner

David Broman

Course Responsible

Philipp Haller

Lectures

Hacking Sessions and Seminars

Literature

The following is the recommended course book:

Keith D. Cooper & Linda Torczon. Engineering a Compiler. Third Edition, Morgan Kaufmann, 2022. Available online using your KTH account.
Andrew W. Appel. Modern compiler implementation in Java. Second Edition, Cambridge University Press, 2002. Available online using your KTH account.

Disability

If you have a disability, you may receive support from Funka.

Funka also recommends that you inform the teacher (in this case David Broman) regarding any needs you may have. Funka does not automatically inform teachers in courses.

Code of Honor

Please make sure that you are aware of and that you understand the KTH EECS Code of Honor.

Policy against Plagiarism

Note that all forms of cheating and plagiarism will be reported. Please see KTH's policy for handling plagiarism.

Programming assignments. You may discuss problems and solutions with anyone. You are not allowed to copy ANY code and submit it as part of your solution. You must create your own solutions from scratch.
Individual theory assignments. You are not allowed to discuss or publish any of the assignments. You are not allowed to get help from anyone or find a solution on the Internet.
Written text assignments. You are not allowed to copy, cut, or paste any text into your report that you have not produced. The only exception is if you quote text properly and give a citation to the original source.

Use of GitHub

Since all students are performing the same exercises in the course, you should not make any of the solutions to the exercises and your compiler solution publicly available during or after the course. This includes making it public on Github, on websites, etc. If you, later on, are applying for a job, it is OK to share it with a potential employer or to share it with other people privately (after the course, as long as it is not for future students). The key thing is to not make it publicly available.

Course Analyses and Feedback

The following course analyses are available:

We think it is very important to continuously improve our course, especially now when it is the first time that the course is given. Therefore, we really appreciate all constructive feedback that we can get. In this course, we collect and analyze feedback in the following ways:

Personal Feedback

We really appreciate if you give us direct and constructive feedback. Please, send us an email (dbro@kth.se and phaller@kth.se) with your feedback, or let's meet up for a cup of coffee!

Battery Evaluation

At the break of one of the lectures, students write down (anonymously) pros and cons of the course. We call this a battery evaluation since the physical answer papers look like batteries (+ and - lists on each part of the paper). The feedback is then collected, summarized, and analyzed by the course responsible. The analysis is presented in one of the following lectures. The benefit of this kind of early and direct feedback during the course is that actions can be taken for you, in this course edition.

Web-based Course Evaluation

We perform standard web-based course evaluations after the course. This feedback will be used to improve next year's course edition. The course analysis is based on this course evaluation.

Course Committee (Kursnämnd)

A course committee is a group of students that meet up with me in the middle and at the end of the course. The purpose is to give concrete oral feedback informally. If you are interested in being part of the course committee, please let me know at the first lecture.

FID3006

FID3006 is the doctoral-level version of the compiler course. It follows the same structure as ID2202 but has an additional project assignment, as well as specific requirements for passing the three-course modules. More specifically, the differences are as follows:

Project assignment. In addition to the course modules (as presented in the course memo for ID2202), FID3006 students need to do small project assignments. In this project assignment, each student should individually do a small project related to compilers and programming languages. The exact topic is quite flexible and can preferably be related to the doctoral student's research. It must be some sort of investigation, provide clear research questions or problem statements, relate to state of the art, include a discussion, and explain the results. It can preferably include an implementation and experiments but can also be of a theoretical nature. Please talk to the examiner and discuss your topic before you start. As a result of the project work, you need to submit a term paper, 3-6 pages, excluding references, using the ACM acmart format, configured using sub format sigplan (two-column format). You submit the term paper by sending it attached in an email to dbro@kth.se. We will then decide on a time slot where you give a 20-minute oral presentation of your work. When both the term paper and the presentation are given a passing grade by the examiner, the project assignment has been passed.
Module grades for course modules 1, 2, and 3. In addition to passing the project assignment, FID3006 students need to get a grade VG (Very Good) on all three course modules. There is no deadline bonus, but we recommend that FID3006 students submit their work according to the schedule of the ID2202 course.

If nothing else is stated, to pass the course, both the project assignment and the course modules must have been finished before the next year's course round starts.