Principles of Modern Compiler Design - May 2015

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 various phases of compiler with example. List various errors detected in each phase of compiler.(8 marks) 1 (b) Design SLR parsing table for following grammar:
S → AS|b
A → SA|a(8 marks) 1 (c) Compare Recursive Descent parser and predictive parser.(2 marks) 10 (a) What are different issues in code generation?(6 marks) 10 (b) Explain simple code generation algorithm. Generate code for following 'C' program.
Main ( )
{
int i;
int a [10];
while (i ? 10)
a [i] = 0;
}(10 marks)

Answer any one question from Q11 and Q12

11 (a) Discuss the principle sources of code optimization. Give proper examples wherever necessary.(8 marks) 11 (b) Explain fundamental data flow properties.(8 marks) 12 (a) What is 'ud chain'? Explain Gen set and Killset for ud chain.(6 marks) 12 (b) What is Global common sub-expression? Write an algorithm for elimination of Global common sub-expression.(6 marks) 12 (c) Explain in brief:
i) Reaching definitions
ii) Live variables(4 marks) 2 (a) Why Lexical analyzer and parser are two separate phases? How they are combined in single pass?(4 marks) 2 (b) Show that following grammar is LR (1) but not LALR.
S → Aac|Bc|bBa
A → d
B → d(8 marks) 2 (c) Test whether following grammar is LL (1)?
S → iEtSS'|a
S' → eS|∈
E → b(6 marks)

Answer any one question from Q3 and Q4

3 (a) What is the need of type checking and type analysis?(4 marks) 3 (b) What are synthesized and inherited attributes? Give proper examples.(4 marks) 3 (c) What are advantages of Syntax Directed Translation (SDT)? Explain how intermediate code is generated using Top-down translation scheme.(8 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) Differentiate between L-attributed definition and S-attributed definition.(4 marks) 4 (c) What is semantic analysis? Give some examples of errors that are detected during semantic analysis.(4 marks)

Answer any one question from Q5 and Q6

5 (a) Explain commonly used intermediate code representations. Give one example for each.(8 marks) 5 (b) Write a syntax directed translation scheme for ?if E then S?. Generate code for following statement using the above scheme: if ad then a = b +c.(8 marks) 6 (a) Give syntax directed translation scheme for Assignment statement.(6 marks) 6 (b) Explain syntax directed translation scheme for Arrays. Generate quadruples for the following:
A [i] [j] = B [i] [j] + C [i] [j]
where A, B and C are arrays of size 10×20.(10 marks)

Answer any one question from Q7 and Q8

7 (a) Explain following storage allocation schemes with proper examples.
i) Stack storage allocation
ii) Static storage allocation
iii) Heap storage allocation(12 marks) 7 (b) For the following 'C' program, show the details of the activation records, if
i) Stack allocation is used
ii) Heap allocation is used

main ( )
{
int * p;
p = fun ( );
}
int * fun ( )
{
int i = 23;
return & i;
}(6 marks) 8 (a) Explain following parameter passing techniques using suitable examples. Call by value, call by reference, call restore, call by name(8 marks) 8 (b) Compare static scope with dynamic scope. Illustrate with suitable example.(10 marks)

Answer any one question from Q9 and Q10

9 (a) Explain Dynamic programming algorithm for code generation.(8 marks) 9 (b) Explain with example:
i) Basic blocks and flow graph
ii) Peephole optimization(8 marks)