View on GitHub

Compiler Construction

Spring 2019

In this course you will learn how programs written in high-level languages are executed on modern hardware. Understanding how languages are implemented is useful for reasoning about program behavior and performance. A secondary goal of the course is to expose students to the principles, techniques, and tools used to construct compilers and interpreters.

The course will cover both the theory and practice of programming language implementation. Topics include compiler structure, lexical and syntactic analysis (parsing), types, semantic analysis, program representations, data-flow analysis, register allocation, optimization, and compiler construction tools. Students will implement a compiler for a high-level programming language on modern hardware.

Lectures Mon, Wed 10:45–12:15 in Room SI-013
Course staff
Instructor
Prof. Nate Nystrom (SI-203)
References
[Notes] A Problem Course in Compilation: From Python to x86 Assembly
Jeremy G. Siek and Bor-Yuh Evan Chang
[Dragon] Compilers: Principles, Techniques, and Tools, 2nd edition
Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, 2006. (amazon.de) — The first edition is also (mostly) acceptable, and cheaper, but chapter references will be to the second edition.
Python3 AST API
Grading 40% Project, 20% Quizzes, 40% Final exam

Schedule

The schedule is subject to change.

Date Topic Readings Assignments
Mon 18 Feb Welcome slides, notes  
Wed 20 Feb ASTs and interpreters [Dragon 1-2], 1.1-1.3, Python notes, notes, count.py  
Mon 25 Feb      
Wed 27 Feb x86 assembly [Dragon 7.1-7.2], 1.4, notes P0 interpreter
Mon 4 Mar Syntax-directed translation [Dragon 5], 1.5-1.6, notes, x86 calling conventions  
Wed 6 Mar Instruction selection [Dragon 6, 8.1-8.3], notes  
Mon 11 Mar Scanning, DFAs, regular expressions [Dragon 3.1-3.7], 2.1-2.2, notes  
Wed 13 Mar Regular expression derivatives paper P0 compiler
Mon 18 Mar Parse trees and derivations, LL parsing [Dragon 4.1-4.9], 2.3-2.4, notes, ll.py  
Wed 20 Mar LR parsing notes  
Mon 25 Mar      
Wed 27 Mar Register allocation, liveness [Dragon 8.8] 3.1-3.6, notes P0 parser
Mon 1 Apr Interference graphs, coloring, spilling    
Wed 3 Apr Loops and control-flow graphs 4.10-4.11, notes  
Mon 8 Apr Polymorphism and tagging 4.1-4.9, notes P0 regalloc
Wed 10 Apr Memory management [Dragon 7.4-7.8], notes  
Mon 15 Apr quiz    
Wed 17 Apr Optimization 1, dataflow analysis notes  
Mon 22 Apr Holiday: no class    
Wed 24 Apr Holiday: no class    
Mon 29 Apr Optimization 2    
Wed 1 May Holiday: no class    
Mon 6 May Functions 5.1-5.5, notes  
Wed 8 May      
Mon 13 May   6.1-6.3 P1 compiler
Wed 15 May Objects notes  
Mon 20 May      
Wed 22 May      
Mon 27 May      
Wed 29 May     P2 compiler

Policies

Assignments

The course is heavily project-based. Students will implement a compiler for a high-level programming language on modern hardware. Students will also do written assignments to understand programming language and compiler principles. Students are expected to read the assigned readings before class. During class sessions we will discuss remaining questions and problems.

Quizzes and exams

There will be one 15-minute quiz approximately every two weeks.

The final exam is a 3-hour written exam.

The best preparation for the exam is to do the assignments and to read the the assigned readings.

Group Work

You are encouraged to work on the programming assignments with your classmates. The contributions of each student must be explicitly described. All students are responsible for understanding the assignments. Written assignments must be done on your own.

Submission

Assignments should be submitted through Github.

Cheating

Cheating and plagiarism are unacceptable. You are free to discuss assignments and solutions with others. However, you must write your own assignments, and must not represent any portion of others’ work as your own. Cases of cheating or plagiarism will be result in penalties for all involved, up to and including receiving a 0 grade for the course.