Studiegids

nl en

Compiler Construction

Vak
2023-2024

Admission requirements

This is a practical-intensive course, which involves lots of low-level systems programming. Mastering all this is also highly rewarding. Students are assumed to have taken courses in (advanced) programming, computer architecture/organization, computer networks, and operating systems at a BSc level.

Description

Computer programs in a higher programming language cannot be executed by a computer until they have been translated into lower-level code. In many cases this is done by a compiler.

In this course we learn how compilers convert source code into assembly code in several steps. We study the theory behind compilers with a keen eye on the practical aspects of building a compiler, and apply this in a series of assignments where we construct a C compiler, which outputs x86-64 code, executable on all modern Intel and AMD processors.

Topics covered during the lectures relate to the process of constructing a compiler, e.g.: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code generation, and code optimization.

Course Objectives

Gain insight into the functionality of the different phases of the compilation process, and how these phases are related to each other. Become familiar with the different steps in the construction of a compiler and the problems that arise with them

Timetable

You will find the timetables for all courses and degree programmes of Leiden University in the tool MyTimetable (login). Any teaching activities that you have sucessfully registered for in MyStudyMap will automatically be displayed in MyTimeTable. Any timetables that you add manually, will be saved and automatically displayed the next time you sign in.

MyTimetable allows you to integrate your timetable with your calendar apps such as Outlook, Google Calendar, Apple Calendar and other calendar apps on your smartphone. Any timetable changes will be automatically synced with your calendar. If you wish, you can also receive an email notification of the change. You can turn notifications on in ‘Settings’ (after login).

For more information, watch the video or go the the 'help-page' in MyTimetable. Please note: Joint Degree students Leiden/Delft have to merge their two different timetables into one. This video explains how to do this.

Mode of Instruction

The course is composed of two components:
1. Lectures given by the instructor, to setup course format, assignments, and to teach key topics in compiler construction. Quizzes will be held during these lectures, to assess the knowledge of the students on the theory.
2. Self-study Lab Assignments. Students are expected to work on the lab assignments autonomously, outside of the lectures. We also set up Lab Class, every week, after the lectures. In these labs, students ask questions and get practical help by teaching assistants. Please note, this is a hands-on course, where the lab constitutes a large part of the final grade.

For the practicals of this course, we implement a (subset-of-)C compiler, which outputs x86-64 instructions.

A regular compiler has 4 main stages to go from code to machine-understandable instructions: 1. Lexical analyzer stage 2. Syntaxtree generator stage 3. Intermediate code generator stage 4. Machine-code emitter stage

There are 6 practical assignments (including one bonus), each one about designing compiler functionality to treat various language features and compiler components and optimizations. Students will build each next stage on top of their previous stage implementations.

A base framework will be published to write your implementation in, featuring: - Basic code to start from. - Unit tests to verify implementation correctness. - An automated grading system.
The assignment will be in modern C++ (C++14).

Grading

The grade for this course is composed of two major components: the practical assignments (80%) and the quizzes (20%).

Practical assignments (Mandatory)

There are five mandatory and one bonus practical assignments and a mandatory final report, in which you will add features to the different parts of a compiler. After each assignment, you will be able to see the code you compiled running in on real-world machines based on the x86_64 architecture (e.g., Intel, AMD). Each assignment will be graded on a scale of 1-10.

Quizzes (Mandatory)

There is no exam, but there are four mandatory quizzes that will test general knowledge of compiler constructions, on the topics discussed in the course. These quizzes will be held on campus during the lectures.

Assessment method

The final grade of this course is composed of a large practical assignment (80%), in-class quizzes (20%).

The final practicum grade will be computed as follows: ((Assignment1 + Assignment2 + Assignment3 + Assignment4 + Assignment5 + Final Report)/6) * 0.9) + (Bonus * 0.2). To pass the course, the average for the practicum has to be >= 6.0. (This means that you can have grades lower than 6.0 for some components iff the average is above 6.0.). All assignments (except for the bonus) have to be submitted.

The in-class activity is composed of several quizzes. Participation in the quizzes is mandatory and the average of the quiz grades has to be sufficient (>= 6) to pass the course.

Course load

Total hours of study: 168 hrs.
Practical work: 100 hrs
Lectures & Tutoring: 20 hrs
Self-tuition: 48 hrs

Reading list

Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, second edition, Pearson New International Edition, 2013, ISBN 9781292024349.

Registration

From the academic year 2022-2023 on every student has to register for courses with the new enrollment tool MyStudyMap. There are two registration periods per year: registration for the fall semester opens in July and registration for the spring semester opens in December. Please see this page for more information.

Please note that it is compulsory to register for every exam and retake. Not being registered for a course means that you are not allowed to participate in the final exam of the course.

Extensive FAQ on MyStudymap can be found here.

Contact

Teachers of the course, Miguel Blom, Kristian Rietveld
Onderwijscoördinator Informatica, Education coordinator LIACS bachelors

Remarks

Voor meer informatie over Brightspace kun je op deze link klikken om de handleidingen van de universiteit te bekijken. Bij overige vragen of problemen kan contact opgenomen worden met de helpdesk van de universiteit Leiden.