# GATE Questions & Answers of Compiler Design Computer Science and Information Technology

#### Compiler Design 47 Question(s) | Weightage 05 (Marks)

Which one of the following kinds of derivation is used by LR parsers?

Consider the grammar given below:

S → Aa

A → BD

B → b | $\in$

D → d | $\in$

Let a, b, d, and $be indexed as follows:  a b d$ 3 2 1 0

Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210) Answer: ________. ##### Show Answer Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let X1, X2, X3, X4, X5, and X6 be the placeholders for the nonterminals D, T, L or L1 in the following table:  Production rule Semantic action D → T L X1.type = X2.type T → int T.type = int T → float T.type = float L → LI , id X3.type = X4.type addType(id.entry, X5.type) L → id addType(id.entry, X6.type) Which one of the following are the appropriate choices for X1, X2, X3 and X4? ##### Show Answer Consider the augmented grammar given below: S' → S S →$\left\langle\mathrm L\right\rangle$| id L → L,S | S Let I0 = CLOSURE ({[S' → •S]}). The number of items in the set GOTO (I0 ,$\langle$) is: ________. ##### Show Answer A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}. Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processed by the analyzer, which one of the following is the sequence of tokens it outputs? ##### Show Answer Consider the following parse tree for the expression$\style{font-family:'Times New Roman'}{a\#b\$c\$d\#e\#f}$, involving two binary operators$ and #.

Which one of the following is correct for the given parse tree?

Consider the following intermediate program in three address code

p  =  a  -  b
q  =  p  *  c
p  =  u  *  v
q  =  p  +  q

Which one of the following corresponds to a static single assignment form of the above code?

Consider the following grammar:
stmt $\style{font-family:'Times New Roman'}\rightarrow$ if expr then expr else expr; stmt | 0
expr $\style{font-family:'Times New Roman'}\rightarrow$ term relop term | term
term $\style{font-family:'Times New Roman'}\rightarrow$ id |number
id $\style{font-family:'Times New Roman'}\rightarrow$ a | b | c
number $\style{font-family:'Times New Roman'}\rightarrow$ [0-9]

where relop is a rational operator (e.g.,<,>,...), O refers to the empty statement, and if, then, else are terminals.

Consider a preogram P following the above grammar containing ten if terminals. The number of control flow paths in P is ________. For example, the program

if e1 then e2 else e3

has 2 control flow paths, $\style{font-family:'Courier New'}{\begin{array}{l}{\mathrm e}_1\;\rightarrow\;{\mathrm e}_2\;\mathrm{and}\;{\mathrm e}_1\;\rightarrow\;{\mathrm e}_3\\\;\end{array}}$.

Consider the expression (a-1)*(((b+c)/3)+d)).  Let X be the minimum number of registers required by an optimal code generation (without any register spill) a algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instruction can have only register or immediate operands. Thevalue of X is _________ .

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it

 (P) Syntax tree (i)Code generator (Q)Character stream (ii)Syntax analyzer (R) Intermediate representation (iii) Semantic analyzer (S)Token stream (iv)Lexical analyzer

Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR

II. SLR is more powerfull than LALR.

III. SLR is more powerful than Canonical LR.

Consider the following expression grammar G:

E -> E - T | T
T -> T + F | F
F -> (E) | id
Which of the following grammars is not left recursive, but is equivalant to G?

Consider the following code segment.

x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;

The minimum number of total variables required to convert the above code segment to static single assignment form is_________ .

Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a,b}.

$\style{font-family:Tahoma}{\begin{array}{l}\mathrm S\rightarrow\mathbf a\mathrm A\;\;\left\{\mathrm{print}\;1\right\}\\\mathrm S\rightarrow\mathbf a\boldsymbol\;\boldsymbol\;\boldsymbol\;\;\left\{\mathrm{print}\;2\right\}\\\mathrm S\rightarrow\mathrm S\mathbf b\;\;\left\{\mathrm{print}\;3\right\}\end{array}}$

Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:

Match the following:

 (P) Lexical analysis (i) Leftmost derivation (Q) Top down parsing (ii) Type checking (R) Semantic analysis (iii) Regular expressions (S) Runtime environments (iv) Activation records

Which one of the following is TRUE at any valid state in shift – reduce parsing?

The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q+r/3+s-t\ast5+u\ast v/w$ is ______.

Match the following:

 P. Lexical analysis Q. Parsing R. Register allocation S. Expression evaluation 1.   Graph coloring    2.   DFA minimization    3.   Post-order traversal    4.   Production tree

Consider the intermediate code given below.
(1) i = 1
(2)
j = 1
(3)
t1 = 5 * i
(4)
t2 = t1+ j
(5)
t3 = 4 * t2
(6)
t4 = t3
(7)
a[t4] = – 1
(8)
j = j + 1
(9)
if j < = 5 goto (3)
(10)
i = i + 1
(11) if i < 5 goto (2)

