Compiler Design :: Course Content & online available resources

Course Content

Introduction: Translators, Various phases of compiler, tool based approach to compiler construction.

Lexical analysis: token, lexeme and patterns, difficulties in lexical analysis, error reporting, implementation, regular definition, transition diagrams, LEX.

Syntax Analysis: top down parsing (recursive descent parsing, predictive parsing), operator precedence parsing, bottom-up parsing (SLR, LALR, Canonical LR), YACC.

Syntax directed definitions: inherited and synthesized attributes, dependency graph, evaluation order, bottom-up and top-down evaluation of attributes, L-attributed and S-attributed Definitions.

Type checking: type system, type expressions, structural and name equivalence of types, type conversion, overloaded functions and operators, polymorphic functions.

Run time system: storage organization, activation tree, activation record, parameter passing, dynamic storage allocation, symbol table: hashing, linked list, tree structures.

Intermediate code generation: intermediate representation, translation of declarations, assignments, control flow, Boolean expressions and procedure calls, implementation issues.

Code generation and Optimization: issues, basic blocks and flow graphs, register allocation, code generation, dag representation of programs, code generation from dags, peephole optimization.

Reference Texts and E-Resources

Compilers: Principles, Techniques, & Tools, second edition, by Aho, Lam, Sethi, Ullman

Compilers: Principles, Techniques, and Tools, first edition, By Aho, Sethi, Ullman

The Theory and Practice of Compiler Writing, By J. P. Trembley and P. G. Sorensen

Compiler Design in C, By Allen I. Holub

Basics of Compiler Design, By Torben Ægidius Mogensen

Modern Compiler Implementation in C, By Andrew W. Appel

Modern Compiler Design, Springer

Modern Compiler Implementation in Java, By Andrew W. Appel and Jens Palsberg

Engineering a Compiler, By Keith D. Cooper, Linda Torczon; Morgan Kaufmann Publishers

Notes by Allan Gottlieb: https://cs.nyu.edu/courses/spring09/G22.2130-001/class-notes.html

Slides: https://www.cse.iitk.ac.in/users/karkare/cs335/

Video Lectures: http://nptel.ac.in/course.php

Lab Assignments

C Language Specification: Appendix A: Reference Manual, C Programming Language, Kernighan and Ritchie

Lex & Yacc Tutorials by: Tom Niemann, Victor Eijkhout, A. Karkare, Dragon Book(Pages- 140, 287)

gcc Compiler: https://gcc.gnu.org/onlinedocs/gcc/

Lex Files and Commands used in Lecture on Lex: Download

Yacc and Lex Files, and Commands used in Lecture on Yacc: Download


Assignments

1. Implement the Lexical Analyzer using C language.
2. Tokenize the hello world program using Lex/Flex tool.
3. Write a program in Flex which recognizes identifiers in C language.
4. Write a program in Flex which recognizes integers and float numbers in C language.
5. Write a program in Flex which recognizes relational operators in C language.

6. Implement the Lexical Analyzer using LEX tool. (Reference: page number 143 of Dragon Book).
7. Compile and execute the yacc source programs given on page numbers 289, and 292 of Dragon Book.
8. Write parser and lexer for a desk calculator using Yacc and Lex tool. Compile and link parser and lexer together to create      a single executable calculator.exe.

9. Write a program to implement symbol table and its operations.
10. Write a program to generate abstract syntax tree using Yacc.
11. Write a program to parse a given string using following parsers:
      (i) Recursive descent parsing,   (v) Predictive parser,    (i) Operator precedence parser,    (ii) LR parser

12. Write a program to generate parsing table for SLR parser.

13. Write a program to check whether the given grammar is LR(0) or not.

14. Write a program to check whether the given grammar is SLR(1) or not.

Reading Assignments:

1. Bootstrapping in Compiler Design
2. Run Time System