To understand a finite automata for a given language.
To understand the relation between grammar and language
To understand the basic principles of working of a compiler
To study about the type checking procedure during the compilation
To understand the storage structure of the running program
UNIT I AUTOMATA 9
Introduction to formal proof – Additional forms of proof – Inductive proofs –Finite Automata (FA) – Deterministic Finite Automata (DFA) – Non-deterministic Finite Automata (NFA) – Finite Automata with Epsilon transitions- Equivalence and minimization of Automata.
UNIT II CONTEXT FREE GRAMMARS AND LANGUAGES 9
Context-Free Grammar (CFG) – Parse Trees – Ambiguity in grammars and languages – Definition of the Pushdown automata – Languages of a Pushdown Automata – Equivalence of Pushdown automata and CFG– Deterministic Pushdown Automata- Normal forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines – Programming Techniques for TM.
UNIT III BASICS OF COMPILATION 9
Compilers – Analysis of source program – Phases of a compiler – Grouping of phases – Compiler construction tools – Lexical Analyzer : Token Specification – Token Recognition – A language for Specifying lexical analyzer – Top down parser : Table implementation of Predictive Parser – Bottom up Parser : SLR(1) Parser – Parser generators.
UNIT IV TYPE CHECKING AND RUNTIME ENVIRONMENTS 9
Syntax directed definitions – Construction of syntax trees – Type systems – Specification of a simple type checker- Equivalence of type expressions – Type conversions – Attribute grammar for a simple type checking system – Runtime Environments: Source language issues – Storage organization – Storage allocation strategies – Parameter passing.
UNIT V CODE GENERATION AND OPTIMIZATION 9
Issues in the design of a code generator – The target machine – Run-time storage management – Basic blocks and flow graphs – Next-use information – A simple code generator – Register allocation and assignment – The dag representation of basic blocks – Generating code from DAG – Dynamic programming code generation algorithm – Code generator generators – Code optimization.
TOTAL: 45 PERIODS
OUTCOMES: Upon completion of the course, the students should be able to :
Design a finite automaton for a specific language.
Design a Turing machine.
Select appropriate grammar for the implementation of compiler phases
Design a lexical analyzer
Design a simple parser
Design and implement techniques used for optimization by a compiler.
Write a very simple code generator
- J.E. Hopcroft, R. Motwani and J.D. Ullman, ―Introduction to Automata Theory, Languages and Computations‖, Second Edition, Pearson Education, 2007. 2. Alfred V. Aho, Monica S.Lam, Ravi Sethi, Jeffrey D.Ullman, ―Compilers :Principles, Techniques and Tools‖, Second Edition, Pearson Education,2008.
- 1. J.Martin, ―Introduction to Languages and the Theory of computation‖ Third Edition, Tata Mc Graw Hill, 2007
- Randy Allen, Ken Kennedy, ―Optimizing Compilers for Modern Architectures: A Dependence-based Approach‖, Morgan Kaufmann Publishers, 2002.
- Steven S. Muchnick, ―Advanced Compiler Design and Implementation‖, Morgan Kaufmann Publishers – Elsevier Science, India, Indian Reprint 2003.
- Muneeswaran. K, ―Compiler Design‖, Oxford University Press, 2012