FINITE AUTOMATA AND REGULAR LANGUAGES
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
COMPILERS AND LEXICAL ANALYSIS
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 Analyzer
Implementation of LEX specification.
SYNTAX ANALYSIS AND SEMANTIC ANALYSIS
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 ENVIRONEMENT AND INTERMEDIATE CODE GENERATION
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.
CODE GENERATION AND CODE 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 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.
Reference Book:
Linz P. An introduction to formal languages and automata. Sixth edition, Jones and Bartlett Publishers; 2016.
C. N. Fisher and R. J. LeBlanc “Crafting a Compiler with C”, First Edition, Pearson Education, 2000.
D.Chithra , “Principles of Compiler Design”, First Edition, CBS Publishers and Distributors , 2014.
Alfred V. Aho, Jeffrey D. Ullman, “Principles of Compiler Design”, Second Edition, Addison-Wesley Publ., 2008.
Ramaiah k. Dasaradh “Introduction to Automata and Compiler Design “ First Edition ,Prentice Hall India Learning Private Limited,2011.
Text Book:
John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman, “Introduction to Automata Theory, Languages and Computation”, Second Edition, Pearson Education, New Delhi, 2007.
Alfred V. Aho, Ravi Sethi Jeffrey D. Ullman, “Compilers- Principles, Techniques, and Tools”, Second Edition , Pearson Education Asia, 2012.
