Course

Unit I

Finite Automata (FA): Introduction, Deterministic Finite Automata (DFA) -Formal definition, simpler notations (state

transition diagram, transition table), the language of a DFA. Nondeterministic Finite Automata (NFA)- Definition of the FA, language of an NFA, Equivalence of Deterministic and Nondeterministic Finite Automata, Applications of Finite Automata, Minimization of Deterministic Finite Automata.

Unit II

Regular Expressions (RE): Introduction, Identities of Regular Expressions, Finite Automata and Regular Expressions- Converting from DFA’s to Regular Expressions, Converting Regular Expressions to Automata, Context Free Grammar (CFG): Derivation Trees, Sentential Forms, Rightmost and Leftmost derivations of Strings.

Unit III

Introduction To Compilers: Definition of compiler, interpreter and its differences, the phases of a compiler, role of lexical analyzer, regular expressions, finite automata, from regular expressions to finite automata. Parsing: Parsing, the role the of parser, context free grammar, derivations, parse trees, elimination of left recursion, left factoring, predictive parsers, LL(1) grammars. Bottom Up Parsing: Definition of bottom-up parsing, LR grammars, LR parsers-simple LR, canonical LR(CLR) and Look Ahead LR (LALR) parsers, error recovery in parsing, parsing ambiguous grammars.

Unit IV

Syntax Directed Translation: Syntax directed definition, construction of syntax trees, S-attributed and L-attributed definitions, translation schemes. Intermediate Code Generation: intermediate forms of source programs– abstract syntax tree, polish notation and three address code, Type Checking: Definition of type checking, type expressions, type systems.

Unit V

Code Optimization: Organization of code optimizer, basic blocks and flow graphs, optimization of basic blocks, the principal sources of optimization, the directed acyclic graph (DAG) representation of basic block, and global data flow analysis. Code Generation: Machine dependent code generation, object code forms, the target machine, a simple code generator, register allocation and assignment, peephole optimization.

Textbooks: 

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2007), Introduction to Automata Theory Languages and Computation, 3rdedition, Pearson Education, India. 
• Alfred V.Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, “Compilers: Principles, Techniques and Tools”, Prentice Hall, Second Edition, 2006. 

References: 

• Martin, John C., Introduction to Languages and the Theory of Computation, 3rd ed., Tata McGraw Hill Education Private Limited. 
• Keith Cooper and Linda Torczon, “Engineering a Compiler”, Second Edition, Morgan Kauffmann, 2011. 
• Andrew W. Appel and Jens Palsberg, “Modern Compiler Implementation in Java”, Cambridge University Press, Second Edition, 2002. 
• Tremblay and Sorenson, The Theory and Practice of Compiler Writing, Tata McGraw Hill & Company.