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|
|Grading||40% Participation, 20% Quizzes, 40% Final exam|
The schedule is subject to change.
|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|
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. Assignments found to have been plagiarized will be given a grade of 0.