Sixth Semester B.E. Degree Examination, June/July 2013 Compiler Design Question paper

Sixth Semester B.E. Degree Examination, June/July 2013 Compiler Design Time: 3 hrs. Max. Marks: 100 Note: Answer FIVEfull questions, selecting at least TWO questions from each part.

PART-A

1)a. Explain three types of software productivity tools.

b. Define sentinels. Give lookahead code with sentinels.              

c. Enlist algebraic laws for regular expressions. d. Give transition diagram for unsigned numbers.

2) a. Write an algorithm to eliminate left recursion from a grammar, also give the syntax of the production. (05 Marks)

b. Consider the production: S~aAb A~ cd/C. Show that recursive-descent parsing fails for the input string "acdb", also explain recursive descent algorithm. (07 Marks)

c. Find First and Follow for the given gplIl}J1lars: i) stmt_sequence ~ stmt stmtsequence' stmt_sequence' ~ ; stmtsequehce/ E stmt ~ s ii) S ~ ,GH; G~aF F ~ bF/E H~KL K ~ m/e L ~ nI E

3) a. What are two types of conflicts during shift reduce parsing? Give examples. (04 Marks)

b. For the given grammar E ~ E + n/n. Construct parsing table ofLL(l). Verify 3 + 4 + 5 and show each step of verification with reference to parsing table.

c. How to verify whether grammar is LL(l) or not? Show that: S ~ AaAb/B bBa A~E B~E is LL (1), without constructing any table. (OS Marks)

4) a. Construct the DFA ofLR(O) items and SLR parsing table for the grammar: Stmt_sequence ~ stmt_sequence; stmt/stmt Stmt ~ S Identify Kernel and non Kernal items in state 14.

b. Discuss the behaviour of the LR parser. c. For the grammar A ~ (A)/a, construct LR(1) set of items.

PART-B

5) a. Write annotated parse tree for 3*5 + 4n using Top down approach. Write semantic rules for each step. (08 Marks)

b. Discuss S-attributes and L-attributes with respect to SDD (Syntax Directed Definition). - (04 Marks)

c. By considering an array type int[3][3], write syntax directed translation with semantic niles. (08 Marks)

6) a. Enlist any four common three address instruction forms.

b. Define quandruples, triples and static single assignment form.

c. Write syntax directed definition for flow of control statements.

7) a. Write a- Version of quick sort, in ML style using the nested functions. Give any four additional features ofML. (08 Marks)

b. "Most progra'1ns exhibit a high degree oflocality", explain the statement.

c. "Garbage collection is seldom used in real time applications", justify the statement. How language design affects the characteristics of memory usage. (07 Marks)

8) a. How register allocation and evaluation order plays an important role in a code generation? Discuss. (06 Marks)

b. Write an intermediate code to set-a 10 x 10 matrix to an identity matrix. (10 Marks)

c. Define flow graph. How it is constructed? (04 Marks)

Editors