Compiler Design - Jun 2015

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 a diagram, the phase of compiler.(8 marks) 1 (b) Write regular definitions for the following using extended regular expression notation:
i) identifier
ii) unsigned number.(6 marks) 1 (c) Write a program for look ahead code with sentinels.(6 marks) 2 (a) Define left- recursive grammar. Eliminate left recursion from the following grammar:
E → E + T | T
T → T * F | F
F → (E) | id.(5 marks) 2 (b) Given the grammar:
S → AaAb | BbBa
A → ∈
B → ∈
i) Compute FIRST() and FOLLOW() functions
ii) construct predictive parsing table
iii) Parse the input string w=ab.(9 marks) 2 (c) Show that the following grammar is ambiguous E → E +E | E * E | (E) | id , write an equivalent un-ambiguous grammar for the same.(6 marks) 3 (a) What is meant by handle pruning? Construct Bottom-up parse tree for the input string
w=aaaa ++. Using the grammar:
S → SS +| SS * | a.(6 marks) 3 (b) Explain the working of shift reduce parser. Parse the input string id * id. Using the grammar of question no 2(a).(8 marks) 3 (c) With a diagram, explain the model of an LR parser.(6 marks) 4 (a) Write an algorithm to construct LAIR parsing table.(6 marks) 4 (b) Construct the parsing table for LALR(1) parser using the grammar:
S → CC
C → aC
C → d.(10 marks) 4 (c) Compare LAIR and canonical LR parsers.(4 marks) 5 (a) Explain the concept of syntax directed definition.(4 marks) 5 (b) Consider the context free grammar given below:
S → EN
E → E+ T | E - T | T
T → T * F | T/F | F
F → (E) | digit
N →:
i) Obtain SDD for the above grammar
ii) Annotated parse tree for the input string 56+7.(10 marks) 5 (c) Define 1) Synthesized attribute and 2) Inherited Attirbute(6 marks) 6 (a) Construct DAG and three address code for the following expression
a+a(b-c)+(b-c)d.(8 marks) 6 (b) Explain the following with a example : i) quadruples ii) triples.(8 marks) 6 (c) Generate three address code for the following statement:
switch (ch)
{ case 1: c=a+b; break;
case 2: c=a-b; break;
}(4 marks) 7 (a) With a neat diagram the general structure of an activation record.(6 marks) 7 (b) Explain in the strategy for reducing fragmentation in heap memory.(8 marks) 7 (c) Explain briefly the performance metrics to be considered while designing a garbage collector.(6 marks) 8 (a) Discuss the various issues in the design of a code generator.(10 marks) 8 (b) What are basic blocks and flow graphs? Write an algorithm to partition the three address instruction into basic blocks.(6 marks) 8 (c) List the characteristics of a peephole optimization.(4 marks)