PRINCIPLES OF COMPILER DESIGN (POCD)–April / May 2011 Question Paper

Anna University

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2011

Sixth Semester

Computer Science and Engineering

CS 2352 — PRINCIPLES OF COMPILER DESIGN

(Regulation 2008)

---

Time : Three hours

Maximum : 100 marks

Answer ALL questions

---

PART A — (10 × 2 = 20 marks)

1. What is an interpreter?

2. Define token and lexeme.
3. What is handle pruning?
4. What are the limitations of static allocation?
5. List out the benefits of using machine-independent intermediate forms.
6. What is a syntax tree? Draw the syntax tree for the following statement:
. : c b c b a − ∗ + − ∗ =
7. List out the primary structure preserving transformations on basic block.
8. What is the purpose of next-use information?
9. Define dead-code elimination.
10. What is loop optimization?

---

PART B — (5 × 16 = 80 marks)

11. (a) (i) Describe the various phases of complier and trace the program
segment 4 : ∗ + = c b a for all phases. (10)

(ii) Explain in detail about compiler construction tools. (6)
Or
(b) (i) Discuss the role of lexical analyzer in detail. (8)

(ii) Draw the transition diagram for relational operators and unsigned
numbers in Pascal. (8)

12. (a) (i) Explain the error recovery strategies in syntax analysis. (6)

(ii) Construct a SLR construction table for the following grammar.
T E E + →
T E →
F T T ∗ →
F T →
( ) E F →
id F → (10)

Or

(b) (i) Distinguish between the source text of a procedure and its
activation at run time. (8)

(ii) Discuss the various storage allocation strategies in detail. (8)

13. (a) (i) Define three-address code. Describe the various methods of implementing three-address statements with an example. (8)

(ii) Give the translation scheme for converting the assignments into
three address code. (8)
Or
(b) (i) Discuss the various methods for translating Boolean expression. (8)

(ii) Explain the process of generating the code for a Boolean expression in a single pass using back patching. (8)
132  132  132 
11267 3

14. (a) (i) Write in detail about the issues in the design of a code generator. (10)
(ii) Define basic block. Write an algorithm to partition a sequence of
three-address statements into basic blocks. (6)

Or

(b) (i) How to generate a code for a basic block from its dag
representation? Explain. (6)
(ii) Briefly explain about simple code generator. (10)

15. (a) (i) Write in detail about function-preserving tran

sformations. (8)
(ii) Discuss briefly about Peephole Optimization. (8)

Or

(b) (i) Write an algorithm to construct the natural loop of a back edge. (6)
(ii) Explain in detail about code-improving transformations. (10)

 

PRINCIPLES OF COMPILER DESIGN (POCD)–Nov / Dec 2011 Question Paper

Anna university

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.

Sixth Semester

Computer Science and Engineering

CS 2352 — PRINCIPLES OF COMPILER DESIGN

(Regulation 2008)

---

Time : Three hours

Maximum : 100 marks

Answer ALL questions.

---

PART A — (10 × 2 = 20 marks)

1. What is the role of lexical analyzer?

2. Give the transition diagram for an identifier.

3. Define handle pruning.

4. Mention the two rules for type checking.

5. Construct the syntax tree for the following assignment statement: a:=b*- c+b*-c.

6. What are the types of three address statements?

7. Define basic blocks and flow graphs.

8. What is DAG?

9. List out the criterias for code improving transformations.

10. When does dangling reference occur?

---

PART B — (5 × 16 = 80 marks)

11. (a) (i) Describe the various phases of compiler and trace it with the program segment (position: = initial + rate * 60). (10)

(ii)

State the complier construction tools. Explain them. (6)

Or

(b) (i) Explain briefly about input buffering in reading the source

program for finding the tokens. (8)

(ii) Construct the minimized DFA for the regular expression

(0+1)*(0+1) 10. (8)

12. (a) Construct a canonical parsing table for the grammar given below.

Also explain the algorithm used. (16)

E → E + T

F → (E )

E → T

F → id .

T → T * F

T → F

Or

(b) What are the different storage allocation strategies? Explain. (16)

13. (a) (i) Write down the translation scheme to generate code for assignment statement. Use the scheme for generating three address code for the assignment statement g: = a+b-c*d. (8)

(ii) Describe the various methods of implementing three-address statements. (8)

Or

(b) (i) How can Back patching be used to generate code for Boolean expressions and flow of control statements? (10)

(ii) Write a short note on procedures calls. (6)

14. (a) (i) Discuss the issues in the design of code generator. (10)

(ii) Explain the structure-preserving transformations for basic

blocks. (6)

Or

(b) (i) Explain in detail about the simple code generator. (8)

(ii) Discuss briefly about the Peephole optimization. (8)

15. (a) Describe in detail the principal sources of optimization. (16)

Or

(b) (i) Explain in detail optimization of basic blocks with example. (8)

(ii) Write about Data flow analysis of structural programs. (8)

---