CS335 Compiler Design (2018-19 IInd Semester)

Instructor: Amey Karkare ( )
TAs: Ameya Rajgopal Loya (ameya@cse), Ayush Tulsyan (atulsyan@cse), Gopichand Kotana (gopick@cse), Manish K Bera (mkbera@iitk), Nimisha Agarwal (nimisha@cse), Pawan Patel (patelp@cse), Rahul Gupta (grahul@cse)
Timings: Mon, Wed, Fri : 9:00AM - 10:00AM
Venue: RM 101 (Rajeev Motvani Building, CSE Dept)

This course aims to teach various phases of Compiler Design.

Code of Ethics
Announcements
Course Outline
Evaluation Scheme
Topics covered and handouts
Assignments
Course Project
Supporting Material
Recommended References

Code of Ethics

Any report/program/assignment you submit must clearly distinguish your contribution from others (webpages, softwares, report, discussions with other students). The penalty for copying in any form will be severe.

Announcements

Important: All emails either to the instructor or the TAs should begin with subject line "[CS335]" -- without any spaces in the course code (and without quotes). Email not complying to this rule will NOT be entertained.
The course site is up on Canvas. Everyone in the class must register on Canvas.

Topics Covered and Slides

The slides are not suitable for taking prints as there is a lot of redundancy due to overlays. Print only the pages that you really require.

Note that [DragonBook] refers to Compilers: Principles, Techniques, and Tools, Second edition, 2006. by Alfred V. Aho , Monica S. Lam , Ravi Sethi , Jeffrey D. Ullman. Almost all the content we cover in the class is also available in the older edition of the book [OldDragonBook], but the chapters/sections could be different.

#	Description (# of Lectures)	Slides	References
1.	Introduction (1)	[slides]
2.	Overview of Compilation (2)	[slides]	Chapter 1 and 2 of the [OldDragonBook]
3.	Lexical Analysis (2)	[slides]	Chapter 3 of the [DragonBook]
4.	Syntax Analysis (1)	[slides]	Chapter 4 (4.1 - 4.3) of the [DragonBook]
5.	Top Down Parsing (Self Study)	[slides]	Chapter 4 (4.4) of the [DragonBook]
6.	Bottom Up Parsing (4)	[slides]	Chapter 4 (4.5 - 4.9) of the [DragonBook]
7.	Lex/Yacc tutorial (1)	[By Saumya Debray][By David Beazley]
8.	Semantic Analysis (1.5)	[slides]	Chapter 5 (5.1) of the [OldDragonBook]
9.	Syntax Directed Translation (3.5)	[slides]	Chapter 5 (5.2 - 5.6, 5.8) of the [OldDragonBook]
10.	Type Checking (2)	[slides]	Chapter 6 (6.1 - 6.6) of the [OldDragonBook]
11.	IR and Symbol Table (2)	[slides]	Sections 7.6 & 8.1 of the [OldDragonBook]
12.	Intermediate Code Generation (4)	[slides]	Chapter 8 of the [OldDragonBook]
13.	Run-time Systems (6)	[slides]	Chapter 7 (7.1 - 7.5) of the [OldDragonBook]
14.	Code Generation (1.5)	[slides]	Chapter 9 of the [OldDragonBook]
15.	Code Gen: Sethi Ullman (1.5)	[slides]	Section 9.10 of the [OldDragonBook]
16.	Code Gen: Aho Johnson (3)	[slides]	Section 9.10 of the [OldDragonBook]
17.	Code Gen: Tree Walking (1.5)	[slides]	Paper

Assignments

There will be short assignments to give you a chance to apply the lecture material. Assignments will have some written and some programming tasks.

Course Project

The course project gives you a chance to apply the concepts learnt in the class to build a prototype compiler. You will be required to implement various phases of a compiler, and perform an experimental evaluation of your implementation.

Project will be done in groups. The maximum (and preferable) size of a group will be three students.

Course Outline

The course will mainly cover topics from the following list (not necessarily in the same order).

Compiler structure: analysis-synthesis model of compilation, various phases of a compiler, tool based approach to compiler construction.
Lexical analysis: interface with input, parser and symbol table, token, lexeme and patterns. Difficulties in lexical analysis. Error reporting. Implementation. Regular definition, Transition diagrams, LEX.
Syntax analysis: CFGs, ambiguity, associativity, precedence, top down parsing, recursive descent parsing, transformation on the grammars, predictive parsing, bottom up parsing, operator precedence grammars, LR parsers (SLR, LALR, LR), YACC.
Syntax directed definitions: inherited and synthesized attributes, dependency graph, evaluation order, bottom up and top down evaluation of attributes, L- and S-attributed definitions.
Type checking: type system, type expressions, structural and name equivalence of types, type conversion, overloaded functions and operators, polymorphic functions.
Run time system: storage organization, activation tree, activation record, parameter passing, symbol table, dynamic storage allocation.
Intermediate code generation: intermediate representations, translation of declarations, assignments, control flow, boolean expressions and procedure calls. Implementation issues.
Code generation and instruction selection: issues, basic blocks and flow graphs, register allocation, code generation, dag representation of programs, code generation from dags, peep hole optimization, code generator generators, specifications of machine.

Evaluation Scheme

(Tentative)

Assignments/Quizzes	10%
Mid semester exam	20%
End semester exam	35%
Course Project	35%

Supporting Material

Most of the following softwares are available from package repositories of linux distributions. It is recommended to use these repositories and install instead of building them from source.

cscope and ctags: Code browsing utilities
Eclipse: A Java based Integrated Development Environment
LaTeX: A document preparation system

Recommended References

Aho, A., Lam, M., Sethi, R., Ullman, J., Compilers: Principles, Techniques, & Tools, Addison Wesley, 2007.
Appel, A., Modern Compiler Implementation in Java (or ML, or C), Cambridge University Press, 2002.
Cooper, K., Torczon, L., Engineering a Compiler, Morgan Kaufmann, 2004
Muchnick, S., Advanced Compiler Design and Implementation, Morgan Kaufmann, 1997.
Randy Allen, Ken Kennedy,Optimizing Compilers for Modern Architectures: A Dependence-based Approach, Morgan Kaufmann, 2001