Introduction - Central concepts of Automata Theory - Types of Grammars- Regular Expressions, Identity rules for Regular Expressions -Finite State Automata - Deterministic Finite State Automata(DFA), Non Deterministic Finite State Automata(NDFA) - Equivalence of DFA and NDFA -Pushdown Automata - Languages of a Pushdown Automata -- Turing Machines- Languages of Turing Machine. Lab Practice: Construction of NFA from Regular Expression.Construction of minimized DFA from a given regular expression

Introduction to Compiling – Compilers – Analysis of the source program – The phases – Cousins – The grouping of phases – Compiler construction tools. The role of the lexical analyzer – Input buffering – Specification and Recognition of tokens – Finite automata – Regular expression to finite automata – A language for specifying lexical analyzer – tool for generating lexical analyzer. Lab Practice: Implementation of Lexical AnalyzerImplementation of LEX specification.

Syntax Analysis – The role of the parser – Context-free grammars – Writing a grammar – Top down parsing – Bottom-up Parsing – LR parsers – SLR Parsers – Canonical LR Parsers – LALR Parsers – Constructing an LR parsing table – Tool to generate parser – Semantic Analysis: Type Checking – Type Systems – Specification of a simple type checker. Lab Practice: Construction of LR parsing table.Implementation of syntax analysis using YACC.Construction of Shift Reduce Parser.

Run-Time Environments – Source language issues – Storage organization – Storage-allocation strategies – Intermediate languages – Declarations – Assignment statements – Boolean expressions – Case statements – Back patching – Procedure calls. Lab Practice: Generation of code for a given intermediate code generator.

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 DAGs. Introduction to optimization techniques – The principle sources of optimization – Peephole optimization – Optimization of basic blocks – Loops in flow graphs – Introduction to global data-flow analysis – Code improving transformations. Lab Practice: Implementation of DAG representation