19EAI332: Automata Theory and Compiler Design
L T P C
3 1 0 4
Finite Automata comprises theoretical computer science to study abstract machines for
solving computation problems. Compilers play a significant role in fulfilling users’ computing
requirements, specified in programs in a high-level language, which translate into machine-
understandable form. The process involved in such a transformation of a program is quite
complex. This course intends to help the students learn the fundamentals of the theory of
computation that can recognize formal languages typically illustrated by the Chomsky
hierarchy and how this knowledge enables one to design a compiler. Automata Theory
provides the basis for developing a compiler.
Course objectives:
1. Impart the mathematical concepts of theoretical computer science from the
perspective offormal languages in solving computational machines.
2. Familiarize various formal languages, grammar, and their relationships.
3. Demonstrate various finite state machines and recognize formal languages.
4. Explore the basic techniques that underlie the principles, algorithms, and data structures in
Compiler Construction.
5. Gain experience in using automated tools that helps in transforming various phases of
the compiler.
Module I: Finite Automata and Regular Languages Number of hours(LTP) 9 3 0
Central concepts of strings, languages and automata theory, Regular expressions and
languages, Deterministic Finite Automata (DFA) and equivalence with Regular expression,
Non- Deterministic Finite Automata, and equivalence with DFA, Minimization of Finite
Automata by partitioning, Chomsky hierarchy of grammars
Learning Outcomes:
After completion of this unit, the student will be able to:
1. illustrate the central concepts of automata theory (L2)
2. construct Deterministic Finite Automata equivalent to Non-Deterministic Finite Automata (L3)
3. construct a Non-Deterministic Finite Automaton equivalent to a regular expression (L3)
4. build the equivalent minimized Deterministic Finite Automata (L3)
Module II: Grammars Number of hours(LTP) 9 3 0
Regular grammars equivalent with Finite Automata, Context-free grammars, and languages;
Parse trees; Applications; Ambiguity in grammars and Languages, Simplification of Context-
Free Grammars, Closure Properties of Context-Free Languages, Membership Algorithm
(CYK).Push down automata,equivalence of push down automata and context free grammar
Learning Outcomes:
After completion of this unit, the student will be able to:
1. classify the Chomsky hierarchy of grammars for formal languages (L2)
2. construct an unambiguous grammar from ambiguous grammar(L3)
3. decide whether a string belongs to a given context free language or not using
membership algorithm(L5)
Module III: Introduction to Compiler Design Number of hours(LTP) 9 3 0
The Structure of Compiler, The Science of Building a Compiler in Bootstrapping and Cross
compiler, The role of the Lexical analyzer, Input Buffering, Specification of Tokens, Recognition of
Tokens, The Lexical Analyzer Generator (LEX/FLEX).
150
Learning Outcomes:
After completion of this unit, the student will be able to:
1. summarizing various phases involved in the design of compiler construction(L2)
2. comparing methods involved in constructing the compiler(L2)
3. highlighting how regular expressions help to design the Lexical Analysis phase(L1)
4. exploring how LEX Tool simplifies the design of the Lexical Analysis phase(L2)
Module IV: Parsing Techniques Number of hours(LTP) 9 3 0
Top-Down parsing: Recursive Descent Parsing, Non-recursive Predictive Parsing, Bottom-Up
parsing - Shift Reduce Parsing, Simple LR Parser, More Powerful LR Parsers, Parser Generator
(YACC).
Learning Outcomes:
After completion of this unit, the student will be able to:
1. design the possible ways of constructing parsers (L3)
2. identifying the issues involved in creating an efficient Top-Down (LL) parser(L1)
3. implementing LR Parsers (L3)
4. illustrating the design of parser through YACC tool (L4)
Module V: Other Phases of Compiler Design Number of hours(LTP) 9 3 0
Intermediate Code Generation: Three Address codes, Code Optimization: The Principal
Sources of Optimization, Basic blocks, and Flow Graphs, Optimization of Basic Blocks, Code
Generation: Issues in designing a code Generator, The Target Language, A Simple Code
Generator, Peephole Optimization.
Learning Outcomes:
After completion of this unit, the student will be able to:
1. illustrating various techniques to store three address statements(L3)
2. identifying issues involved in the machine-independent code optimization(L1)
3. illustrating with a suitable example on local and loop optimization(L4)
4. estimating the processes involved in obtaining the final code (L2)
Text Books(s)
1. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata
Theory,Languages and Computation, 3/e, Pearson, 2008.
2. Alfred.V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey. D. Ullman, Compilers Principles,
Techniques and Tools, 2/e, Pearson Education, 2008.
Reference Book(s)
1. Alfred.V. Aho, J.D.Ullman, Principles of compiler design, Narosa Publications, 2002
2. Peter Linz, An Introduction to Formal Language and Automata, NarosaPub. House, Reprint
2000.
3. Michael Sipser, Introduction to Theory of Computation, 3/e, Wadsworth Publishing Co Inc,
2012.
Course Outcomes:
1. illustrate the concepts in the design of Finite State Machines to recognize Regular
Languages(L2)
2. analyze the relation between grammar and language, and design Context-Free Grammars
for formal languages (L4)
3. define and analyze various phases involved in developing a compiler(L1)
4. compare between bottom-up and top-down parsing techniques(L2)
5. identify different machine-independent optimization generating target code techniques(L4)
151
