Compiler Design - Jun 2014

Computer Science Engg. (Semester 6)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) Explain the various phases of a compiler with the help of neat diagram.(8 marks) 1 (b) Give the formal definitions of operations on languages with notations.(4 marks) 1 (c) Write the transition diagram to recognize the taken below:
i) relop (relational operations)
ii) unsigned number.(8 marks) 2 (a) Give the rules for constructing FIRST and FOLLOW sets.(6 marks) 2 (b) Construct the predictive parsing table by making necessary changes to the grammar given below:
E → E+T|T
T → TF|F
F → (E) |id(10 marks) 2 (c) Give the formal definition of CFG with an example.(4 marks) 3 (a) What is a shift ? reduce parser? Explain the conflicts that may occur during shift-reduce parsing. List the actions of shift reduce parser.(6 marks) 3 (b) Form the Action / Goto table for the following grammar:
S → Aa bAc| Ba | bBa
A → d
B → d
Justify whether the grammar is LR(0) or not.(14 marks) 4 (a) Construct the canonical LR(1) item sets for the following grammar:
S → AA
A → aA|b(10 marks) 4 (b) Construct LALR parsing table for the grammar shown in Q4 (a) using LR(1) items.(10 marks) 5 (a) Define inherited and synthesized attributes. Given examples.(6 marks) 5 (b) Given the SDD for simple desk calculator and draw dependency graph for expression. 123(4+5)n(10 marks) 5 (c) Write SDD that generates either a basic type or an array type.(4 marks) 6 (a) Draw the DAG for the expression, a+a(b-c)+(b-c)d. Show the steps for constructing the same.(10 marks) 6 (b) Explain the following with examples: i) Quadruples ii) Triples.(6 marks) 6 (c) Write the three address code for the expression: a+a(b-c)+(b-c)d(4 marks) 7 (a) Give the general structure of an activation record. Explain the purpose of each component.(8 marks) 7 (b) Explain the performance metrics that must be considered while designing garbage collector.(8 marks) 7 (c) Give the memory hierarchy configurations of modern computer highlighting size and acces times.(4 marks) 8 (a) Explain the main issues in code generation.(10 marks) 8 (b) For the following program segment:
for i=1 to 10 do
for j=1 to 10 do
a[i, j]=0.0
for i=1 to 1o do
a[i, j]=10
Generate intermediate code and identify basic blocks.(10 marks)