View on GitHub

Compiler Construction

Spring 2018

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-007
Course staff
Instructor
Prof. Nate Nystrom (SI-203)
Assistant
Omar Javed (2nd floor open space)
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% Participation, 20% Quizzes, 40% Final exam

Schedule

The schedule is subject to change.

Date Topic Readings Assignments
Mon 19 Feb Welcome notes  
Wed 21 Feb ASTs and interpreters [Dragon 1-2], 1.1-1.3, count.py, notes  
Mon 26 Feb      
Wed 28 Feb x86 assembly [Dragon 7.1-7.2], 1.4, notes P0 interpreter
Mon 5 Mar Syntax-directed translation [Dragon 5], 1.5-1.6, notes  
Wed 7 Mar Instruction selection, quiz [Dragon 6, 8.1-8.3]  
Mon 9 Mar      
Wed 14 Mar Scanning, DFAs, regular expressions [Dragon 3.1-3.7], 2.1-2.2, notes P0 compiler
Mon 19 Mar Holiday: no class    
Wed 21 Mar Parse trees and derivations [Dragon 4.1-4.9], 2.3-2.4  
Mon 26 Mar LL parsing notes  
Wed 28 Mar LR parsing notes  
Mon 2 Apr Holiday: no class    
Wed 4 Apr Holiday: no class    
Mon 9 Apr Register allocation, liveness [Dragon 8.8] 3.1-3.6, notes  
Wed 11 Apr Interference graphs, coloring, spilling, quiz    
Mon 16 Apr      
Wed 18 Apr Polymorphism and tagging 4.1-4.9 P0 parser, notes
Mon 23 Apr Loops and control-flow graphs 4.10-4.11, notes  
Wed 25 Apr     P0 regalloc
Mon 30 Apr Optimization 1, dataflow analysis notes  
Wed 2 May Optimization 2    
Mon 7 May Functions 5.1-5.5, notes  
Wed 9 May      
Mon 14 May   6.1-6.3 P1 compiler
Wed 16 May Object notes  
Mon 21 May Holiday: no class    
Wed 23 May Memory management [Dragon 7.4-7.8], notes  
Mon 28 May      
Wed 30 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. Assignments found to have been plagiarized will be given a grade of 0.