The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are

Among simple LR (SLR), canonical LR, and look – ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?

Consider the following grammar G
SF | H
Fp | c
Hd | c

Where S, F, and H are non – terminal symbols, p, d, and c are terminal symbols. Which of the following statements (s) is/are correct?

S1. LL(1) can parse all strings that are generated using grammar G

S2. LR(1) can parse all strings that are generated using grammar G

Which one of the following is FALSE?

A canonical set of items is given below

S → L. > R
Q → R.

On input symbol < the set has

Consider the grammar defined by the following production rules, with two operators * and +

S → T ∗ P
T → U | T ∗ U
P → Q + P | Q
Q → Id
U → Id

Which one of the following is TRUE?

For a C program accessing X[i][j][k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.

t0 = i * 1024
t1 = j * 32
t2 = k * 4
t3 = t1 + t0
t4 = t3 + t2
t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

One of the purposes of using intermediate code in compilers is to

Consider the basic block given below.
a = b + c
c = a + d
d = b + c
e = d - b
a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type $\mathrm{A}\to \mathrm{ϵ}$ and $\mathrm{A}\to \mathrm{a}$) to parse a string with n tokens?

Consider the following two sets of LR(1) items of an LR(1) grammar.

 X → c.X, c/d X → .cX, c/d X → .d, c/d X → c.X, $X →.cX,$ X →.d, $Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since look aheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets. ##### Show Answer Consider the program given below, in a block-structured pseudo-language with lexical scoping and nesting of procedures permitted. Program main; Var ... Procedure A1; Var ... Call A2; End A1 Procedure A2; Var ... Procedure A21; Var ... Call A1; End A21 Call A21; End A2 Call A1; End main. Consider the calling chain: Main $\to$ A1 $\to$ A2 $\to$ A21 $\to$ A1 The correct set of activation records along with their access links is given by ##### Show Answer For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string,$\$$indicates end of input, and, | separates alternate right hand sides of productions. S $\to$ a A b B | b A a B | $\epsilon$ A $\to$ S B $\to$ S  a b  S E1 E2 S→ε A A→S A→S error B B→S B→S E3 The FIRST and FOLLOW sets for the non-terminals A and B are ##### Show Answer For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, \$$ indicates end of input, and, | separates alternate right hand sides of productions.

S $\to$ a A b B | b A a B | $\epsilon$
A $\to$ S
B $\to$ S

 a b \$ S E1 E2 S→ε A A→S A→S error B B→S B→S E3

The appropriate entries for E1, E2, and E3 are

In a compiler, keywords of a language are recognized during

Consider two binary operators ‘↑’ and '↓ ’ with the precedence of operator ↓ being lower than that of the operator ↑ ; . Operator ↑ is right associative while operator↓ is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2)?

Which data structure in a compiler is used for managing information about variables and their attributes?

Which languages necessarily need heap allocation in the runtime environment?

The grammar SaSa|bS|c is

Which of the following statements are TRUE?

I.  There exist parsing algorithms for some programming languages whose complexities are less than $\mathrm{\theta }$(n3).
II.  A programming language which allows recursion can be implemented with static storage allocation.
III.  No L-attributed definition can be evaluated in the framework of bottom-up parsing.
IV. Code improving transformations can be performed at both source language and intermediate code level.

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

Some code optimizations are carried out on the intermediate code because

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

Which one of the following is a top-down parser?

Consider the grammar with non-terminals N = {S,C,S1}, terminals T = {a, b, i, t, e}, with S as the start symbol, and the following set of rules:

S $\to$ iCtSS1 | a
S1 $\to$ eS | ε
C $\to$ b

The grammar is NOT LL(1) because:

Consider the following two statements:

P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

In a simplified computer the instructions are:

OP Rj, Ri   - Performs Rj OP Ri OP Ri and stores the result in register Ri.
OP m, Ri    - Performs val OP Ri and stores the result in Ri. val denotes the content of memory location m.
MOV, m Ri   - Moves the content of memory location m to register Ri.
MOV Ri, m   - Moves the content of register Ri to memory location m.

The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:

t1 = a + b
t2 = c + d
t3 = e - t2
t4 = t1 - t3

Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

Consider the CFG with {S, A, B} as the non-term , {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules:

 S$\to$aB S$\to$bA B$\to$b A$\to$a B$\to$bS A$\to$aS B$\to$aBB A$\to$bAA

Which of the following strings is generated by the grammar?

 S$\to$aB S$\to$bA B$\to$b A$\to$a B$\to$bS A$\to$aS B$\to$aBB A$\to$bAA