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

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

General Information

Lecture:  Mondays, 7:10-9:00pm, CIWW 202
Instructors:  Kristoffer H. Rose (krisrose@cs.nyu.edu) with Eva Rose
Instructors's office hours:  Mondays 6:00-7:00pm, 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), aka the Dragon Book,
by Aho/Lam/Sethi/Ullman. Addison-Wesley, 2007.
Grader:  Weicheng Ma
Grader's office hours:  Wednesday 5:30-6:30pm, Room CIWW 230
Mailing list:  http://www.cs.nyu.edu/mailman/listinfo/csci_ga_2130_001_sp14

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.


Elements

The course includes the following elements:

Schedule

Here is the schedule. Each lecture links to the slides for that lecture, as they become available. Each homework and project milestone deliverable is linked from the due week. Paragraph references are to the dragon book, except H references that refer to sections of the hacs-gently.pdf document provided with HACS.

Date Lecture topic Reading
Mon 1/27 Introduction 1.1-1.2 (12p), H1
Mon 2/3 Lexical analysis 3.1-3.6 (43p), H2
Mon 2/10 Top-down syntax analysis 2.4 + 4.1-4.4 (50p), H3
Mon 2/17 Presidents Day
Mon 2/24 Syntax-directed translation (SDT) 2.3 + 2.5 + 5.1-5.3 (37p), H4
Mon 3/3 Name analysis 1.6 + 2.7 (15p), H5+H6
Mon 3/10 Type analysis 6.3 + 6.5 (20p)
Mon 3/17 Spring Recess---no class
Mon 3/24 Intermediate code generation 6.1, 6.2, 6.4, 6.6, 6.9 (34p), H7+8
Mon 3/31 Midterm exam
Mon 4/7 Runtime environments (extra slides) 7.1-7.4 (36p)
Mon 4/14 Code generation 8.1-8.4 + 8.6 (34p)
Mon 4/21 Register allocation 8.8 (5p)
Mon 4/28 Optimization 8.5 + 8.7 + 9.1 (26p)
Mon 5/5 Bottom-up syntax analysis 4.5 + 4.8 (17p)
Mon 5/12 Final exam
Mon 5/19 GSAS Graduation---no class


Grading

Final grades will be calculated to 10% from homeworks, 50% from the project, 10% from the midterm exam, and 30% 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 Mondays at 9am unless a different time is distributed explictly. To submit homeworks, log into home.nyu.edu, 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:

Official Updates

All official updates and changes are published on the class mailing list (cited at the top of the page).

See also

Documentation:

The Dragon book, 2nd edition: http://dragonbook.stanford.edu/
HACS: http://krisrose.net/hacs.zip
Introduction to ARM Subset: Not Yet Available

Supplementary Documentation:

ARM Instruction Set Summary: http://ozark.hendrix.edu/~burch/cs/230/arm-ref.pdf
ARM Calling Conventions: http://infocenter.arm.com/help/topic/com.arm.doc.ihi0042e/IHI0042E_aapcs.pdf
Useful ARM Reference Manual: https://www.scss.tcd.ie/john.waldron/3d1/arm_arm.pdf

NYU Information:

Machines at Courant: http://cims.nyu.edu/webapps/content/systems/resources/computeservers
Graduate cs.nyu.edu courses: http://cs.nyu.edu/webapps/spring2014/Graduate/courses
Graduate cs.nyu.edu calendar: http://cs.nyu.edu/webapps/Graduate/calendar
Previous Incarnations: 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

http://cs.nyu.edu/courses/spring14/CSCI-GA.2130-001/index.html
This file was last checked into CVS $Date: 2013/10/27 03:06:57 $ UTC (New York is at UTC-5).