Automata and Language: Chomsky hierarchy of languages, Introduction to Finite Automata –Non-Deterministic Finite Automata- equivalence of NFAs and DFAs- minimization of DFA-Regular Expressions. Context-free Grammar – Parse tree derivations (Top-down, Bottom-up), Context-free languages – Chomsky normal form, GNF.

Introduction to Compilers: Compiler structure – Overview of Translation. Lexical Analysis: From regular expression to Scanner. Implementation of scanner: Lex – Parsers: Expressing syntax – Top-down parsing: Recursive descent parsing, Non-recursive predictive parsing. Bottom-up parsing: LR(0), LR(1) and LALR(1) – Implementation of Parser – YACC

Context-Sensitive Analysis: Type Systems – Attribute – Grammar – Syntax Directed Translation. Intermediate Representations: Graphical and Linear Intermediate Representations – Symbol tables. Procedure Abstraction: Procedure calls – Name Spaces – Communicating Values between Procedures.

Iterative Data Flow Analysis – Instruction selection via Tree Pattern Matching – Register allocation: Local and Global – Introduction to Optimization.

1. Peter Linz, “An Introduction to Formal Languages and Automata”, Fifth Edition, 2012.
2. Keith Cooper and Linda Torczon, “Engineering a Compiler”, Second Edition, Morgan Kauffmann, 2011.
3. Alfred V.Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, “Compilers: Principles, Techniques and Tools”, Prentice Hall, Second Edition, 2006.
4. Andrew W. Appel and Jens Palsberg, “Modern Compiler Implementation in Java”, Cambridge University Press, Second Edition, 2002.