Compiler Construction

Course manual 2023/2024

Course content

As implementations of programming languages, compilers are integral parts of any computing system software stack. More generally, transforming structured text from one format to another is ubiquitous in all areas of computer science. This course covers all aspects of classical compiler design and implementation: lexical and syntactical analysis, context/type checking and inference, high-level code transformations/optimisations and target code generation. In additional guest lectures, industrial aspects of compiler construction are covered as well as some recent academic advances in the area.

A model programming language named CiviC serves as a case study throughout the course. The case study language exposes common imperative programming features, as found in languages such as C, Pascal or Java. The theory taught in the course is brought to practice in a compiler construction project. The goal of the project is to develop a fully-fledged compiler for the CiviC language targeting a stack-based virtual machine very similar to the Java Virtual Machine. The project is organised as a medium-scale software engineering project with milestones.

Study materials

Literature

• The course does not follow any specific text book. The following list summarises a number of interesting books 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, 2nd edition, 2011.
  • Andrew W. Appel, Maia Ginsburg: Modern Compiler Implementation in C, Cambridge University Press, 2004.
  • Dick Grune, Kees van Reeuwijk, Henri E. Bal, Ceriel J.H. Jacobs, Koen Langendoen: Modern Compiler Design, Springer, 2nd edition 2012.
  • Randy Allen, Ken Kennedy: Optimizing Compilers for Modern Architectures, Morgan Kauffmann, 2000.

Practical training material

• • CiviC language specification
  • Lecture slides
  • Tool chain documentation
  • Compiler Construction Framework documentation

Software

• • CiviC reference compiler
  • CiviC assembler
  • CiviC virtual machine
  • Compiler Construction Framework

Other

Objectives

• To develop a profound understanding about the inner workings of compilers.
• To develop the ability to design and implement compilers for varying purposes.

Teaching methods

• Hoorcollege
• Werkcollege
• Laptopcollege
• Zelfstudie
• Lecture
• Computer lab session/practical training
• Self-study
• Working independently on e.g. a project or thesis

Learning activities

Attendance

Programme's requirements concerning attendance (OER-B):

• For practical trainings and tutorials/seminars with assignments attendance is, in principle, obligatory. When students do not meet the requirements for attendance, this may lead to not finishing a course with a pass mark.
  

Additional requirements for this course:

Attendance during the lectures and labs is highly recommended, but strictly speaking not enforced by legal or organisational means. This is your responsibility!

As academic software, the compiler construction framework we use throughout the practical part of the course is not very well documented. We provide a live introduction during week 1. Attendance during these lectures and labs is essential for successfully passing the course. The framework has been developed by previous attendees of the course and can be taken as a source of inspiration for your own graduation project!

Assessment

Inspection of assessed work

The manner of inspection will be communicated via the digitial learning environment.

Feedback for the weekly assignments is given during the labs including example solutions. For individual feedback contact the TAs during the labs.

Feedback for the CiviC Compiler Project is given by Simon Polstra on request by individual appointment.

Feedback for the CiviC Compiler Report is given by Thomas van Binsbergen or Martin Bor on request by individual appointment.

Assignments

Assignment 1

• Elementary CiviC Programming and Familiarisation with Compiler Framework

Assignment 2

• Lexicographic Analysis

Assignment 3

• Syntactic Analysis

Assignment 4

• Semantic Analysis

Assignment 5

• Code Transformation and Optimisation

Assignment 6

• Code Generation

CiviC Compiler Code

• Code base of your CiviC compiler

CiviC Compiler Report

• Report describing the design and special features of your CiviC compiler

Special Assignment

• CiviC AST Specification

The Weekly Assignment 1 must be submitted individually. All other Weekly Assignments, the CiviC Compiler Project and the CiviC Compiler Report must be worked on in fixed teams of 2 students. The CiviC AST specification must be submitted individually and is only graded pass/fail. 

Each Weekly Assignment counts 5% to the overall grade. The CiviC Compiler Implementation counts 60%, and the CiviC Compiler Report counts for the final 10%. A minimum of 5 is required for the weekly assignments (average) and for the compiler project and report together. 

Fraud and plagiarism

Over het algemeen geldt dat elke uitwerking die je inlevert ter verkrijging van een beoordeling voor een vak je eigen werk moet zijn, tenzij samenwerken expliciet door de docent is toegestaan. Het inzien of kopiëren van andermans werk (zelfs als je dat hebt gevonden bij de printer, in een openstaande directory of op een onbeheerde computer) of materiaal overnemen uit een boek, tijdschrift, website, code repository of een andere bron - ook al is het gedeeltelijk - en inleveren alsof het je eigen werk is, is plagiaat.

We juichen toe dat je het cursusmateriaal en de opdrachten met medestudenten bespreekt om het beter te begrijpen. Je mag bronnen op het web raadplegen om meer te weten te komen over het onderwerp en om technische problemen op te lossen, maar niet voor regelrechte antwoorden op opgaven. Als in een uitwerking gebruik is gemaakt van externe bronnen zonder dat een bronvermelding is vermeld (bijvoorbeeld in de rapportage of in commentaar in de code), dan kan dat worden beschouwd als plagiaat.

Deze regels zijn er om alle studenten een eerlijke en optimale leeromgeving aan te kunnen bieden. De verleiding kan groot zijn om te plagiëren als de deadline voor een opdracht nadert, maar doe het niet. Elke vorm van plagiaat wordt bestraft. Als een student ernstige fraude heeft gepleegd, kan dat leiden tot het uitschrijven uit de Universiteit. Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam: www.student.uva.nl

Course structure

Additional information

• Prerequisites for success: general programming skills, familiarity with imperative programming in the language C, user-level knowledge of UNIX-like operating systems, general knowledge in computer science as provided by the first two years of the Bachelor Informatica.
• All study material as well as the lectures are provided in English.

Contact information

Coordinator

• dr. L.T. van Binsbergen

Staff

• dr. ir. Martin Bor
• dr. Andrés Goens Jokisch
• drs Simon Polstra