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 to sections of the HACS documentation.

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 (solutions)  
Thur 9/18 3. Top-down syntax analysis 2.4 + 4.1-4.4 (50p), H3 hw3 (solutions) pr1 (due 10/6) samples (zip), solution (pr1-rose.hx, updated)
Thur 9/25 4. Syntax-directed translation (SDT) 2.3 + 5.1-5.3 (30p), H4 hw4 (Bool.hx, solutions)  
Thur 10/2 5. Name analysis 1.6 + 2.7 (15p), H7 hw5 (solutions)  
Thur 10/9 6. Type analysis 6.3 + 6.5 (20p), H6 hw6 (solutions) pr2a (due 11/3) solution
Thur 10/16 7. Intermediate code generation 6.1, 6.2, 6.4, 6.6, 6.9 (34p), H5 hw7 (solutions) pr2b (due 11/25) Pr2Base.hx sample (zip)
Thur 10/23 Midterm exam (solutions)      
Thur 10/30 8. Runtime environments 7.1-7.4 (36p) hw8 (solutions)  
Thur 11/6 9. Code generation 8.1-8.4 + 8.6 (34p) hw9 (solutions)  
Thur 11/13 10. Register allocation 8.8 (5p) hw10 (solutions)  
Thur 11/20 11. Bottom-up syntax analysis 4.5-4.6 (26p) hw11 (solutions)  
Thur 11/27 Thanksgiving recess      
Thur 12/4 12. Optimization 8.5 + 8.7 + 9.1 (26p)   pr3 (due 12/16) Pr3Base.hx samples (zip) hints
Thur 12/11 13. Burka: The Shape of an Object     final announcements, blackboard hints left|right
Thur 12/18 Final exam      

Supporting Materials

Guest Lecture

This year, the guest lecture is given by Peter Burka:
The Shape of an Object

The layout of structures in memory is often an after-thought in the early designs of languages and their runtime systems. However there are a surprising number of choices available to the designer, with interesting trade-offs in speed, determinism, memory requirements, memory-management options, and other capabilities. Some of these are old techniques known to assembly programmers of yore, but forgotten by most high-level programmers. Others are still largely academic.

Peter worked at IBM for 14 years, mostly on the J9 Java Virtual Machine team. In this talk we'll explore some of the techniques used to optimize object shape in the J9 VM, as well as some more speculative options.


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