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|
|Grading||40% Project, 20% Quizzes, 40% Final exam|
The schedule is subject to change.
|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|
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.
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.
Assignments should be submitted through Github.
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.