Compiler Design

Set No. 1

Code No: 2320502

III B.Tech II Semester Regular Examinations, April/May 2009 COMPILER DESIGN (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆ 1. Explain the input buffer scheme for scanning the source program. How the use of sentinels can improve its performance? Describe in detail. [16] 2. (a) What are the difficulties in top down parsing? Explain in detail. (b) Consider the following grammar S → (L) |a L → L, S |S Construct leftmost derivations and parse trees for the following sentences: i. (a,(a,a)) ii. (a,((a,a),(a,a))).

[8+8]

3. C onstruct LALR Parsing table for the following grammar S → Aa|bAc|Bc|bBa A →d B→d

[16]

4. (a) Write a note on the specification of a simple type checker. (b) What is a type expression? Explain the equivalence of type expressions with an appropriate examples. [8+8] 5. (a) Compare three different storage allocation strategies. (b) Consider the following array declaration in ‘c’; float a[100][100]; Assume that the main memory in byte addressable and that the array is stored starting from the memory address 100. What is the address of a[40][50]?[8+8] 6. Explain different principal sources of optimization technique with suitable examples. [16] 7. (a) Write and explain live variable analysis algorithm. (b) Explain the use of algebraic transformations with an example

[8+8]

8. (a) Write an algorithm for generating code from a labeled tree. (b) Construct a DAG for the following program code: x=y*z w=p+y y=y*z p=w-x

[10+6] 1 of 2

Set No. 1

Code No: 2320502 ⋆⋆⋆⋆⋆

2 of 2

Set No. 2

Code No: 2320502

III B.Tech II Semester Regular Examinations, April/May 2009 COMPILER DESIGN (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆ 1. Explain the input buffer scheme for scanning the source program. How the use of sentinels can improve its performance? Describe in detail. [16] 2. (a) What are the difficulties in top down parsing? Explain in detail. (b) Consider the following grammar S → (L) |a L → L, S |S Construct leftmost derivations and parse trees for the following sentences: i. (a,(a,a)) ii. (a,((a,a),(a,a))).

[8+8]

3. Construct LALR parsing table for the following grammar S → A S|b A → S A|a

[16]

4. Write type expressions for the following types. (a) An array of pointers to reals, where array index ranages from 1 to 100. (b) A two dimensional array of integers (i.e. an array of array) whose rows are indexed from 0 to 9 and whose columns are indexed from -10 to 10. (c) Functions whose domains are functions from integers to pointers to integers and whose ranges are records consisting of an integer and a character. [5+5+6] 5. Explain in detail, about the various storage allocation schemes.

[16]

6. (a) What is frequency reduction? Explain with an example (b) Explain the following with suitable examples. i. ii. iii. iv.

Constant Propagation Strength Reduction Induction Variables Code Motion

[8+8]

7. What are the various primary structure-Preserving transformations on basic blocks? Explain each of them in detail. [16] 8. (a) Explain the concept of object code forms.

1 of 2

Set No. 2

Code No: 2320502

(b) Generate optimal machine code for the following C program. main() { int i, a[10]; while (i<=10) a[i] =0 }

⋆⋆⋆⋆⋆

2 of 2

[6+10]

Set No. 3

Code No: 2320502

III B.Tech II Semester Regular Examinations, April/May 2009 COMPILER DESIGN (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆ 1. Explain with an example, how LEX program performs lexical analysis for the following patterns in C : identifier, comments, constants, and arithmetic operators. [16] 2. (a) Consider the following grammar. S → 0A|1 B|0| 1 A → 0S|1 B| 1 B → 0 A|1 S Construct leftmost derivations and parse trees for the following sentences i. 0101 ii. 1100101 (b) Consider the following grammar E → T + E|T T → V∗ T|V V → id Write down the procedures for the nonterminals of the grammar to make a recursive descent parser. [8+8] 3. (a) Define LR(k) parser. Draw and explain model of LR parser. (b) Write LR parsing algorithm.

[8+8]

4. (a) Write a note on the specification of a simple type checker. (b) What is a type expression? Explain the equivalence of type expressions with an appropriate examples. [8+8] 5. (a) What is an ordered and unordered symbol table? What is the function of symbol table in the compliation process? Explain. (b) What are the various attributes of a Symbol Table?

[10+6]

6. (a) What is DAG? Construct the DAG for the following basic block D := B∗ C E :=A+B B := B+C A := E-D (b) What are the legal evaluation orders and names for the values at the nodes for the DAG of problem (a). 1 of 2

Set No. 3

Code No: 2320502

i. Assuming A, B and C are alive at the end of the basic block? ii. Assuming only A is live at the end?

[6+10]

7. A flow graph is useful for understanding code generation algorithm? Justify your answer with an example. [16] 8. (a) Explain the different issues in the design of a code generator. (b) Generate code for the following C statements: i. ii. iii. iv.

x= x= x= x=

f(a) + f(a) + f(a) f(a) /g(b,c) f(f(a)) ++f(a)

[8+8] ⋆⋆⋆⋆⋆

2 of 2

Set No. 4

Code No: 2320502

III B.Tech II Semester Regular Examinations, April/May 2009 COMPILER DESIGN (Computer Science & Engineering) Time: 3 hours Max Marks: 80 Answer any FIVE Questions All Questions carry equal marks ⋆⋆⋆⋆⋆ 1. (a) What is regular expression? Write regular expressions for the following patterns: identifiers and float constants. (b) Define lexeme, token and pattern. Identify the lexemes, that make up the tokens in the following program segment. Indicate corresponding token and pattern. [6+10] void swap(int i, int j) { int t; t=i; i=j; j=t; } 2. (a) Compare top down parsing and bottom up parsing. (b) Explain backtracking in top down parsing with an example. 3. Construct LALR parsing table for the following grammar. A′ → A A → (A) A→a

[8+8]

[16]

4. (a) Draw syntax tree for the arithmetic expressions a∗ (b + c) − d/2 Also write the given expression in postfix notation. (b) Write the quadruple, triple, indirect triple for the following expression (x + y)∗ (y + z) + (x + y + z) [8+8] 5. Only one occurrence of each object is allowable at a given moment during program execution. Justify your answer with respect to static allocation. [16] 6. (a) What is DAG? Construct the DAG for the following basic block D := B∗ C E :=A+B B := B+C A := E-D 1 of 2

Set No. 4

Code No: 2320502

(b) What are the legal evaluation orders and names for the values at the nodes for the DAG of problem (a). i. Assuming A, B and C are alive at the end of the basic block? ii. Assuming only A is live at the end?

[6+10]

7. Consider the following matrix multiplication Program begin for i := 1 to n do for j:=1 to n do c[i, j] :=0; for i := 1 to n do for j:=1 to n do for k :=1 to n do c[i, j] :=c[i , j] +a[i ,k] *b [k ,j] end (a) Construct a flow graph and find the loops in the flow graph (b) Move the loop-invariant computations out of the loops

[8+8]

8. (a) Explain the concept of object code forms. (b) Generate optimal machine code for the following C program. main() { int i, a[10]; while (i<=10) a[i] =0 }

⋆⋆⋆⋆⋆

2 of 2

[6+10]