Automata Theory and Compiler Design

Unit 1: Introduction to Compilers

• Phases of the Compiler
• Formal Language and Regular Expressions:
  • Languages
  • Operations on Languages
  • Regular Expressions
• Finite Automata:
  • Deterministic Finite Automata (DFA)
  • Non-Deterministic Finite Automata (NFA)
  • Conversion of Regular Expression to NFA
  • ε-NFA (NFA with ε-moves)
  • Conversion of ε-NFA to NFA and DFA

Unit 2: Syntax Analysis

• Context-Free Grammar (CFG):
  • Introduction to CFG
  • Derivation and Parse Trees
  • Ambiguity in CFG
  • Left Factoring
  • Left Recursion
• Parsing Techniques:
  • Top-Down Parsing
  • Recursive Descent Parsers
  • LL(k) Parsers
  • Bottom-Up Parsing
  • Shift-Reduce Parsing
  • LR Parsers: SLR, CLR, LALR

Unit 3: Syntax-Directed Definitions and Intermediate Code Generation

• Syntax-Directed Definitions:
  • Construction of Syntax Trees
  • Bottom-Up Evaluation of S-Attributed Definitions
  • L-Attributed Definitions
• Intermediate Code Generation:
  • Different Intermediate Forms
  • Symbol Table

Unit 4: Code Optimization and Code Generation

• Code Optimization:
  • Principal Sources of Optimization
  • Optimization of Basic Blocks
  • Loops in Flow Graphs
  • Global Data Flow Analysis
  • Peephole Optimization
• Code Generation:
  • Issues in Design of Code Generator
  • Simple Code Generator
  • Register Allocation and Assignment
  • Directed Acyclic Graph (DAG) Representation of Basic Blocks