Principles of Modern Compiler Design - Dec 2014

Computer Engineering (Semester 7)

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.

Answer any one question from Q1 and Q2

1 (a) Explain the interaction between Lexical Analyzer and Parser in first pass of compiler.(4 marks) 1 (b) Generate predictive parsing table for the given grammar and parse the string acbbgf.
S → a B D h
B → c C
C → b C/E
D → E F
E → g/E
F → f/F(10 marks) 1 (c) Differentiate between SLR, LR(K), and LAIR parsers.(4 marks) 10 (a) Explain: Issue in code generation.(6 marks) 10 (b) Determine cost of following instruction sequence. (Clearly mention your assumptions)
MOV b, R_o
ADD c, R_o
MOV R_o, a
MOV * R_{p * Ro}(6 marks) 10 (c) What is peephole optimization?(4 marks)

Answer any one question from Q11 and Q12

11 (a) Which are basic dataflow properties? Explain in detail.(8 marks) 11 (b) Given flow graph:
Generate IN, OUT, GEN and KILL sets for all blocks.

(8 marks) 11 (c) What is control ? flow analysis?(2 marks) 12 (a) Explain following optimizations with examples:
i) Common Subexpression Elimination
ii) Code movement
iii) Variable Propagation
iv) Strength reduction(8 marks) 12 (b) Explain: Meet Over Path (MOP) solution to data flow problems.(4 marks) 12 (c) Explain algorithm for global common subexpression elimination. (Support your answer with example flowgraph).(6 marks) 2 (a) Differentiate between top-down and bottom-up parsers.(4 marks) 2 (b) Generate SLR parsing table for the given grammar and parse the string id₁+id₂+id₃*id₄
E → E+T / T
T → T * F / F
F → id(8 marks) 2 (c) Explain: operator Precedence parser.(6 marks)

Answer any one question from Q3 and Q4

3 (a) Differentiate between S-attributed and L-attributed grammar.(4 marks) 3 (b) What is syntax tree? Give YACC specification to generate syntax tree for expression a+b*c.(8 marks) 3 (c) Explain: static & Dynamic checking of types.(4 marks) 4 (a) Discuss working of Recursive - Descent parser with suitable example.(6 marks) 4 (b) What is type checking? Give various type expressions.(6 marks) 4 (c) Explain in brief: syntax directed translation.(4 marks)

Answer any one question from Q5 and Q6

5 (a) Explain how boolean expressions are evaluated while generating intermediate code. Explain use of marker non-terminals and backpatching.(6 marks) 5 (b) Given code: a = b * c + d
write syntax directed translation scheme to translate above code into postfix notation.(6 marks) 5 (c) Explain: Need for Intermediate code(4 marks) 6 (a) Generate 3-addr code for following statements. specify the translation scheme used.
A[i] = B [i] + C
P = A [i](8 marks) 6 (b) Compare: Quadruple, Triple, Indirect Triple(6 marks) 6 (c) Generate Triple representation for following:
A = B * (C + D) / E(2 marks)

Answer any one question from Q7 and Q8

7 (a) Explain: Source Language issues(4 marks) 7 (b) Explain following
Call by Value
Call by Name
Call by Reference(6 marks) 7 (c) Discuss in detail the interaction of symbol table with various phases of compiler.(6 marks) 8 (a) Explain: Issue related to nested procedures.(4 marks) 8 (b) Explain run-time management of variable length data.(6 marks) 8 (c) Discuss storage organization and allocation strategies.(6 marks)

Answer any one question from Q9 and Q10

9 (a) What is DAG? Explain its use in code generation. Generate DAG:
T₁ = A+B
T₂ = C+D
T₃ = E-T₂
T₄ = T₁-T₃(8 marks) 9 (b) What is need for next- use information? Explain how to compute next ? use information.(6 marks) 9 (c) Explain the concept of basic block.(2 marks)