Question Paper: Compiler Design Question Paper - December 2015 - Computer Science (Semester 6) - Visveswaraya Technological University (VTU)
0

## Compiler Design - December 2015

### VTU Computer Science (Semester 6)

Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary
1 (a) With the help of a diagram, explain the various phases of a compiler. 10 marks

1 (b) What is meant by input buffering? Write an algorithm for look ahead code with sentinels. 10 marks

1 (c) Construct transition diagram to recognize the tokens below
(i) Identifier (ii) Relation operator (iii) unsigned number.
10 marks

2 (a) With a neat diagram explain the role of a parser. 10 marks

2 (b) Explain different error recovery strategies. 10 marks

2 (c) Consider the context free grammar S→SS+|SS|a And the string aa+a
i) Give a left most derivation for the string
ii) Give a right most derivation for the string
iii) Give a parse tree for the string
iv) Is the grammer ambiguous or unambiguous? Justify.
v) Describe the language generated by this grammar
vi) Remote the left recursion from the grammar?
vii) Left factor this grammar.
10 marks

3 (a) Given the grammar S→a|(L), L→L, S|S
i) Do the necessary changes to make it suitable for LL(1) parser
ii) Check the resultant grammar is LL(1) or not
iii) Show the moves made by the predictive parser on the input (a, (a, a)).
10 marks

3 (b) What is meant by handle pruning? List the actions of shift reduce parser. Consider the following grammar
S→TL;
T→int|float
L→L, id | id parse the input string int id, id; using shift reduce parser.
10 marks

4 (a) Given the grammar
S→AA
A→Aa|b
i) Construct sets of LR(1) items
ii) Construct canonical LR(1) parsing table
10 marks

4 (b) How LALR parsing table is constructed? Develop an algorithm for the same. 10 marks

5 (a) Give the syntax directed definition to process a sample variable declaration in C and construct dependency graph for the input float x,y,z. 10 marks

5 (b) Write the grammar and syntax directed definitions for a simple desk calculator and show annotated parse tree for the expression 3*5+4n. 10 marks

6 (a) Draw the DAG for the arithmetic expression.
a+a(b-c)+(b-c)d. Show the steps for constructing the DAG.
10 marks

6 (b) What are three address codes? Explain different ways of representing three address codes, with examples. 10 marks

7 (a) Distinguish between static scope and dynamic scope. Briefly explain access to non-local names in static scope. 10 marks

7 (b) Explain in detail, the strategy for reducing fragmentation in heap memory. 10 marks

8 (a) Discuss the following terms:
(i) Basic blocks (ii) Next use information (iii) Flow graph.
10 marks

8 (b) With example, explain common subexpression and dead code elimination methods. 10 marks