Compiler Design

CS 335, IIT Kanpur, Semester 2023-24-II

Instructor Information

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

TA Information

Name	Email (AT cse.iitk.ac.in)
Binong Kiri Bey	binong@cse.iitk.ac.in
Mannu Kumar Gaddhyan	mannugaddhyan@cse.iitk.ac.in
Sandula Lavanya	lavanyasandula@cse.iitk.ac.in
Shrawan Kumar	shrawan@cse.iitk.ac.in
Shrutika Anil Jadhav	shrutikaaj@cse.iitk.ac.in
Sodanapalli Linga Reddy	lreddy@cse.iitk.ac.in
Srinjoy Sarkar	srinjoy@cse.iitk.ac.in
Vinay Agrawal	vinayagrawal@cse.iitk.ac.in
Vipin Patel	vipinpat@cse.iitk.ac.in

Course Description

The objective of the course is to learn useful concepts 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 learned 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. The project will be done in groups.

Prerequisites

ESC101, ESO207/CS210, CS220, CS340.
Programming maturity with popular programming languages like C, C++, and Java.

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

Syllabus and Policies

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/Flex.
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/Bison/ANTLR.
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, flow graphs, register allocation, code generation, DAG representation of programs, code generation from DAGs, peep hole optimization, code generator generators, and specifications of the machine.

The course may also involve reading related research papers.

Policies

Be on time for class.
Avoid using laptops and/or mobile devices in class, they are distracting for both the instructor and other students who want to concentrate.
You are allowed up to two late days to submit your assignment, with a 25% penalty for each day.

Feedback

I am open to constructive feedback about the course content and presentation. Feel free to provide suggestions for improvements.

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	12%	Approximately three (same weight)
Quizzes	8%	At least two (same weight), dates will be announced, closed book, no cheat sheet
Midsem	20%	Closed book, will allow one A4-sized cheat sheet
Endsem	25%	Whole syllabus, closed book, will allow one A4-sized cheat sheet
Project	35%	Will post evaluation details in due time

Resources

Date	Topic	Resources	Reading Assignment
	First Course Handout	PDF
05/01, 08/01	Overview of Compilation	Slides	DRAGv2 Chapter 1 EaC Chapter 1
10/01, 12/01, 15/01	Lexical Analysis	Slides	DRAGv2 2.6-2.7, 3.1-3.4, 3.6-3.8 EaC 2.1-2.5
	Flex	Manual flex In A Nutshell An Overview of flex, with Examples	DRAGv2 3.5
17/01	Syntax Analysis	Slides	DRAGv2 2.2, 4.1-4.3 EaC 3.1-3.2
19/01, 24/01, 26/01	Top-down Parsing	Slides	DRAGv2 2.4, 4.2-4.4 EaC 3.3
26/01, 27/01, 29/01, 31/01, 05/02	Bottom-up Parsing	Slides	DRAGv2 4.5-4.8 EaC 3.4-3.6
	Bison	Manual	DRAGv2 4.9
07/02, 09/02, 12/02	Semantic Analysis	Slides	DRAGv2 2.3, 5.1-5.4 EaC 4.1, 4.3, 4.4
14/02, 16/02, 26/02	Type Systems	Slides	DRAGv2 6.3, 6.5 EaC 4.2
26/02, 28/02, 01/03, 02/03, 04/03, 06/03	Intermediate Representations	Slides	DRAGv2 2.7, 6.1-6.2, 6.4, 6.6-6.8 EaC Chapter 5
11/03, 13/03, 18/03, 20/03, 22/03	Runtime Environments	Slides Notes	DRAGv2 7.1-7.3 EaC 6.1-6.5, 7.1-7.2, 7.9
01/04, 03/04, 05/04, 06/04, 08/04	Code Generation	Slides	DRAGv2 8.1-8.6, 8.9, 8.10 EaC Chapter 11
10/04, 12/04, 15/04, 17/04	Register Allocation	Slides	DRAGv2 8.8 EaC Chapter 13
19/04	Compiler Optimizations	Slides	DRAGv2 9.1

References

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

[DRAGv1] A. Aho, R. Sethi, and J. Ullman. Compilers: Principles, Techniques, and Tools, 1^st edition.
[DRAGv2] 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 (3^rd edition came out in 2023).

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