FILE NO



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

[pic]

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 : |2014 |

|Name 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 |

| | | | | |

| | | | | |

| |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 | | |R1:725 |

| |Automata | | |,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 | | |R1:215,193, |

| |Compiler, Bootstrapping of Compiler | | |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,R|

| | | | |3:148 |

|17 |Recursive Descent Parsers | | |R1:257 |

|18 |Predictive Parsers | | |R1:299,R5:15|

| | | | |4 |

| |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:25|

| | | | |2 |

|29 |YACC, Intermediate Code Generation | | |R1:413,R5:27|

| | | | |8 |

|30 |three address code | | |R2:328, |

| | | | |R2:336 |

|31 |Quadruples & Triples. | | |R1:478,R2:25|

| | | | |4 |

|32 |. Translation of Declaration, Assignment | | |R1:500,R2:27|

| | | | |1 |

|33 |Control flow, Boolean expression | | |NOTES |

|34 |Array References in arithmetic expressions | | |R1:526,R2:52|

| | | | |1 |

|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 | | |R1:608,R2:410 |

| |allocation schemes | | | |

|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 | | |R2-408 |

| |optimization | | | |

|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. cs.uccs.edu/~abudjen/classsnotes.doc

2. os.iitb.ac.in/~sri/notes/lexical.pdf

3. 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.

| |(a) |Explain dynamic source routing (DSR) protocols with its advantages and disadvantages. |5 |

| | |Evaluate the route discovery (RD) time parameter in the communication performance of ad-hoc network. | |

| |(b) | |5 |

| |(a) |Describe the power management at various layers. |5 |

| |(b) |What are smart batteries? What are its characteristics ? |5 |

| |(a) |Explain the ATM cell header at UNI and at NNI. |5 |

| | | | |

| |(b) |What are the advantages and disadvantages of packet switching over circuit switching? |5 |

| |(a) |Draw and discuss the ATM protocol architecture model. |5 |

| | | | |

| |(b) |With neat sketch, explain architecture of 802.11 LAN. Also, explain its MAC logic. |5 |

| | |Write short note on (any two) |10 |

| | |ZRP protocol | |

| | |EED performance in ad-hoc network | |

| | |X.25 | |

| | |AAL | |

| | | | |

| | | | |

| | | | |

| | | | |

| | |------------------------------------------------ | |

| |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, Bhopal |

| |Department 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, Bhopal |

| |Department 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, Bhopal |

| |Department 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 b then x = a + b

else x = a - b

(b) Translate the following expression to quadruple, triple-

- (x + y) * (z + c) – (x + y + z)

OR

6. Write short notes on the following -

7. S- attributed definitions

8. L- Attributed definition

9. Dependency graph

10. (a) Explain the role of symbol table in various phases of compiler.

(b) What do you mean by heap allocation? Explain the following terms related to heap allocation-

11. Fragmentation

12. Free list

13. Bit map

14. Reference counts

OR

15. (a) Explain various storage allocation strategies. Which storage allocation model is to be used if a language permits recursion ?

(b) Describe parameter passing mechanisms for a procedure call.

16. (a) Describe the necessary and sufficient conditions for performing constant propagation and dead code eliminations.

(b) Write and explain data flow equations.

OR

17. Explain the following -

18. Loop invariant conditionals

19. Conditional depending on loop index

20. Independent loop conditionals

21. Reduction loops

***********************************************************************

Model Paper

CS-701

COMPILER DESIGN

Time - 3 Hrs

Max. Marks-100

Minimum Pass Marks - 35

Note - Solve any five questions. All questions carry equal marks.

1.(a) What is the basic task of scanning. What are the difficulties faced in delimeter oriented scanning. How can this be removed.

(b) What is the structure of a compiler. Discuss phases of a compiler briefly.

2. (a) What are errors can be encountered by virtually all the phases of a compiler.

(b) Explain the concept of transition diagram and its use in building a lexical analyzer.

3 (a) Why are multiple passes required in a compiler. Describe strategies for reducing the number of passes.

(b) What are data structures used for symbol tables management. Explain each of them in brief.

4(a) Comment on the need for indirection in symbol table.

(b) What is p-down parsing. What are the difficulties encountered in it and how are they overcome.

5(a) Write the quadruples, triples and indirection triples for the expression -

A ( B + C*D | E

(b) Why is the dynamic srage allocation strategy particularly amendable the run-time usage requirements of block structured languages. Write the procedure for run-time address calculation in our dynamic srage allocation mode.

6. (a) Describe Global Data Flow analysis. How is it useful in code optimization.

(b) Define the ambiguity of grammer. Suggest some possible solutions remove the ambiguity of a grammer.

7. Given a grammer with the following productions. -

S ( E

E ( T | E – T

T ( F | T * F

F ( i | (E)

• Generate the sets of LR (1) items

• Give a trtace of the Parse of the following input string (i – i) * i.

8. What is operar precedence grammer? For given the grammer:

E ( E + T | T

T ( T * F | F

F ( (E) | id

Obtain the following -

• Operator precedence matrix

• The parse for input string id + id

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download