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

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

General Information

Lecture:  Thursdays, 5:10-7:00pm, CIWW 312
Instructors:  Eva Rose (evarose@cs.nyu.edu) and Kristoffer H. Rose (krisrose@cs.nyu.edu)
Instructors's office hours:  Thursdays, 4-5pm, CIWW 328
Prerequisites:  G22.1170 (algorithms), G22.2110 (programming languages), and G22.2250 (operating systems)
Text book:  Compilers: Principles, Techniques, and Tools (2nd Edition), aka the Dragon Book,
by Aho/Lam/Sethi/Ullman. Addison-Wesley, 2007.
Grader:  Weicheng Ma (wm724@nyu.edu)
Grader's office hours:  Tuesday, 6-7pm, in CIWW 229 (the computer lab)
Mailing list:  http://www.cs.nyu.edu/mailman/listinfo/csci_ga_2130_001_fa14.

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 a simple programming language. The implementation will use a custom NYU version of the compiler-generator infrastructure CRSX, called HACS.


Schedule

Here is the schedule. Each lecture links to the slides for that lecture, as they become available. Paragraph references are to the dragon book, except H references that link to handouts with sections of the HACS documentation as it evolves.

Note that the contents of every provided link is subject to change up to end of the lecture it is associated with.

Date Lecture topic Reading Homework Project milestone
Thur 9/4 1. Introduction 1.1-1.2 (12p) hw1 (solutions)  
Thur 9/11 2. Lexical analysis 3.1-3.4,3.6,3.7 (50p), H1+H2 hw2  
Thur 9/18 3. Top-down syntax analysis 2.4 + 4.1-4.4 (50p), H3 hw3 pr1 (due 10/6) samples
Thur 9/25 4. Syntax-directed translation (SDT) 2.3 + 2.5 + 5.1-5.3 (37p), H4 hw4  
Thur 10/2 5. Name analysis 1.6 + 2.7 (15p), H5 hw5  
Thur 10/9 6. Type analysis 6.3 + 6.5 (20p), H6 hw6 pr2 (due 11/3)
Thur 10/16 7. Intermediate code generation 6.1, 6.2, 6.4, 6.6, 6.9 (34p), H7 hw7  
Thur 10/23 Midterm exam      
Thur 10/30 8. Runtime environments 7.1-7.4 (36p) hw8  
Thur 11/6 9. Code generation 8.1-8.4 + 8.6 (34p), H8 hw9 pr3 (due 12/1)
Thur 11/13 10. Register allocation 8.8 (5p) hw10  
Thur 11/20 11. Bottom-up syntax analysis 4.5 + 4.8 (17p) hw11  
Thur 11/27 Thanksgiving recess      
Thur 12/4 12. Optimization 8.5 + 8.7 + 9.1 (26p) hw12  
Thur 12/11 13. TBA      
Thur 12/18 Final exam      


Elements

The course includes the following elements:


Grading

Final grades will be calculated to 15% from homeworks, 45% from the project, 15% from the midterm exam, and 25% from the final exam.

See Also

NYU Information:

Machines at Courant: http://cims.nyu.edu/webapps/content/systems/resources/computeservers
Graduate cs.nyu.edu courses: http://cs.nyu.edu/webapps/fall2014/Graduate/courses
Graduate cs.nyu.edu calendar: http://cs.nyu.edu/webapps/Graduate/calendar
Previous Incarnations: Spring'14 (Kristoffer Rose with Eva Rose), Fall'13 (Martin Hirzel and Kristoffer Rose), Spring'13 (Hubertus Franke), Fall'12 (Mohamed Zahran), Fall'11 (Martin Hirzel), Spring'09 (Allan Gottlieb)
Academic integrity policy: http://cs.nyu.edu/web/Academic/Graduate/academic_integrity.html