JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD 
III Year B.Tech. IT/CST - I Sem L T/P/D C 
4 -/-/- 4 
(A50513) AUTOMATA AND COMPILER DESIGN 

---

Objectives:

Automata and compiler Design mainly deals with the languages which are formal and regular and also deals with grammar present in the machine. An compiler is a program that accepts a program in source language and converts into a machine understandable format. The push down automata is the major one it's a five tuple set containing states, alphabets, transition function and accept states.

UNIT - I:

Formal Language and Regular Expressions : Languages, Definition Languages regular expressions, Finite Automata – DFA, NFA. Conversion of regular expression to NFA, NFA to DFA. Applications of Finite Automata to lexical analysis, lex tools. 

Context Free grammars and parsing : Context free grammars, derivation, parse trees, ambiguity LL(K) grammars and LL(1) parsing 

UNIT - II: 

Bottom up parsing handle pruning LR Grammar Parsing, LALR parsing, parsing ambiguous grammars, YACC programming specification. 

Semantics : Syntax directed translation, S-attributed and L-attributed grammars, Intermediate code – abstract syntax tree, translation of simple statements and control flow statements. 

UNIT - III:

Context Sensitive features – Chomsky hierarchy of languages and recognizers. Type checking, type conversions, equivalence of type expressions, overloading of functions and operations. 

UNIT - IV:

Run time storage : Storage organization, storage allocation strategies scope access to now local names, parameters, language facilities for dynamics storage allocation. 

Code optimization : Principal sources of optimization, optimization of basic blocks, peephole optimization, flow graphs, Data flow analysis of flow graphs. 

UNIT - V: 

Code generation : Machine dependent code generation, object code forms, generic code generation algorithm, Register allocation and assignment. Using DAG representation of Block. 

TEXT BOOKS: 

1. Introduction to Theory of computation.Sipser, 2nd Edition, Thomson. 
2. Compilers Principles, Techniques and Tools Aho, Ullman, Ravisethi, Pearson Education. 

REFERENCES: 

1. Modern Compiler Construction in C , Andrew W.Appel Cambridge University  Press. 
2. Compiler Construction, LOUDEN, Thomson. 
3. Elements of Compiler Design, A. Meduna, Auerbach Publications, Taylor and Francis Group.
4. Principles of Compiler Design, V. Raghavan, TMH.
5. Engineering a Compiler, K. D. Cooper, L. Torczon, ELSEVIER.
6. Introduction to Formal Languages and Automata Theory and Computation - Kamala Krithivasan and Rama R, Pearson.
7. Modern Compiler Design, D. Grune and others, Wiley-India.
8. A Text book on Automata Theory, S. F. B. Nasir, P. K. Srimani, Cambridge Univ. Press.
9. Automata and Language, A. Meduna, Springer.

Outcomes:

• Graduate should be able to understand the concept of abstract machines and their power to recognize the languages.
• Attainsthe knowledge of language classes & grammars relationship among them with the help of chomsky hierarchy.
• Ability to understand the design of a compiler given features of the languages.
• Ability to implement practical aspects of automata theory.
• Gain knowledge of powerful compiler generation tools.