Compiler Design - May 2016
VTU Computer Science (Semester 6)
Total marks: --
Total time: -- INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary 1(a) Explain with a neat diagram, the phases of a compiler. Mention the input and output for each phase with an example, 'position = initial + rate * 60'. 12 marks
1(b) Explain input buffering strategy used in lexical analysis phase. 12 marks
1(c) Construct a transition diagram for relational operators. 12 marks
2(a) Show that the following grammar is ambiguous:
E → E + E | E * (E) | id
Write an unambiguous grammar for the same. 12 marks
2(b) Given the grammar
S → (L) | α
L → L,S|S
i) Make necessary changes to make it suitable for LL(1) parsing.
ii) Construct FIRST and FOLLOW sets.
iii) Construct the predictive parsing table.
iv) Show the moves made by the predictive parser on the input (a, (a, b)). 12 marks
2(c) Write a recursive descent parser for the grammar: S → cAd, A → ab | a and for the input 'cad' trace the parser. 12 marks
3(a) Show that the following grammar is not LL(1) without constructing parsing table.
S → iCtSS' | α
S' → eS|∈
C → b 12 marks
3(b) What is meant by handle pruning? Show the working of a shift reduce parser for accepting id + id * id, considering grammar:
E → E + T | T
T → T*F | F
F → (E) | id 12 marks
4(a) Consider the following grammer:
S → L = R | R
L → *R | id
R → L
i) Obtain LR(0) items
ii) Compute FIRST and FOLLOW.
iii) Obtain SLR parsing table.
iv) Check whether the given grammer is SLR or not. 12 marks
4(b) Consider the following grammar:
S → AA
A → Aa | b
i) Compute sets of LR(1) items.
ii) Construct canonical LR(1) parsing table.
iii) Show the parsing steps for the string 'baaba'. 12 marks
5(a) For the given productions shown below, write semantic rules and construct annotated parse tree for 35+4n
L → En, E → EI+T, E → T, T → TIF, T → F, F → (E), F → digit 12 marks
5(b) Obtain SDD for simple type declaration. Construct a dependency graph for the declaration float a, b, c along with evaluation order. 12 marks
5(c) Define the following with examples:
i) S - attributed definitions
ii) L - attributed definitions 12 marks
6(a) Explain how DAG will help in intermediate code generation. Construct a DAG and a three address-code for the expression a+a(b-c)+(b-c)d 12 marks
6(b) Explain the following with an example:
i) Quadruples ii) Triples iii) Indirect triples 12 marks
6(c) Explain syntax directed translation of switch statement. 12 marks
7(a) Describe the general structure of an activation record. Explain the purpose of each item in the activation record. 12 marks
7(b) What is garbage collection? Explain the design goals of garbage collector. 12 marks
7(c) Define local and non-local data. 12 marks
8(a) Briefly explain various issues in code generation phase. 12 marks
8(b) Generate the 3-address statements for the following programming construct and obtain the basic blocks for generated code.
i = 1
sum = sum + a[i] * b[i]
i = i+1
while (i < =20) 12 marks