T P C
4 0 3
COMPILER DESIGN
Compiler Design Course Objectives:
To make the student to understand the process involved in a compiler, create an overall view of various types of translators, linkers, loaders, and phases of a compiler, understand what is syntax analysis, various types of parsers especially the top down approach, awareness among students the various types of bottom up parsers, understand the syntax analysis and, intermediate code generation, type checking, the role of symbol table and its organization, Code generation, machine independent code optimization and instruction scheduling.
Course Outcomes:
1. To introduce the major concept areas of language translation and compiler design
2. To develop an awareness of the function and complexity of compilers.
3. To provide practical, hands on experience in compiler design
4. Identify the similarities and differences among various parsing techniques and grammar transformation techniques
Unit – I :
Overview of language processing – pre-processors – compiler – assembler – interpreters, pre-processors, – linkers & loaders - structure of a compiler – phases of a compiler (TEXT BOOK 2). Lexical Analysis – Role of Lexical Analysis – Lexical Analysis Vs. Parsing – Token, patterns and Lexemes – Lexical Errors – Regular Expressions – Regular definitions for the language constructs – Strings, Sequences, Comments – Transition diagram for recognition of tokens, Reserved words and identifiers, Examples.
Unit – II : Syntax Analysis – discussion on CFG, LMD,RMD, parse trees, Role of a parser – classification of parsing techniques – Brute force approach, left recursion, left factoring, Top down parsing – First and Follow- LL(1) Grammars, NonRecursive predictive parsing – Error recovery in predictive parsing.
Unit – III : What is bottom up parsing approach, Types of Bottom up approaches; Introduction to simple LR – Why LR Parsers – Model of an LR Parsers – Operator Precedence- Shift Reduce Parsing – Difference between LR and LL Parsers, Construction of SLR Tables. More powerful LR parses, construction of CLR (1), LALR Parsing tables, Dangling ELSE Ambiguity, Error recovery in LR Parsing. Comparison of all bottoms up approaches with all top down approaches
Unit–IV : Semantic analysis, SDT Schemes, evaluation of semantic rules. Intermediate code, three address code, quadruples, triples, abstract syntax trees. Types and declarations, type Checking.
Unit–V : Symbol tables: use and need of symbol tables. Runtime Environment: storage organization, stack allocation, access to non-local data, heap management, parameter passing mechanisms, introduction to garbage collection. Reference counting garbage collectors. Code generation: Issues, target language, Basic blocks & flow graphs, Simple code generator, Peephole optimization, Register allocation and assignment.
Unit–VI : Machine independent code optimization – semantic preserving transformations, global common sub expression elimination, copy propagation, dead code elimination, constant folding, strength reduction, loop optimization. Instruction scheduling, inter procedural optimization. TEXT
BOOKS :
1. Compilers, Principles Techniques and Tools- Alfred V Aho, Monica S Lam, Ravi Sethi, Jeffrey D. Ullman,2nd ed, Pearson,2007.
or
http://www.informatik.uni-bremen.de/agbkb/lehre/ccfl/Material/ALSUdragonbook.pdf
2. Compiler Design, K. Muneeswaran, Oxford.
REFERENCE BOOKS:
1. Engineering a compiler, 2nd edition, Keith D.Cooper & Linda Torczon, Morgan Kaufman.
2. http://www.nptel.iitm.ac.in/downloads/106108052/
3. Principles of compiler design, V. Raghavan, 2nd ed, TMH, 2011.
4. Compiler construction, Principles and Practice, Kenneth C Louden, CENGAGE
5. Implementations of Compiler, A new approach to Compilers including the algebraic methods, Yunlinsu, SPRINGER
-----------------------------
----------------------------
