Course Title: 
Compiler Design
Course Code: 
Year Taught: 
Postgraduate (PG)
School of Engineering

'Compiler Design' is a course offered in fifth semester of M. C. A. (Master of Computer Applications) program at School of Engineering, Amrita Vishwa Vidyapeetham, Amritapuri.

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.

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