Compiler Design 2018 Question Paper — Government College of Engineeri…

The 2018 Compiler Design previous year question paper (Government College of Engineering and Technology, Jammu), with every question and its marks.

Instructions

Attempt five questions in all selecting at least two questions from each Section.
Each question carries 20 marks.

Attempt at least two questions from this Section.

Q1. (a) Explain all the necessary phases and passes in compiler design. Write down the purpose of each pass. (b) What do you understand by left factoring? Consider the following grammar $S \rightarrow iEtS \mid iEtSeS \mid a$ $E \rightarrow b$ Write the procedure for the above to eliminate left factoring. [20 marks]
Q2. (a) (i) What is a Regular Expression? List and explain the rules that define a regular expression. (ii) Design a DFA over an alphabet $\Sigma = \{a, b\}$ that accepts all the strings ending with 'ab'. Process a string 'aabab' in this finite automata. (b) Consider the grammar $S \rightarrow iCtSS' \mid a$ $S' \rightarrow eS \mid \varepsilon$ $C \rightarrow b$ (i) Compute FIRST and FOLLOW for the above grammar. (ii) Construct the predictive parsing table for the above grammar and check whether the grammar is LL (1) or not. [20 marks]
Q3. (a) Explain basic parsing techniques. What is top down parsing? (b) Give a formal definition of context - free grammar (CFG). Discuss role of parser in compiler design. Consider the following CFG: $E \rightarrow E+E \mid E-E$ $E \rightarrow E*E \mid E/E$ $E \rightarrow d$ Check whether the grammar is ambiguous or not for the following string. $id + id + id$ [20 marks]
Q4. Explain GOTO and CLOSURE function in LR grammars. Consider the following grammar: $E \rightarrow E+T \mid T$ $T \rightarrow T*F \mid F$ $F \rightarrow (E) \mid id$ Find the collection of LR (0) items for the above grammar. [20 marks]

Attempt at least two questions from this Section.

Q5. (a) (i) Explain the concept of syntax - directed definition (SDD) with examples. (ii) Define inherited and synthesize attributes with respect to SDD. (b) Write the grammar and syntax - directed definitions for a simple desk calculator and show annotated parse tree for the expression $3 * 5 + 4n$ where 'n' is endmarker for the expression. [20 marks]
Q6. (a) What is Directed Acyclic Graph (DAG)? Draw DAG and three - address - code for the expression, $a+a*(b-c) +(b-c)*d$. Show the steps for constructing the same. (b) (i) List and explain various intermediate code form with an example. (ii) What do you mean by Postfix Notation? Evaluate the postfix expression $ab+c*$ using a stack. Assume that $a = 1, b = 2,$ and $c = 3$. [20 marks]
Q7. (a) What information is represented by symbol table? Explain the data structures used for symbol table. (b) Explain storage allocation scheme for a block structured language. [20 marks]
Q8. (a) How register allocation and evaluation order plays an important role in a code generator? Discuss. (b) Explain the following with an example: (i) Peephole optimization (ii) Global data flow analysis. [20 marks]