Compiler Construction
CSCI-GA.2130-001/Spring 2015

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

General Information

Lecture:  Mondays, 7:10-9:00pm, CIWW 202
Instructors:  Eva Rose (evarose@cs.nyu.edu) and Kristoffer H. Rose (krisrose@cs.nyu.edu)
Instructors's office hours:  Mondays, 6-7pm, CIWW 328, or by appointment
Prerequisites:  G22.1170 (algorithms), G22.2110 (programming languages), and G22.2250 (operating systems)
Grader:  José Pablo Cambronero (jpc485@nyu.edu)
Grader's office hours:  Thursdays, 6-7pm, CIWW 229 (Computer Lab)
Mailing list:  http://www.cs.nyu.edu/mailman/listinfo/csci_ga_2130_001_sp15.

Materials

Dragon Book
Compilers: Principles, Techniques, and Tools (2nd Edition),
by Aho/Lam/Sethi/Ullman. Addison-Wesley, 2006.
HACS
Manual: Introduction to Compiler Generation Using HACS by Rose. Available from crsx.org/hacs.pdf (under continuous revision so check the version number).
Software: HACS 1.0.2 (reference version for pr1), HACS 1.0.13 (reference version for pr2), HACS 1.0.19 (updated reference version for pr3 per bulletin 8). HACS 1.0.20 (per pr3 bulletin 10).
ARM32
ARM32 subset documentation: MinARM32.pdf.
Full ARM32 documentation (background information): Architecture, Refcard.

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 the compiler-generator tool HACS (part of the open source CRSX project).


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 Hn references to sections of the HACS manual and An references to the ARM subset (both quoted in the materials above).

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

Date Lecture topic Reading Homework Project milestone
Mon 1/26 1. Introduction 1.1-1.2 (12p), H1-2 hw1  
Mon 2/2 2. Lexical analysis 3.1-3.4,3.6,3.7 (50p), H3 hw2  
Mon 2/9 3. Top-down syntax analysis 2.4 + 4.1-4.4 (50p), H4 hw3 Project Milestone 1: pr1 due 2/27, samples.zip (corrected)
Mon 2/16 Presidents Day    
Mon 2/23 4. Syntax-directed translation and recursive HACS 2.3 + 5.4 (21p), H5, H9 hw4
Mon 3/2 5. Syntax-directed definitions and type analysis 5.1-5.3 + 6.3, 6.5 (40p) hw5 Project Milestone 2: pr2 due 3/9 and 3/31
Mon 3/9 6. Name analysis and SDD to HACS translation 1.6 + 2.7 (15p), H6-8 hw6
Mon 3/16 Spring Recess    
Mon 3/23 7. Intermediate code generation 6.1, 6.2, 6.4, 6.6, 6.9 (34p) hw7
Mon 3/30 Midterm exam    
Mon 4/6 8. Runtime environments 7.1-7.4 (36p), A1 hw8 (solution)  
Mon 4/13 9. Code generation 8.1-8.4 (28pp), A2 hw9 Project Milestone 3: pr3 due 4/20 and 5/1
Mon 4/20 10. Register allocation 8.6 + 8.8 (11p) hw10
Mon 4/27 11. Bottom-up syntax analysis 4.5 + 4.6 (26p) hw11
Mon 5/4 12. Optimization 8.5 + 8.7 + 9.1 (26p)  
Mon 5/11 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: Fall '14 (Eva Rose and Kristoffer Rose), 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