CS3020: Principles of Compiler Design and CS6240: Advanced Compiler Design

August 2014 - Nov 2014

Instructor: Ramakrishna Upadrasta (U. Ramakrishna)
Email: Ramakrishna AT iith DOT ac DOT in
Office:

TAs (IITH email-IDs: <ID> AT iith DOT ac DOT in) : Kanigalpula Samanvi (cs13m1001), Kanishka Chauhan (cs13m1003), Natti Bhuvana Sai (cs13m1006), Parag Jain (cs13m1008), Kiran Bhos (cs13m1011), Chavan Yogesh Laxman (cs13m1012), Anjali Singh (cs13m1013)

Discussion Google-group: iith-compilers-aug14 AT googlegroups DOT com Join Group (only with IITH email-IDs)
Classes: Mon: 8:30am-10:00am, Thu: 10:00am-11:30am (A slot); Room: LH1
Labs (CS3021) : Wed: 8:30am-10:00am (L40, L35, L15); 10:00-11:30am (L40, L35, CL121); 11:30am-1:00pm (L40, L35, CL121).
(Code: L40=1st floor lab, L35=DISANET lab, L15=Lab next to server room, CL121: Classroom #121 for students with laptops.)

Credits: CS3020:CS3021 3:2; CS6240 3:0
Prerequisites: CS3020:CS3021 3rd/4th year B.Techs; CS6240: M.Techs and PhDs (Primarily 1st years: exceptions allowed. Please get a permission from me.)

Course Description (CS3020 and CS6240)

The objective of these courses is to learn basic principles and advanced techniques of compiler design. Both the courses will focus lexical analysis, syntactic analysis, semantic analysis, abstract syntax tree and code-generation as well as basic optimizations.

The initial part of both the courses will focus on the classic techniques of lexical analysis and scanning/screening, syntactic analysis like bottom-up and top-down parsing techniques, semantic analysis, type-checking, abstract syntax tree and code generation. The latter part will focus on intermediate representations and simple optimizations like register allocation and instruction scheduling.

A significant focus of these courses would be on designing and implementing parts of compiler for a subset of C++/Java. The language of implementation would be in C/C++ languages. There would also be effort to study modern compilers like LLVM in the form of mini-assignments.

Course Description (CS3021)

This is the B.Tech lab accompanying the corresponding B.Tech course CS3020. For registrants of CS3020, a registration to CS3021 is compulsory. The major means of evaluation of CS3021 would be the above mentioned project.

Course Description (CS6240)

This is a sister course to CS3020 being offered to B.Techs. This beginning level M.Tech/PhD course would have additional project work, a paper presentation, and some research component.

Lecture Schedule

31-July-2014	Organization & Logistics, An Overview of Compilers PDF Acknowledgements
4th-Aug-2014	An Overview of Compilers PDF, Introduction to Lexical Analysis PDF Readings: ALSU, Ch.1
7th-Aug-2014	Introduction to Lexical Analysis PDF Finite Automata (Deterministic and Non-deterministic), Regular Expressions, Transition Diagrams. Code Examples Regular expressions in vim, bash and perl. Readings (All) ALSU, Sec. 2.6 Readings (All) Cool-manual PDF and Cool Tour PDF
11th-Aug-2014	Gradiance session
14th-Aug-2014	Lexical Analysis (Contd.) PDF Transition Diagrams (contd.), Introduction to lex/flex tool. Code Examples EDG lexical analysis, GCC 2.9.5 lexical analysis. Readings (All) ALSU, Chapter#3 Readings (All) Lex paper PDF, Flex manual, PDF
18th-Aug-2014	Introduction to Parsing PDF Introduction to Syntax Analysis, Parsing, Context Free Grammars. Readings (All) ALSU, Sections#4.1-4.2
21st-Aug-2014	Parsing (contd.) PDF Pushdown Automata, Top-Down Parsing using LL Grammars, LL(1) parsing. Readings (All) ALSU, Sections#4.2 and 4.3-4.4
25th-Aug-2014	Top-Down Parsing PDF Predictive parsing, FIRST and FOLLOW sets and their computation. Readings (All) ALSU, Sections#2.4 and 4.3-4.4
28th-Aug-2014	Top-Down Parsing (contd.) PDF FIRST and FOLLOW sets recap. Useless symbols and their removal, Left recursion and Left factoring, Recursive Descent parsing. Readings (All) ALSU, Sections#2.4 and 4.3-4.4 Readings (All: for fun) Litte Languages by Jon Benteley ALSU, Readings (CS6240) Parr et al. ANTLR paper on LL(*) parsing
1st-Sep-2014	Bottom-Up Parsing PDF Shift-Reduce parsing, Rightmost derivations, LR Parsing, Handles Readings (All) ALSU, Section#4.5
4th-Sep-2014	Bottom-Up Parsing PDF Viable Prefixes, Item sets, Handles, SR parsing: states, LR(0) automaton. Readings (All) ALSU, Section#4.6
8th-Sep-2014	Bottom-Up Parsing PDF LR(0) automaton, The Nondeterministic and deterministic versions. Readings (All) ALSU, Section#4.6
11th-Sep-2014	Bottom-Up Parsing PDF PDF LR(0) automaton, Conflicts, SLR parsing basics, An overview of Yacc and Assign#3. Readings (All) ALSU, Section#4.6
15th-Sep-2014	Bottom-Up Parsing PDF SLR parsing and LR(1) parsing Yacc, error recovery/handling in LR parsing, Basics of Abstract Syntax Tree. Readings (All) ALSU, Section#4.8, 4.9, 2.5.1 (AST basics).
23rd-Sep-2014	Midterm Examination Syllabus Till SLR(1) parsing.
	Midterm and Dussehra Break
9th-Oct-2014 & 13th-Oct-2014	AST, Semantic Analysis, Attribute grammars PDF PDF PDF PDF Semantic Analysis, Attribute Grammars, Synthesized and Inherited Attributes, Attribute Dependence Graph, Attribute Evaluation. Code Examples LLVM AST for simple C/C++ programs. Readings (All) ALSU, Sections#5.1, 5.2 Readings (All: for fun) Circularity of attribute grammars by Don Knuth PDF. The above chapter is from the book Selected Papers on Computer Languages
16th-Oct-2014	Attribute Grammars: SATG PDF PDF Introduction to Symbol Tables. PDF Attribute grammars: SATG. Code Examples LLVM AST for C/C++ (basic constructs) programs using Clang. Symbol table structure from EDG. Readings (All) ALSU, Sections#6.1, 6.2
20th-Oct-2014	Intermediate Code Generation PDF PDF PDF PDF S-Attributed definitions and grammars, Intermediate code generation. Code Examples LLVM IR for common constructs. Readings (All) ALSU, Sections#6.4, 6.6, 6.7
23rd-Oct-2014	Deepavali Break
27th-Oct-2014	Basic Blocks PDF Introduction to Optimizations PDF PDF Basic Blocks, Control Flow Graphs (CFG) CFGs of common constructs Machine Independent Optimizations: CSE, LICM etc. Code Examples LLVM CFG and introduction to passes Readings (All) ALSU, Sections#8.4, 9.1
30th-Oct-2014	Introduction to Data-Flow Analysis PDF PDF PDF Introduction to SSA form PDF Introduction to Data-Flow Analysis (DFA), Basic Concepts of DFA, Reaching Definitions, Live Variables. SSA form introduction Readings (All) ALSU, Sections#9.1, 9.2
3rd-Nov-2014 & 10th-Nov-2014	Introduction to Register Allocation PDF PDF PDF Register allocation, DU chains, Kempe's heuristic, Chaitin's algorithm. Readings (All) ALSU, Sections#8.8
TBD

References:

[Text Book] Compilers: Principles, Techniques, and Tools ("Dragon book") by Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, 2006

[Ref. Book] Compiler Design "Syntactic and Semantic Analysis" by Reinhard Wilhelm, Helmut Seidl and Sebastian Hack, 2013

[Adv. Ref. Book] Advanced Compiler Design and Implementation by Steven Muchnick, 1997

[NPTEL] NPTEL course on Principles of Compiler Design by Prof. Y.N. Srikant from Indian Institute of Science, 2012-2014 IITM Link

[Coursera] Coursera course on Compilers by Prof. Alex Aiken at Stanford, 2012-2014 Coursera Compilers

[Gradiance] Gradiance System by Prof. Jeffrey D. Ullman newgradiance link

.....

Some Class Links:

news

doc