21CS51 AUTOMATA THEORY AND COMPILER DESIGN
Module - 1
Introduction to Automata-Theory: Central Concepts of Automata-theory, Deterministic Finite Automata(DFA), Non- Deterministic Finite Automata(NFA) ,Epsilon- NFA, NFA to DFA Conversion, Minimization of DFA
Introduction to Compiler Design: Language Processors, Phases of Compilers
Module - 2
Regular Expressions and Languages: Regular Expressions, Finite Automata and Regular Expressions, Proving Languages Not to Be Regular
Lexical Analysis Phase of compiler-Design: Role of Lexical Analyzer, Input Buffering , Specification of Token, Recognition of Token.
Module - 3
Context Free Grammars: Definition and designing CFGs, Derivations Using a Grammar, Parse Trees, Ambiguity and Elimination of Ambiguity, Elimination of Left Recursion, Left Factoring.
Syntax Analysis Phase of Compilers: part-1: Role of Parser , Top-Down Parsing
Module - 4
Push Down Automata: Definition of the Pushdown Automata, The Languages of a PDA.
Syntax Analysis Phase of Compilers: Part-2: Bottom-up Parsing, Introduction to LR Parsing: SLR, More Powerful LR parsers
Module - 5
Introduction to Turing Machine: Problems that Computers Cannot Solve, The Turing machine, problems, Programming Techniques for Turing Machine, Extensions to the Basic Turing Machine
Undecidability : A language That Is Not Recursively Enumerable, An Undecidable Problem That Is RE.
Other Phases of Compilers: Syntax Directed Translation- Syntax-Directed Definitions, Evaluation Orders for SDD’s. Intermediate-Code Generation- Variants of Syntax Trees, Three-Address Code.
Code Generation- Issues in the Design of a Code Generator