Compiler Design - Dec 2013

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 compiler. Show the translations for an assignment statement. Position= initial+rate60, clearly indicate the output of each phase.(12 marks) 1 (b) Write the regular definition for an unsigned number. Also write the transition diagram.(6 marks) 1 (c) What is printed by the following C code?
#define a(x+1)
int x=2;
void b() {int x=1; printf("%d ln".a);}
void c() {printf("%d ln", a);}
void main() {b(): c();}(2 marks) 2 (a) Describe an algorithm used for eliminating the left recursion. Eliminate left recursion from the grammar:
S→Aa|b A→Ac|Sd|a.(6 marks) 2 (b) Show that the following grammar is ambiguous:
E→E+E|EE|(E)| id. Write an equivalent unambiguous grammar for the same.(6 marks) 2 (c) What are the key problems with top down purse? Write a recursive descent parser for the grammar:
S→cAd A→ab|a.(8 marks) 3 (a) Given the grammar:
S →aABb
A → c|ϵ
B → d|ϵ
i) Compute FIRST and FOLLOW sets
ii) Construct the predictive parsing table
iii) Show the move made by predictive parser on the input: acdb.(10 marks) 3 (b) Explain with a neat diagram, the model of a table drive predictive parser.(5 marks) 3 (c) What is handle pruning? Give a botton-up parse for the input: aaaa++ and grammar: S → SS + |SS * | a.(5 marks) 4 (a) Given the grammar:
S → CC
C → cC|d
i) Obtain the sets of canonical collection of set of valid LR(0) items
ii) Design SLR parsing table.(10 marks) 4 (b) Write an algorithm used to compute LR(1) sets of items.(6 marks) 4 (c) Write a note on the parser Generator - Yacc.(4 marks) 5 (a) Explain the concept of syntax - directed definition.(5 marks) 5 (b) The SDD to translate binary integer number into decimal is shown below:

Construct the parse tree and annotated parse tree for the input string: 11001.(5 marks) 5 (c) Given a SDI for desktop calculator and show its parse stack implementation.(10 marks) 6 (a) Translate the arithmetic expression: a+ - (b+c) into quadruples, triples and indirect triples.(6 marks) 6 (b) Give a semantic action for: S → if (B) S₁ else S₂;(6 marks) 6 (c) Develop SDD to produce directed a cycle graph for an expression. Show the steps for constructing the directed acyclic graph for the expression: a+a(b-c)+(b-c)*d(8 marks) 7 (a) Describe the general structure of an activation record. Explain the purpose of each field in the activation record.(8 marks) 7 (b) A C code to compute Fibonacci numbers recursively is shown below:
int f(int n)
{ int t, s;
if (n<=2) return 1;
s=f(n-1);
t=f(n-2);
return (s+1);
}
i) Draw the activation tree for the call: f(5)
ii) What is the largest number of activation records that ever appear together on the stack>(6 marks) 7 (c) Explain the performance metrics to be considered while designing a garbage collector.(6 marks) 8 (a) Discuss the issues in the design of a code generator.(10 marks) 8 (b) Write the tree address code and construct the basic blocks for the following program segment.
sum =0;
for (i=0; i<=10; i++)
sum=sum+a[i];(5 marks) 8 (c) Give the code generation process for operations.(5 marks)