UNIT I Automata Introduction to formal proof - Additional forms of proof - Inductive proofs - Finite Automata (FA) - Deterministic Finite Automata (DFA) - Non-deterministic Finite Automata (NFA) - Finite Automata with Epsilon transitions- Equivalence and minimization of Automata. (Chapter - 1) UNIT II Context Free Grammars and Languages Context-Free Grammar (CFG) - Parse Trees - Ambiguity in grammars and languages - Definition of the Pushdown automata - Languages of a Pushdown Automata - Equivalence of Pushdown automata and CFG - Deterministic Pushdown Automata - Normal forms for CFG - Pumping Lemma for CFL - Closure Properties of CFL - Turing Machines - Programming Techniques for TM. (Chapters - 2, 3) UNIT III Basics of Compilation Compilers - Analysis of source program - Phases of a compiler - Grouping of phases - Compiler construction tools - Lexical Analyzer: Token Specification - Token Recognition - A language for Specifying lexical analyzer - Top down parser: Table implementation of Predictive Parser - Bottom up Parser: SLR(1) Parser - Parser generators. (Chapters - 4, 5) UNIT IV Type Checking and Runtime Environments Syntax directed definitions - Construction of syntax trees - Type systems - Specification of a simple type checker - Equivalence of type expressions - Type conversions - Attribute grammar for a simple type checking system - Runtime Environments: Source language issues - Storage organization - Storage allocation strategies - Parameter passing. (Chapters - 6, 7, 8) UNIT V Code Generation and Optimization Issues in the design of a code generator - The target machine - Run-time storage management - Basic blocks and flow graphs - Next-use information - A simple code generator - Register allocation and assignment - The dag representation of basic blocks - Generating code from DAG – Dynamic programming code generation algorithm – Code generator generators - Code optimization. (Chapters - 9, 10)
