CS 515 Programming Languages and Compilers I
16:198:515 Fall 2014
- September 10: Class timings changed to 10.00-1.00pm to accomodate
students attending another class at 1.40pm
- First class on September 3, 2014.
CS 515 is a graduate level course in programming language design and
implementation. We will cover basic concepts of programming languages
and the challenges in building compilers for them. The
students will incrementally build a compiler from a C-like language to
a subset of x86 assembly during this course. In this process,
they will learn lexing, parsing, interpreters, challenges in
translating high-level languages to machine code, and the x86
architecture. The course will also introduce students to OCaml, a
functional programming language.
This is a project intensive course with numerous projects. The
projects will expose students to real world compilation environments
like GCC and LLVM, functional programming in OCaml, and in summary,
create a better understanding of code and teaches you how to be a good
- Instructor: Prof. Santosh
Office: Core 328
Office hours: Wednesday 4pm-5pm or by appointment
- Teaching Assistant: David Menendez, Office
hours: Thursday 2-4pm Core 329
- Lecture location: SEC-117
, Wednesday 10.00am - 1.00pm
- Prerequisites: Significant programming
experience and preferably undergraduate compilers (CS 314 at
The textbooks for this course are the
The bookstore links for these books can be found here.
In addition, the following web sites provide supplementary
material. Reading selections from these sources will be announced in
- Compilers (2nd Edition) by Aho, Lam, Sethi, and Ullman
- Modern Compiler Implementation in ML by Andrew Appel
- Advanced Compiler Design and Implementation by Muchnick
The tentative lecture schedule and the reading material for the class
| September 4, 2014
|| Introduction: Compilers, Interpreters, OCaml
| September 10, 2014
|| OCaml Programming, Introduction to X86Simplified
| September 17, 2014
|| X86Simplified Programming, Lexing DFAs and OCamlLex
| September 24, 2014
|| Parsing: Context Free Grammars and OCamlYACC, LL(k) Parsing,
| October 1, 2014
|| Parsing: LR Parsing, Intermediate Representations
| October 8, 2014
|| LLVM IR, Contexts and Scoping, compiling control flow
| October 15, 2014
|| Structured data, first class functions
| October 22, 2014
|| Interpretation and type-checking, closures, types and subtypes
| October 29, 2014
|| Midterm, Prof. Santosh Nagarakatte away at LLVM dev conference
| November 5, 2014
|| Objects and dynamic dispatch, multiple inheritance
| November 12, 2014
|| Typechecking, Intro to optimizations
| November 19, 2014
|| Dataflow analysis
| November 26, 2014
|| No class as Friday schedule on November 26
| December 3, 2014
|| Control flow analysis, Register allocation
| December 10, 2014
|| Manual memory management, garbage collection, reference counting
The goal of this course is to learn. Collaboration is encouraged.
However, you should not copy the actual code for programming
assignments, the reviews or copy the wording for written
homeworks. Any violation of these rules will be considered cheating
and dealt with severely. Here are links to the Rutgers University
Academic Integrity Policy and the Department
of Computer Science Integrity Policy.
This course is a project intensive
course with a total of 8 projects. Each project will incrementally
build the compiler from a C-like source language with objects to a
subset of x86 assembly.
515 is a graduate course. Projects that
don't compile or don't execute will get zero credit. Passing the
automatic grader is essential. Up to date details about the project and
other resources are available on
- Project 1 : OCaml programming. Download project code and details
- Project 2: X86 Interpreter and progrmaming. Download project code and
- Project 3: Compling Arithmetic Expressions to X86. Download
project code and details here .
- Project 4: Compiling Control Flow. Download project code and
details here .
- Project 5: Type Checking and Compiling Arrays, Structures, and
Functions. Download project code and details here .
- Project 6 (Extra credit): Live Variable Dataflow Analysis for
The grading will be performed according to the following distribution:
| Projects || 70%
| Midterm || 10%
| Final || 15%
|Class participation || 5%
- Lecture attendance is important.
- Projects have to be done individually.
- All project discussion emails should be sent via discussion
forums on sakai.
- All individual-specific questions should be sent with the string
"" at the beginning of the subject field of the email.
- Any project that does not compile will get zero credit.
This course uses a significant fraction of the materials from
Prof. Steve Zdancewic's (Penn) course, which is in turn modeled on
courses by Prof. Andrew Myers(Cornell) and Prof. Greg Morrisett