Compiler Design

Course Code: BCA5141

Course Title: Compiler Design (4 Credits)




Course Contents


Unit 1: INTRODUCTION TO COMPILING: Compilers Analysis of source Program, The Phases of a compiler, The tasks of a compiler, Analysis of the Source Program, Phases and Passes in compilers, Cousins of the compiler, The Grouping of phases, Compiler - construction tools,


Unit 2: LEXICAL ANALYSIS: Lexical Analysis - The role of Lexical Analyzer, Input Buffering, Specification of Tokens, Recognition of Tokens, A Language for Specifying Lexical Analyzer, Review of Regular Expressions, Finite State Machines, Finite Automata based, Pattern Matching. Specification and recognition of tokens, a language for specifying lexical analyser,


Unit 3: LEXICAL ANALYSER GENERATOR: Introduction to Lexical Analyser Generator, Design of Lexical Analyzer generator, Programming assignment on lex, Regular expression to finite automation - Use of a tool for generating lexical analyser.


Unit 4:  SYNTAX ANALYSIS – Part 1: Introduction to syntax analysis, the Role of Parser, Review of grammars, Chomsky Hierarchy, Context-free Grammars, Writing a Grammar, Top-down Parsing, error recovery in Top down parsers,


Unit 5:  SYNTAX ANALYSIS – Part 2: Bottom-up Parsing, Overview of Shift reduce parsing, Operator-Procedure Parsing,  Finite automata of LR(0) items and LR (0) parsing, SLR parsing, Canonical LR Parsing, LALR Parsing, Compaction of LR parsing table, Using ambiguous grammars, Error recovery in bottom up,


Unit 6: PARSER GENERATORS: Introduction to Parser Generators, parsers, tools to generate parsers, Use of a tool to generate parsers, Yacc: an LALR(1) Parser generator, Abstract Syntax trees, Optimizing a grammar.


Unit 7: SYNTAX-DIRECTED TRANSLATION: Syntax Directed Definitions and translations, Attributes and Attribute, Grammar, Constructions of syntax Trees, Bottom-up Evaluation of S-attributed, L-attributed definitions, Top down translation, Bottom up evaluation of inherited attribute, Assigning space at compiler construction time, analysis of syntax directed definitions.


Unit 8: TYPE CHECKING: Type systems, Specification of simple type checker, equivalence of type expressions, type conversions, overloading of functions and operators, Polymorphic functions, an algorithm for unification.


Unit 9: RUN-TIME ENVIRONMENTS: Source Language Issues, Storage Organization, Storage Allocation strategies, parameter passing, access to non-local names, memory allocation in block structured language, various algorithms for Garbage collection, Parameter passing.


Unit 10: DYNAMIC STORAGE ALLOCATION TECHNIQUES: Introduction to Dynamic storage, symbol tables, Symbol Table Organization, Symbol attributes and Symbol table entries, Local Symbol Table management, Global Symbol table structure, language facilities for dynamic storage allocation, dynamic storage allocation techniques. Symbol Table for block structured language, Different types of dynamic storage Allocation Techniques, Static versus dynamic storage allocation techniques.


Unit 11: INTERMEDIATE CODE GENERATION: Intermediate Languages, Declarations, Assignments, Boolean Expression, Flow control statements - Back patching, Case Statements


Unit 12: CODE GENERATION: Introduction to optimization techniques , Issues in the design of code Generator, the target Machine, Run-Time storage Management, Basic blocks and flow graphs, Next-use information,


Unit 13: A SIMPLE CODE GENERATOR:Design of a simple code generator, A simple code generator, Register allocation and Assignment, The DAG representation of Basic blocks.


Unit 14: CODE OPTIMIZATION-I: Introduction, Early Optimizations, The Principle of Optimization, Optimization of Basic Blocks, Loops in flow graphs, Constant-Expression Evaluation (Constant Folding, Algebraic Simplifications and Re-association, Value numbering, Copy Propagation. Redundancy Elimination: Common-Subexpression Elimination.


Unit 15: CODE OPTIMIZATION-II: Loop-Invariant Code Motion, Partial- Redundancy Elimination, Redundancy Elimination and Reassociation, Code Hoisting, Loop Optimizations: Induction-Variable Optimizations, Unnecessary Bounds – Checking Elimination. Procedure Optimizations: Tail-Call Optimization and Tail-Recursion Elimination, Procedure Integration, In-Line Expansion, Leaf-Routine Optimization and Shrink Wrapping.