VTU Previous Year Question Papers BE CS Sixth Semester
Compiler Design December 2010
Note: 1. Answer any FIVE full questions.
2. Any missing data may be suitably assumed
1 a. Explain the different phases of a compiler, with a neat diagram.
b. Explain the token generators and token recognizers, with a simple example.
c. Write a Lex program to recognize the string anb.
2 a. Define the following, with examples ;
i) Ambiguous grammar
ii) Derivation tree.
b. Show that the following grammar is ambiguous
S-I C t S |I C t S c S| a
Write the unambiguous grammar for the same.
c. Explain with an example, the recursive descent parser with backtracking.
3 a. Bring out the differences between top-down and bottom-up parsing methods.
b. Compute FIRST () and FOLLOW ( ) symbols for the following grammar and find if the grammar is LL(1)
E -» TE’
E’ -» + TF | e T FT T -> * FT’ | e
F —> (E)/ id.
c. Given the following precedence relation table, parse the string id + id * id
4 a. Explain with an example, the stack implementation of a shift reduce parser. (10 Marks) b. Define the following, with examples.
i) Synthesized attribute
ii) Inherited attribute
iii) Annotated parse tree
iv) Dependency graph.
5 a. What is an activation record? Explain the purpose of different fields in an activation record.
b. Explain the following storage allocation strategies.
i) Static allocation
ii) Heap allocation.
6 a. Define 3-address statement and list the types of 3-address statement. (08 Marks) b. Define the terms quadruples, triples and indirect triples. Give their representation for the assignment statement A = B * (C + D) by generating an appropriate 3-address code.
7 a. Explain the issues in the design of a code generator.
b. Generate the -code for the following three address statement, using the code generation algorithm t = a- b u = a-c v = t + u d = v + u with d live at the end.
8 a. Optimize the following code Product = 0 i = 1 do product = product + A[i] *B[i] i — i + 1 while (i < = 20).
b. Write algorithm to construct a DAG from a basic block.