Compiler Construction

Course manual 2020/2021

Course content

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 and target code generation

A model programming language named CiviC 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 as a medium-scale software engineering project with milestones, etc, course participants develop a fully-fledged compiler for this language targeting a stack-based virtual machine very similar to the Java Virtual Machine.

Two guest lectures by renowned Amsterdam-based compiler experts touch upon the industrial and commercial aspects of compilers.

Study materials

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, 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

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 any purpose.

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 much other academic software the compiler construction framework we use throughout the practical part of the course is not well documented. We provide a life introduction during week 1. Attendance during these lectures and labs is essential for successfully passing the course.

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 Clemens Grelck 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%.

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

Timetable

The schedule for this course is published on DataNose.

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.

Processed course evaluations

We have been working on a novel compiler construction framework for a few years, which will tested with a few groups of students this year.

Contact information

Coordinator

• dr. C.U. Grelck

Staff

• dr Clemens Grelck
• drs Simon Polstra
• Lukas Miedema, MSc
• Daan Kruis, MSc
• Damian Frölich, BSc
• Tim Müller, BSc
• Folkert van Verseveld, BSc