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

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

General Information

Lecture: Wednesdays 5:00 pm - 6:50 pm, Room WWH 312
Instructor: Martin Hirzel, hirzel@cs.nyu.edu
Instructor's office hours: Wednesdays 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 5 guest lecturer: Philippe Charles
Grader: Robert Soulé, soule@cs.nyu.edu
Grader's office hours: Thursdays 3:00-4:00, 719 Broadway room 715
Mailing list: http://www.cs.nyu.edu/mailman/listinfo/csci_ga_2130_001_fa11

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 “Tack”. Tack is a simple statically-typed programming language invented for this course. The preferred programming language for implementing the project is Java, and the preferred parser-generator is Rats!. 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 energon1.cims.nyu.edu to energon4.cims.nyu.edu machines at NYU.


Schedule

Date Lecture topic Reading Homework due Project milestone due
We 9/7 Introduction 1.1-1.2 (12p)    
We 9/14 Simple translator 2.1-2.5 (35p) hw1  
We 9/21 Lexical analysis 3.1-3.6 (43p) hw2  
We 9/28 Top-down syntax analysis 4.1-4.4 (42p) hw3  
We 10/5 Bottom-up syntax analysis 4.5 + 4.8 (17p)   pr1: Syntax checker
We 10/12 --Midterm exam--   hw4  
We 10/19 Syntax-directed translation5.1 - 5.3 (21p) hw5  
We 10/26 Name and type analysis 1.6 + 2.7 + 6.5 (30p)   pr2: AST generator
We 11/2 Intermediate-code generation6.2-6.4 + 6.6 (34p) hw6  
We 11/9 Run-time environments 7.1-7.4 (36p)   pr3: Semantic analyzer
We 11/16 Code generation 8.1-8.4 + 8.6 (34p) hw7  
We 11/23 Register allocation 8.8 (5p)    
We 11/30 Optimization 8.5 + 8.7 (13p)   pr4: IR generator
We 12/7 Garbage collection; Review 7.5-7.6 (20p) hw8  
We 12/14 (no lecture, NYU is on a Monday schedule)     pr5: Code generator
We 12/21 --Final exam--      


Grading

Final grades will be calculated to 10% from homeworks, 30% from the project, 20% from the midterm exam, and 40% from the final exam. (Midterm grades are calculated to 10% from hw1-hw3, 30% from pr1, and 60% from the midterm exam.)

Points from homeworks and quizzes

Each row contains the points of all 17 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  24  24  24  24  24  24  24  23  23  22  12   0
hw2      24  24  24  24  24  24  24  24  24  24  24  24  22  20  18  18  18
hw3      24  24  24  24  24  24  22  22  22  22  22  20  20  20  20  19  14
pr1     100 100 100 100 100 100 100 100 100 100 100  92  44  28  10   5   0
midterm 100 100  99  99  96  96  95  94  94  94  92  92  91  81  80  75  69
m-score 100 100  99  99  97  97  96  95  93  92  88  78  71  69  67  63  62
hw4      24  24  24  24  24  24  24  24  24  24  24  24  24  24  24  23  23
hw5      24  24  24  23  23  23  23  23  23  21  21  21  21  18  18  13  13
pr2     100 100 100 100 100 100 100 100 100 100 100  94  85  55  43  43
hw6      24  24  24  24  24  24  24  24  24  24  24  24  22  22  20  20
pr3     100 100 100 100 100 100 100 100 100 100  93  86  79  79  72  36
hw7      24  24  24  24  24  24  24  24  24  24  24  23  22  22  18  11
pr4     100 100 100 100 100 100 100 100 100  95  95  90  90  85  60  50
hw8      24  24  24  23  23  23  22  22  22  22  21  20  20  18  13   0
pr5     100 100 100 100 100 100 100 100 100 100  95  95  85  55  50  50
final    97  96  94  92  92  92  88  73  73  72  71  70  69  63  60  58
f-score  98  98  95  94  93  93  91  87  86  84  81  79  76  75  69  63

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. The policy for late assignments is as follows:

See also

Documentation:

Rats! parser generator: rats-intro.pdf, http://cs.nyu.edu/rgrimm/xtc/
Tack language specification: tack-spec.pdf
Tack interpediate representation: ir-spec.pdf, IRInterpreter.jar
x64 instruction set: x64-intro.pdf, assembly, instructions, calling conventions
Java specification: Java 6 APIs, JLS (Java language specification)
The Dragon book, 2nd edition: http://dragonbook.stanford.edu/
Lecture notes: 9/7, 9/14, 9/21, 9/28, 10/19, 10/26, 11/2, 11/9, 11/16, 11/23, 11/30, 12/7
Homework assignments: hw1, hw2, hw3, pr1, hw4, hw5, pr2, hw6, pr3, hw7, pr4, hw8, pr5

NYU Information:

Machines at Courant: http://cims.nyu.edu/webapps/content/systems/resources/computeservers
Graduate cs.nyu.edu courses: http://cs.nyu.edu/webapps/fall2011/courses
Graduate cs.nyu.edu schedule: http://cs.nyu.edu/webapps/fall2011/Graduate/courses
Graduate cs.nyu.edu calendar: http://cs.nyu.edu/webapps/Graduate/calendar
Compiler construction course: Spring'11 (Mohamed Zahran), Spring'09 (Allan Gottlieb), Spring'06 (Benjamin Goldberg)
Academic integrity policy: http://cs.nyu.edu/web/Academic/Graduate/academic_integrity.html

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