Compiler Design

CS 335, IIT Kanpur, Semester 2019-2020-II

Instructor Information

Name	Swarnendu Biswas
Email	swarnendu AT cse.iitk.ac.in
Class hours	MonWedFri 9:00-9:50 AM in RM 101
Office hours	TueThurs 4-5 PM in KD 302

TA Information

Name	Email (AT cse.iitk.ac.in)
Nimisha Agarwal	nimisha
Manish Kumar Bera	mkbera
K Karthikeyan	kkarthi
Anuj Mishra	anujmi
Vipin Patel	vipinpat
Bidya Sarkar	bidya
Prafulla Saxena	prafulla
Krishna Kumar Tayal	ktayal
Nilesh Vasita	nilesh

Course Description

The objective of the course is to learn concepts that are useful to understand, design, and modify compilers for programming languages.

This course will involve both pen-paper and programming assignments.

The course project will require you 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.

Prerequisites

ESC101, ESO207/CS210, CS220, CS340.
Good knowledge in languages like C, C++, and/or and Java is required for the project.

Course Policies and Syllabus | Academic Integrity | Evaluation Scheme | Resources | References

Course Policies and Syllabus

Policies

Remember that clarifying every question and doubt is important. There is nothing like a trivial or a foolish question.
Please be on time to class, it is distracting for everyone when students keep trickling in late to class.
Please try to avoid using laptops and/or mobile devices in class, they are distracting for both the instructor and other students who want to concentrate.
Submitting your assignments late will mean losing points automatically. You will lose 20% for each day that you miss, for up to two days. You might be excused only under extreme circumstances, but let me now at the earliest.

Syllabus

The following is a tentative list of topics that we will cover during the course. We might add new, drop existing, or reorder topics depending on progress and class feedback.

Overview of Compilation: 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.
Runtime Systems: 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.

The course may also involve reading related research papers.

Feedback

I am open to constructive feedback about the course content and presentation. I may distribute unofficial feedback forms a few weeks into the semester, and you will have the choice of remaining anonymous.

Academic Integrity

You may discuss concepts with classmates, but all submissions must be your own or your team's work when teamwork is permitted.
You may not search online for existing solutions related to the assignments, even as a reference.
Students caught cheating or plagiarizing will automatically fail the course and will be reported to the institute.

Evaluation Scheme

Assignments - 15%
Mid semester exam - 20%
End semester exam - 30%
Project - 35%

Resources

We will use Piazza as the discussion forum. Click here to register for the course on Piazza.
We will use Canvas for course submissions.

Date	Topic	Resources	Recommended Reading
03/01, 06/01	Course Overview, Overview of Compilation	Course Overview Compiler Overview	DRAG Chapter 1 EaC Chapter 1
08/01, 10/01, 13/01	Lexical Analysis, Lex/Flex	Lexical Analysis Lex/Flex	DRAG 2.6-2.7, 3.1-3.4, 3.6-3.8 EaC 2.1-2.5
13/01, 15/01	Syntax Analysis	Slides	DRAG 2.2, 4.1-4.3 EaC 3.1-3.2
15/01, 17/01, 20/01	Top-down Parsing	Slides	DRAG 2.4, 4.2-4.4 EaC 3.3
20/01, 22/01, 24/01, 27/01	Bottom-up Parsing	Slides	DRAG 4.5-4.7 EaC 3.4
29/01, 31/01, 03/02	Semantic Analysis	Slides	DRAG 2.3, 5.1-5.3 EaC Chapter 4 PLP Chapter 4
05/02, 07/02, 10/02	Type Systems	Slides	EaC Chapter 4.2 PLP Chapters 7-8
12/02, 14/02, 24/02, 26/02, 28/02, 29/02	Intermediate Representations	Slides	DRAG 2.7, 6.1-6.2, 6.4, 6.6-6.8 EaC Chapter 5
02/03, 04/03, 06/03	Runtime Environments	Slides	DRAG 7.1-7.4 EaC Chapters 6, 7.1-7.2
TBD	Code Generation	Slides	DRAG 8.1-8.6, 8.9 EaC Chapter 11
TBD	Instruction Scheduling	Slides	EaC Chapter 12
TBD	Register Allocation	Slides	EaC Chapter 13 DRAG 8.8

References

I have listed (NOT in any particular order) a few popular references.

[DRAG] A. Aho, M. Lam, R. Sethi, and J. Ullman. Compilers: Principles, Techniques, and Tools, 2^nd edition.
[EaC] K. Cooper and L. Torczon. Engineering a Compiler, 2^nd edition.
[MCI] A. Appel. Modern Compiler Implementation in Java, 2^nd edition.
[PLP] M. Scott. Programming Language Pragmatics, 4^th edition.

We may read and discuss related materials and research papers which we will announce in class.