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:
1 Linz P. An introduction to formal languages and automata. Sixth edition, Jones and Bartlett Publishers; 2016.
2 C. N. Fisher and R. J. LeBlanc “Crafting a Compiler with Câ€, First Edition, Pearson Education, 2000.
3 D.Chithra , “Principles of Compiler Designâ€, First Edition, CBS Publishers and Distributors , 2014.
4 Alfred V. Aho, Jeffrey D. Ullman, “Principles of Compiler Designâ€, Second Edition, Addison-Wesley Publ., 2008.
5 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.
