Compiler Construction
CSCI-GA.2130-001, Fall 2013

General information / Course Description / Schedule / Grading / See also

General Information

Lecture: Thursdays 5:10 pm - 7:00 pm, Room WWH 312
Instructors: Martin Hirzel ( and Kristoffer H. Rose (
Instructors's office hours: Thursdays 4:00-5:00, Room CIWW 328, or by appointment
Prerequisites: G22.1170 (algorithms), G22.2110 (programming languages), and G22.2250 (operating systems)
Text book: Compilers: Principles, Techniques, and Tools (2nd Edition), by Aho/Lam/Sethi/Ullman. Addison Wesley, 2007.
October 17 guest lecturer: Philippe Charles
Grader: Bowen Li (
Grader's office hours: Tuesdays 1:00-2:00, Room CIWW 230
Mailing list:

Course Description

The course description below is quoted from the Graduate School of Arts and Science Bulletin:

This is a capstone course based on compilers and modern programming languages. The topics covered include structure of one-pass and multiple-pass compilers; symbol table management; lexical analysis; traditional and automated parsing techniques, including recursive descent and LR parsing; syntax-directed translation and semantic analysis; run-time storage management; intermediate code generation; introduction to optimization; and code generation. The course includes a special compiler-related capstone project, which ties together concepts of algorithms, theory (formal languages), programming languages, software engineering, computer architecture, and other subjects covered in the MS curriculum. This project requires a substantial semester-long programming effort, such as construction of a language compilation or translation system that includes lexical and syntactic analyzers, a type checker, and a code generator.

Specifically, the course will follow the “Dragon Book” (second edition) as the text book. In the semester-long programming project, we will implement a fully functional compiler for “Tiger”. Tiger is a simple statically-typed programming language invented by Andrew Appel for compiler construction courses. The preferred compiler-generator infrastructure for implementing the project is CRSX. The project consists of multiple milestones. Each milestone builds on code from the previous milestone, and that code will be made available to you at the appropriate time. You can develop the project on your own machine, but must make sure that it works on the to machines at NYU.


Date Lecture topic Reading Homework due Project milestone due
Thu 9/5 Introduction (MH, KR) (sample) 1.1-1.2 (12p)    
Thu 9/12 Lexical analysis (MH) 3.1-3.6 (43p) hw1  
Thu 9/19 Top-down syntax analysis (KR) 4.1-4.4 (42p) hw2  
Thu 9/26 Syntax-directed translation (MH) 2.5 + 5.1-5.3 (28p)   pr1: Lexer and parser
Thu 10/3 Name analysis (KR) 1.6 + 2.7 (15p) hw3  
Thu 10/10 Type analysis (MH) 6.5 (12p) hw4  
Thu 10/17 Bottom-up syntax analysis (PC) 4.5 + 4.8 (17p) hw5  
Thu 10/24 --Midterm exam--   hw6  
Thu 10/31 Intermediate code generation (KR) 6.2-6.4 + 6.6 (34p)   pr2: Semantic analyzer
Thu 11/7 Runtime environments (MH) 7.1-7.4 (36p) hw7  
Thu 11/14 Code generation (KR) 8.1-8.4 + 8.6 (34p)    
Thu 11/21 Register allocation (MH) 8.8 (5p)    
Thu 11/28 --Thanksgiving recess--   hw8  
Thu 12/5 Optimization (KR) 8.5 + 8.7 (13p)   pr3: IR generator
Thu 12/12 --Final exam--      


Final grades will be calculated to 10% from homeworks, 30% from the project, 20% from the midterm exam, and 40% from the final exam.

Academic integrity

Please carefully read the CIMS department's academic integrity policy.

Assignment deadlines

All homework and project assignments will be due on Fridays at 1pm. To submit homeworks, log into, go to Academic → NYU Classes → Compiler Construction → Assignments, and upload your file with answers there. Don't forget to click “submit” before the deadline, just “upload” is not enough. The policy for late assignments is as follows:

Points from homeworks and exams

Each row contains the points of all 6 enrolled students, in descending order by points for that particular row. That means that the same student might be further left in one row and further right in another, depending on how well they did on that part of the class.
hw1      24  24  24  24  24 
hw2      24  24  23  23  19  17
pr1     100  95  95  95  90  80
hw3      24  24  24  18  13   0
hw4      16  16  16  16  15  14
hw5      24  24  23  23  22  22
midterm  37  34  33  32  30  27  //midterm exam
m-score  93  91  83  83  81  76  //calculated from hw1-hw5, pr1, midterm exam
m-grade   A   A   B   B   B   C  //based on m-score
hw6      16  16  15  15  15  10
pr2     100 100 100 100 100 100
hw7      36  36  36  36  32
hw8      16  16  16  15  15
pr3      90  90  80  80  80  70
final    58  51  50  48  46  40
f-score  95  86  86  81  81  80
f-grade   A  A-   A-  B   B   B  //based on f-score

See also


Tiger language specification: tiger-spec.pdf
Intermediate representation: ir-spec.pdf, IRInterpreter.jar
x64 instruction set: x64-intro.pdf, assembly, instructions, calling conventions
The Dragon book, 2nd edition:
The Tiger Book, Java edition:
HACS Compiler Generator: (distribution) hacs_gently.pdf (Gentle Introduction)

NYU Information:

Machines at Courant:
Graduate courses:
Graduate calendar:
Compiler construction course: Spring'13 (Hubertus Franke), Fall'12 (Mohamed Zahran), Fall'11 (Martin Hirzel), Spring'09 (Allan Gottlieb)
Academic integrity policy:
This file was last checked into CVS $Date: 2014/01/06 16:41:31 $ UTC (New York is at UTC-5).