Compiler Design

CS 335, IIT Kanpur, Semester 2022-2023-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	WedFri 10-11 AM in KD 302

TA Information

Name	Email (AT cse.iitk.ac.in)
Abhishek Revskar	abhishekdr
Akash Panzade	akashp
Arpan Kapoor	arpank
Ashutosh Patel	ashutoshp
Deepak Raj	deepakr
Dinkar Tewari	dinkart
Mayank Solanki	smayank
Siddhartha Bura	siddhab
Vikas	vikasv
Vipin Patel	vipinpat

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 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	15%
Midsem	20%
Endsem	30%
Project	35%

Resources

Register on Canvas for course management
Register on Piazza for discussions
Follow the course calendar

Date	Topic	Resources	Recommended Reading
	First Course Handout	PDF
06/01, 09/01	Overview of Compilation	Slides	DRAGv1 Chapter 1 DRAGv2 Chapter 1 EaC Chapter 1
11/01, 13/01, 16/01, 18/01	Lexical Analysis	Slides	DRAGv1 2.6-2.7, 3.1-3.4, 3.6-3.8 DRAGv2 2.6-2.7, 3.1-3.4, 3.6-3.8 EaC 2.1-2.5
	Lex/Flex	Manual flex In A Nutshell An Overview of flex, with Examples	DRAGv1 3.5 DRAGv2 3.5
20/01	Syntax Analysis	Slides	DRAGv1 2.2, 4.1-4.3 DRAGv2 2.2, 4.1-4.3 EaC 3.1-3.2
23/01, 25/01, 27/01	Top-down Parsing	Slides	DRAGv1 2.4, 4.2-4.4 DRAGv2 2.4, 4.2-4.4 EaC 3.3
30/01, 01/02, 03/02, 06/02, 08/02	Bottom-up Parsing	Slides	DRAGv1 4.5, 4.7 DRAGv2 4.5-4.7 EaC 3.4
	Yacc/Bison	Manual	DRAGv1 4.9 DRAGv2 4.9
10/02, 13/02, 15/02	Semantic Analysis	Slides	DRAGv1 2.3, Chapter 5 DRAGv2 2.3, 5.1-5.4 EaC 4.1, 4.3, 4.4
17/02, 27/02	Type Systems	Slides	DRAGv1 Chapter 6 DRAGv2 6.3, 6.5 EaC 4.2
01/03, 03/03, 13/03, 15/03, 17/03, 20/03	Intermediate Representations	Slides	DRAGv1 8.2 DRAGv2 2.7, 6.1-6.2, 6.4, 6.6-6.8 EaC Chapter 5
22/03, 27/03, 29/03, 31/03	Runtime Environments	Slides Notes	DRAGv1 Chapter 7 DRAGv2 7.1-7.4 EaC Chapters 6, 7.1-7.2
01/04, 03/04, 05/04, 10/04, 12/04, 14/04	Code Generation	Slides	DRAGv1 Chapter 9.1-9.8, 9.10, 9.11 DRAGv2 8.1-8.6, 8.9, 8.10 EaC Chapter 11
17/04, 21/04	Register Allocation	Slides	DRAGv1 9.7 DRAGv2 8.8 EaC Chapter 13

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.

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