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
  • .....

  • Suggested readings:

  • .....

  • Grading (CS3020)

    Activity Weight
    Class Participation 10%
    Mid Term Exam 25%
    End Term Exam 30%
    Project + Mini Prog. Assignments (LLVM) 15+10=25%
    Gradiance Homeworks 10%


    Grading (CS6240)

    Activity Weight
    Mid Term Exam 15%
    End Term Exam 25%
    Project + Mini Prog. Assignments (LLVM) 25+10=35%
    Gradiance Homeworks 10%
    Paper Presentation + Writeup 10+5=15%