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.