Compiler Design - Dec 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 with neat diagram, the phase of compiler with example.(10 marks) 1 (b) Construct a transition diagram for recognizing relational operators. Sketch the program segment to implement it, showing the first state and one final state.(10 marks) 2 (a) Briefly explain the problems associated with top down parser.(3 marks) 2 (b) Show that following grammar is ambiguous: S → S+S|SS|id. Give an unambiguous grammar for the above grammar such that '+' has highest priority and * has less priority and both are left associative.(7 marks) 2 (c) Given the grammar A → (A)/a
i) Construct predictive parser table
ii) Check the grammar is LL(I) or not.
iii) Show the parser steps for the input ((a)).(10 marks) 3 (a) Obtain LR(0) items for the following grammar:
S→L→R| R L→ R| id R → L.(8 marks) 3 (b) Obtain FIRST and FALLOW sets for the grammar shown in Q3 (a) and obtain SLR parsing table. Is the grammar SLR?(12 marks) 4 (a) Given the grammar: A →CC C→aC|b
i) Construct sets of LR(1) items
ii) Construct canonical LR(1) parsing table.(12 marks) 4 (b) Write a note on the parse generator - YACC.(3 marks) 4 (c) Write the YACC specification of a simple desk calculator with following grammar for arithmetic expression:
E → E+T|T
T→TF|F
F→(E)| digit where digit between 0 to 0.(5 marks) 5 (a) Explain type of attributes for non terminal with example.(4 marks) 5 (b) Write annotated parse tree for expression 5+43n where grammar is
L→En
E → E + T|T
T → T * F|F
F → (E) | digit(6 marks) 5 (c) How different classes of SDD's that guarantee evaluation order?(6 marks) 5 (d) Obtain postfix SDT for simple desk calculator.(4 marks) 6 (a) Obtain the directed a cyclic graph for the expression x+x*(y+z) + (y+z)=w.(6 marks) 6 (b) Explain the following with example:
i) Quadruples ii) Triples
iii) Indirect triples(6 marks) 6 (c) Explain SDT of switch statement.(8 marks) 7 (a) What is activation records? Explain structure and purpose of each field in the activation record.(6 marks) 7 (b) Explain tasks of caller and callee when procedure called and exit.(8 marks) 7 (c) Explain briefly the performance metric to be considered while designing garbage collector.(6 marks) 8 (a) Write intermediate code for the following source code:
for i from 1 to 10 do
for j from 1 to 10 do
a[i, j]=0.0;
for i from 1 to 10 do
a [i, j]=1.0;
and identify basic blocks.(10 marks) 8 (b) Discuss the issues in the design of a code generator.(10 marks)