COLLEGE NAME, BHOPAL
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
COURSE FILE
Program : B.E.
Semester : VII
Course Code :
Subject Name : Automata and Compiler Design
Prepared By: Approved By
Index
S.No. Contents Page No.
1. Scheme
2. Syllabus
3. Time Table
4. Lecture Plan
5. List of Books
6. Mid Semester Exam Question Papers
7. RGPV Question Paper
8. Tutorial Questions
9. Assignment Questions
10. Hand-Written Notes
11. Transparencies/PPT Slides
12. Mid Semester Exam Result
13. Attendance Sheet
PROGRAMME: B.E. Information Technology VII Semester
IT 704 Elective –I (IT- 713- Automata and Compiler Design)
Unit I: Introduction: Alphabets, Strings and Languages; Automata and Grammars, Deterministic finite Automata (DFA)-Formal Definition, Simplified notation: State transition graph, Transition table, Language of DFA, Nondeterministic finite Automata (NFA), Equivalence of NFA and DFA, Minimization of Finite Automata, Regular Expressions, Arden’s theorem.
Unit II: Compiler Structure: Compilers and Translators, Various Phases of Compiler, Pass Structure of Compiler, Bootstrapping of Compiler. Lexical Analysis: The role of Lexical Analyzer, A simple approach to the design of Lexical Analyzer, Implementation of Lexical Analyzer. The Syntactic Specification of Programming Languages: CFG, Derivation and Parse tree, Ambiguity, Capabilities of CFG. Basic Parsing Techniques: Top-Down parsers with backtracking, Recursive Descent Parsers, Predictive Parsers,
Unit III: Bottom–up Parsers, Shift-Reduce Parsing, Operator Precedence Parsers, LR parsers (SLR, Canonical LR, LALR) Syntax Analyzer Generator: YACC, Intermediate Code Generation: Different Intermediate forms: three address code, Quadruples & Triples. Syntax Directed translation mechanism and attributed definition. Translation of Declaration, Assignment, Control flow, Boolean expression, Array References in arithmetic expressions, procedure calls, case statements, postfix translation.
Unit IV: Run Time Memory Management: Static and Dynamic storage allocation, stack based memory allocation schemes, Symbol Table management Error Detection and Recovery: Lexical phase errors, Syntactic phase errors, Semantic errors.
Unit V: Code Optimization and Code Generation: Local optimization, Loop optimization, Peephole optimization, Basic blocks and flow graphs, DAG, Data flow analyzer, Machine Model, Order of evaluation, Register allocation and code selection
References:
1.Louden, “Compiler construction”, Cengage learning .
2. Alfred V Aho, Jeffrey D. Ullman, “Principles of Compiler Design”, Narosa.
3. A.V. Aho, R. Sethi and J.D Ullman, “Compiler: principle, Techniques and Tools”, AW.
4. Michal Sipser, “Theory of Computation”, Cengage learning.
5. H.C. Holub, “Compiler Design in C”, Prentice Hall Inc.
6. Hopcroft, Ullman, “Introduction to Automata Theory, Languages and Computation”, Pearson
Education.
Time Table
Department / Information Technology / Session : / 2014Name of Teacher / Sem / VII
Subject / Compiler Design / Sub. Code / IT-713
(B) TIME SCHEDULE : Total expected periods:___, Extra periods (if required)_____
Lecture Plan
Day / Mon / Tue / Wed / Thu / Fri / Sat / Max. availableNo. of
Periods / 01 / 01 / 01 / 01 / 01 / 01
Lecture. / Topics to be covered / Planned
Date of Completion / Remarks
UNIT-I
1 / Alphabets, Strings and Languages / R1:1, R2:1
2 / Automata and Grammars / R1:3, R2:1
3 / Deterministic finite Automata (DFA) / R1:10 , R2:5
4 / State transition graph, Transition table / R1:84,88,R2:74
5 / Nondeterministic finite Automata (NFA / R1:105, R2:103
6 / Equivalence of NFA and DFA, / R2:20
7 / Minimization of Finite
Automata / R1:725 ,R2:24
8 / Regular Expressions, Arden’s theorem / NOTES
Unit-II
9 / Compilers and Translators / R2:126
10 / Various Phases of Compiler / R2-147
11 / Pass Structure of
Compiler, Bootstrapping of Compiler / R1:215,193, R2:158
12 / The role of Lexical Analyzer / R1:215,193, R2:158
13 / A simple approach to the design of Lexical Analyzer, / R1:215,193, R2:158
14 / CFG, Derivation and Parse tree, / R1:52,207, R2:146
15 / Ambiguity, Capabilities of CFG. Basic Parsing / R1:215,193, R2:158
16 / Top-Down parsers with backtracking / R1:227,233,R3:148
17 / Recursive Descent Parsers / R1:257
18 / Predictive Parsers / R1:299,R5:154
Unit-III
24 / Bottom–up Parsers / R1:360,R4:83-89
25 / Shift-Reduce Parsing / R1:-350
26 / Operator Precedence Parsers / R1-366
27 / LR parsers / NOTES
28 / Syntax Analyzer Generator / R1:408,R5:252
29 / YACC, Intermediate Code Generation / R1:413,R5:278
30 / three address code / R2:328, R2:336
31 / Quadruples & Triples. / R1:478,R2:254
32 / . Translation of Declaration, Assignment / R1:500,R2:271
33 / Control flow, Boolean expression / NOTES
34 / Array References in arithmetic expressions / R1:526,R2:521
35 / procedure calls / R1:28
36 / case statements / R1:526,
37 / postfix translation / NOTES
Unit –IV
39 / Run Time Memory Management / R2-408
40 / Static and Dynamic storage allocation / R1:608,R2:410
41 / stack based memory
allocation schemes / R1:608,R2:410
42 / Symbol Table management Error Detection and Recovery / R2-408
43 / Lexical phase errors / R3:661
44 / Syntactic phase errors, Semantic errors / R2-408
Unit –V
45 / Code Optimization and Code Generation / R2-408
46 / Local optimization / R1:608,R2:410
47 / Loop optimization / R1:608,R2:410
48 / Peephole
optimization / R2-408
49 / Basic blocks and flow graphs / R3:661
50 / DAG / R2-408
51 / Data flow analyzer / R1:608,R2:410
52 / Machine Model / R1:608,R2:410
53 / Order of evaluation / R2-408
54 / Register allocation and code selection / R3:661
REFERENCE BOOKS
R1: Compilers Principles, Techniques, and Tools by Aho,Ullman & Sethi, Pearson Education
R2: Principles of Compiler Design by Aho & Ullman, Narosa Publishing House
R3:Compiler Construction 2/e: Dhamdhere
R4: Compiler Design by Santanu Chattopadhyay, PHI
R5: Compilers Construction & Design by Rajni Jindal, Umesh Publications
R6: Compiler Design by O. G. Kakde, Laxmi Publications (p) LTD
Websites:
1. www.cs.uccs.edu/~abudjen/classsnotes.doc
2. www.os.iitb.ac.in/~sri/notes/lexical.pdf
3. www.iitb.ac.in/~sri/notes/compiler/regex.pdf
List of Books
1. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and
Tools , Pearson Education
2 Raghavan, Compiler Design, TMH Pub.
3. Louden. Compiler Construction: Principles and Practice, Cengage Learning
4. A. C. Holub. Compiler Design in C , Prentice-Hall Inc., 1993.
5. Mak, writing compiler & Interpreters, Willey Pub.
COLLEGE NAME
MID SEMESTER I
BRANCH- IT
SEMESTER: VII
SUBJECT: COMPILER DESIGN
SUBJECT CODE: IT-713
Max. Marks: 40 Time: 2 Hours
Note: All questions are compulsory carry equal marks.
1. (a) What is Ad hoc network and how it differs from other network?
(b) Explain various challenges of mobile Ad hoc network.
2. What is Source and Receiver oriented MAC Routing Protocol?
3. Write the difference between-
a. Cellular and Mobile Ad hoc Network
b. Proactive and Reactive Routing protocol
4. Explain various design issues of Ad hoc Network in brief.
5. Explain the Working of DSDV Routing protocol
COLLEGE NAME
MID SEMESTER II
BRANCH- IT
SEMESTER: VII
SUBJECT: COMPILER DESIGN
SUBJECT CODE: IT-713
Max. Marks: 40 Time: 2 Hours
Note: Attempt any four questions.
1. / (a)(b) / Explain dynamic source routing (DSR) protocols with its advantages and disadvantages.
Evaluate the route discovery (RD) time parameter in the communication performance of ad-hoc network. / 5
5
2. / (a)
(b) / Describe the power management at various layers.
What are smart batteries? What are its characteristics ? / 5
5
3. / (a)
(b) / Explain the ATM cell header at UNI and at NNI.
What are the advantages and disadvantages of packet switching over circuit switching? / 5
5
4. / (a)
(b) / Draw and discuss the ATM protocol architecture model.
With neat sketch, explain architecture of 802.11 LAN. Also, explain its MAC logic. / 5
5
5. / Write short note on (any two)
i) ZRP protocol
ii) EED performance in ad-hoc network
iii) X.25
iv) AAL
------ / 10
COLLEGE NAME, Bhopal
Department of Information Technology
Assignment-1
Subject: Compiler Design
Subject Code: IT-713
Unit-1
1. Give the reasons for the separation of scanner and parser in separate phases of compiler.
2. Describe the role of lexical analyzer in recognizing tokens.
3. Explain the concept of input buffering.
4. Explain how tokens are recognized.
5. What is simple approach to design of lexical analyzer for an identifier.
6. What’s LEX? Describe auxiliary definitions and translation rules for LEX with suitable example.
7. What are the tasks performed by the compiler in lexical and syntax analysis phases. Explain with help of examples.
8. Explain role of symbol table in various phases of compiler
COLLEGE NAME, BhopalDepartment of Information Technology
Assignment-2
Subject: Compiler Design
Subject Code: IT-713
Unit-2
1. Write in brief about the error recovery procedure in LL and LR parsing.
2. Write short note on automatic parser generator.
3. Describe the function of LALR parser generator YACC.
4. What is meant by syntax directed translation?
5. Explain. Give the parse tree and translation for expression 23* 5+4 according to the syntax directed translation scheme.
6. Differentiate between synthesized translation and inherited translations.
7. Let the synthesized attribute “val”, give the integer value associated with non terminals in following grammar-
L→ E
E →E +T | T
T→ T*F | F
F→(E)| digit
8. Write a brief note on syntax tree.
9. For the following grammar find FIRST and FOLLOW sets for each non terminal-
S→aAB |bA|€
A→aAb|€
B→bB|€
Where € is Null string.
10. What is Shift-Reduce and Reduce-Reduce conflict? How these can be resolved? With examples explain in which condition S-R and R-R conflict can occur in SLR, Canonical LR and LALR parsers. (Make use of LR(0), LR(1) items.
COLLEGE NAME, BhopalDepartment of Information Technology
Assignment-3
Subject: Compiler Design
Subject Code: IT-713
Unit-3
1. What do you mean by heap allocation? Explain the following terms related to heap allocation-
(i) Fragmentation
(ii) Free list
(iii) Reference counts
2. Explain the difference between static, stack and heap allocation.
3. What is the difference between dynamic and static storage management?
4. What are different parameter passing mechanisms?
5. Explain with a suitable example, mechanisms, used by the compiler to handle procedure parameters.
6. Write short note on symbol table organization.
7. Explain various symbol table management techniques.
8. Explain various data structures used for implementing the symbol table and compare them.
9. What is hashing? What are different types of hashing techniques available?
COLLEGE NAME, BhopalDepartment of Information Technology
Assignment-4
Subject: Compiler Design
Subject Code: IT-713
Unit-4
1. Define Leaders.
2. Explain DAG construction.
3. What are applications of DAGs?
4. Write advantages of DAG.
5. Write short note on application of DAG in code generation.
6. Discuss the various methods of translating Boolean expression.
7. Construct DAG of basic block after converting code in 3-address representation-
Begin
Prod:=0;
i :=1;
do
begin
prod:= prod+a[i]*b[i];
i:=i+1;
end
while i<=20
end
8. Translate the following expression into quadruples, triples and indirect triples.
COLLEGE NAME, BhopalDepartment of Information Technology
Assignment-5
Subject: Compiler Design
Subject Code: IT-713
Unit-5
1. What is global data flow analysis? What is its use in code optimization?
2. Describe global data flow analysis.
3. Write the criteria for code improving transformations. Explain the principal sources of optimization.
4. Define dominators and write short note on loops in flow graph.
COLLEGE NAME, BhopalDepartment of Information Technology
Tutorial-1
Subject: Compiler Design
Subject Code: IT-713
Topic to be covered: Unit-1
9. Explain why one should study about the compilers.
10. Explain working of compilers drawing its block diagram.
11. What are the features of good compiler?
12. Compare and contrast the features of single pass compiler with multi pass compiler.
13. Write short note on bootstrapping.
14. Compiler uses two passes scheme of compilation, performing analysis, in first pass and synthesis in second pass. Explain what use is made of the symbol table in two passes of compiler.
15. Draw and explain various phases of compiler
16. Draw the block diagram of lexical and syntax analyzer and state clearly input , output and task performed by them.
COLLEGE NAME, BhopalDepartment of Information Technology
Tutorial-2
Subject: Compiler Design
Subject Code: IT-713
Unit-2
1. Write short note on grammar. What do you mean by ambiguity of grammar?
2. What is top down parsing? What are the difficulties encountered in this and how they overcome?
3. Write short note on recursive decent parser.
4. What is predictive parser? How a parser is controlled by a program?
5. Differentiate top down and bottom up parsing. Give examples of method of each type.
6. What is operator precedence grammar?
7. What Describe operator precedence parsing algorithm.
8. What are the limitations of operator precedence parsing?
9. What do you understand by LR(k) grammar?
10. Write the Algo/ Procedure for construction of canonical LR parsing table.
COLLEGE NAME, BhopalDepartment of Information Technology
Tutorial-3
Subject: Compiler Design
Subject Code: IT-713
Unit-3
1. Give a brief description of type checking.
2. Give the difference between implicit type conversion and explicit type conversion with help of an example.
3. Differentiate between static and dynamic binding.
4. Explain the importance of run time storage management in compiler.
5. What do you mean by activation record? Why this record is maintained by the compiler?
6. Explain various fields of activation record.
7. Describe storage allocation strategies.
8. What do you mean by static allocation? What are its drawback?
COLLEGE NAME, BhopalDepartment of Information Technology
Tutorial-4
Subject: Compiler Design
Subject Code: IT-713
Unit-4
9. Write a translation scheme to generate intermediate code for assignment statement with array references.
10. Write syntax directed definition to translate ‘switch’ statement. With a suitable example, show translation of the source language ‘switch’ statement.
11. Write short note on back patching.
12. Write short note on code generation.
13. What are general issues in designing a code generator?