Compiler Construction 2021


Course code 5062COMP6Y
Format Lecture course with lab sessions and project work
Curriculum BSc Informatica
Block 4
Status Constrained choice
ECTS 6 credits
Language English
Study Guide Click here.
Objectives

To develop a profound understanding about the inner workings of compilers and the ability to design and implement compilers for any purpose.

Contents

As implementations of programming languages compilers are integral parts of any computing system software stack. The more general task of compilers to transform structured text from one format to another is ubiquitous in all areas of computer science. Step-by-step the course covers all aspects of modern compiler design and implementation: lexical and syntactical analysis, context/type checking and inference, high-level code transformations/optimisations, target code generation and the interplay between compilers and runtime/operating systems. A model programming language that exposes common imperative programming features, as found in languages such as C, Pascal or Java, serves as a case study throughout the course. Organised in the form of a software engineering project participants develop a fully-fledged compiler for this language targeting a virtual machine similar to the Java Virtual Machine.

  • Chapter 1: Introduction and Motivation
  • Chapter 2: Compilers at a Glance
  • Chapter 3: Lexicographic Analysis
  • Chapter 4: Syntactic Analysis
  • Chapter 5: Semantic Analysis
  • Chapter 6: Optimisation
  • Chapter 7: Code Generation
  • Chapter 8: Memory Management
Lecturer Dr Clemens Grelck
Assistants Simon Polstra
Lukas Miedema
Folkert van Verseveld
Tim Müller
Daan Kruis
Damian Frolich
Lectures Tue, 13-15
Wed, 13-15
See Datanose for all details.
Labs Tue, 15-17
Wed, 15-17
See Datanose for all details. During the first week of the course (lectures and labs) we will explain the project assignment and provide you with an in-depth introduction to the compiler construction framework used during the course. Your presence during these sessions is essential!!
Exam We have no written exam; the final grade is determined by assessment of the project and the weekly assignments.
Grading Compiler (60%), Report (10%), Assignments (30%)
You need a minimum grade of 5.0 in each category to pass the course!
Both the project and the weekly assignments are to be worked on (!) and submitted in groups of two students.
If we have reason to believe that the workload and contributions in a group are not reasonably equivalent, we reserve the right to conduct individual assessments.
Slides Slides will be made available on Canvas after each lecture.
Project

In the project we implement a fully-fledged compiler for a non-trivial model language named CiviC ("Civilised C"). The language combines essential ideas from C, Pascal and Fortran into a fairly simple language design that allows us to focus on essential concepts in compilation techniques rather than providing support a complete real world programming language. The complete language, including all extensions, features the usual structured programming constructs (loops and branches), modules with information hiding and separate compilation, nested function definitions with private scopes and, last not least, fully-fledged multi-dimensional arrays.
After lexicographic, syntactic and semantic analysis as well as some optimisation your compiler is supposed to generate code for the CiviC Virtual Machine CiviC-VM, a byte code interpreting virtual machine with many similarities to the Java-VM.
Your practical work will be supported by a fully-fledged compiler construction framework that has proven itself in a number of academic compiler projects. As documentation of this framework is unfortunately a bit scarce, your presence during the first labs, where a hands-on tutorial is given, is crucial.
The CiviC language manual and all further documentation are available on Canvas as well as here.
Project due date: April 6, 2020

Assignments The purpose of the theoretical assignments is to deepen your understanding of compiler construction and to complement the practical work undertaken in the project. There are a total of 6 assignments, i.e. each assignment counts for 5% of your final grade. The first assignment must be submitted individually; all further assignents in fixed groups of two. The assignments will be made available on Canvas.
Mailing Lists The UvA mailing list CoCo2020 serves as the primary medium of communication between lecturers and participants as well as among participants themselves. Subscription to the mailing list is controlled and restricted to participants of the course. Traffic on the mailing list is archived; access to the archives is restricted to participants. Please, subscribe!!
The UvA mailing list CoCo2020-Team serves as a convenient way to reach all members of the teaching team at once. Participants of the course are permitted to post to this mailing list, but are not subscribed to it.
Guest lectures

The course features two guest lectures by renowned industrial compiler experts. Each lecture is planned to take about 45 minutes including questions. Before or after the usual break we will pusrsue our regular programme.

March 9, 2021:
ir Marco Roodzant
Empero, Amsterdam:
Compiler Economics and Software Engineering

Abstract:
Compilers are a pain! In his talk, Marco will give a view on compilers from different angles. A bit of (Dutch) history, the compiler business and most about compiler economics, which can be directly related to software engineering. Some real industrial and open source communities cases will enlighten the talk, where also the (licensing) politics or religions that play a big role in the compiler arena will be touched.

Guest lecturer:
Marco Roodzant did his MSc at ACE on the topic of assembler generation in 1983 while studying electronics at Delft Technical University. Since then he has worked in the systems software arena, with engineering, standardisation, product marketing, consulting and commercial activities. Marco has been instrumental in the business development of the CoSy compiler development system and in earlier days of The ACE Unix system, the CADESE Software Engineering product and the ACE Benchmark Suite and publications. He now supports young high-tech companies to bring their unique new enabling technologies to international markets.

March 3, 2021
Dr Marcel Beemster
Solid Sands BV, Amsterdam:
C and C++ Compiler Testing for Safety

Abstract:
During this guest lecture we discuss topics such as the nature of C and C++ compiler testing, quality vs safety as in the ISO-26262 standard, the V-model versus modern software engineering techniques and, generally, challenges in compiler testing.

Guest lecturer:
Since he wrote his first professionally used assembler in 1985 Marcel Beemster has never stopped tinkering with compiler technology. In 1996 he received his PhD in Computer Science from the University of Amsterdam. He left the UvA in 1999 to work as a senior software engineer at ACE Associated Compiler Experts, where he contributed to the CoSy compiler development system. In 2014 he co-founded Solid Sands to focus on C and C++ compiler testing with SuperTest.

Background Material Bison Manual
Literature The course does not follow any specific text book. The following list summarises a number of interesting textbooks on various aspects of the course. While books are always a helpful source of background information, I do not expect participants of the course to buy any or all of these, nor do I receive revenues from any of these books.
  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Compilers: Principles, Techniques, and Tools, Addison Wesley, 2007.
  • Keith D. Cooper, Linda Torczon: Engineering a Compiler, Morgan Kauffmann, 2004.
  • Andrew W. Appel, Maia Ginsburg: Modern Compiler Implementation in C, Cambridge University Press, 2004.
  • D. Grune, H. Bal, C. Jacobs, K. Langendoen: Modern Compiler Design, John Wiley & Sons, 2000.
  • Randy Allen, Ken Kennedy: Optimizing Compilers for Modern Architectures, Morgan Kauffmann, 2000.

Valid HTML 4.01!     Valid CSS!             Dr Clemens Grelck