Principles of Modern Compiler Design - May 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 design of compiler with front end and back end arrangement. Clearly mention the advantages achieved.(6 marks) 1 (b) Check whether following grammar is LL(1). Also depict the moves by parser for input string 'ab'.
i) S -> aABb
A -> c|ε
B -> d|ε(8 marks) 1 (c) Define: Token, Lexical error, Regular Expression, Cross compiler.(4 marks) 10 (a) Discuss various issues in code generation.(4 marks) 10 (b) Explain: Dynamic programming algorithm for code generation.(8 marks) 10 (c) What is peephole optimization?(4 marks)

Answer any one question from Q11 and Q12

11 (a) What is copy propagation? Illustrate how copy propagation facilitates other optimization opportunities.(6 marks) 11 (b) Draw a sample flow graph. Explain generation and killing of expressions with respect to the flow graph.(6 marks) 11 (c) What are induction variables? Explain with example how induction variables help in loop optimization?(6 marks) 12 (a) Consider following basic blocks:
i) T₁b+c
T₂=dc
T₃=b+c

T₄=T₂T₃
T₅=T₄*f
x=T₁-T₅
Which of the local optimization techniques are possible to be carried out with above basic block?(6 marks) 12 (b) Compare quadruples, triples and indirect triples with respect to their use in code optimization.(6 marks) 12 (c) Explain following terms:
Available expression
Reaching definition
Live variable(6 marks) 2 (a) Compare SLR, LR (1) and LALR parser generation methods(6 marks) 2 (b) Construct LR(1) parsing table for following grammar:
S → Aa|bAc|Bc|bBa
A → d
B → d(8 marks) 2 (c) Explain the working of Operator Precedence parser.(4 marks)

Answer any one question from Q3 and Q4

3 (a) How do we evaluate synthesized and inherited attributes in the semantic rules during bottom-up parsing? Illustrate with example.(8 marks) 3 (b) What is type expression? Write type expression for following: An array of pointer to real where array index ranges from 1 to 50.(4 marks) 3 (c) What is semantic analysis? Give an example of error that is detected during semantic analysis.(4 marks) 4 (a) What is type casting? Explain implicit and explicit type casting with example. What changes should be made in semantic analyzer to add type casting.(8 marks) 4 (b) What is type checking?(2 marks) 4 (c) Construct a top-down parser for generating intermediate code for declarative statement in C language.(6 marks)

Answer any one question from Q5 and Q6

5 (a) Write CFG for following statement:
While condition do S. Write syntax directed translation to translate this statement in Three address code.(8 marks) 5 (b) Translate following statement into three address code:
C[i][j] = A[i][j] + B[i][j]
Assume suitable values.(6 marks) 5 (c) Compare triple and indirect triple.(2 marks) 6 (a) How is a switch case statement translated into three address code? Illustrate with an example.(8 marks) 6 (b) Discuss the advantages and disadvantages of short circuit evaluation of Boolean expression with example.(4 marks) 6 (c) Generate three address code in the form of Quadruple:
If (a < b) then
While (c > d) do x = p*q(4 marks)

Answer any one question from Q7 and Q8

7 (a) Discuss the need for symbol table with compiler. Explain different symbol table organizations.(8 marks) 7 (b) Define Activation record. Explain with example, the elements of activation record.(8 marks) 8 (a) Explain with example various parameter passing techniques.(8 marks) 8 (b) Compare and Contrast static storage management and dynamic storage management.(8 marks)

Answer any one question from Q9 and Q10

9 (a) Explain advantages of dividing the three address statements into basic blocks.(4 marks) 9 (b) With a proper example, explain algorithm for labelling a tree.(6 marks) 9 (c) What is register allocation and assignment problem?(6 marks)