## Compiler-Design

 Question 1
Consider the grammar given below:
S → Aa
A → BD
B → b | ε
D → d | ε
Let a, b, d and \$ be indexed as follows: 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)
 A 30 B 31 C 10 D 21
Compiler-Design       Parsers       GATE 2019       Video-Explanation
Question 1 Explanation:
Follow(B) = First(D) Union Follow(A)
{Follow(B) = Follow(A) when D is epsilon}
Follow(B) = {d} Union {a} = {a,d}
 Question 2

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

 A Leftmost in reverse B Rightmost in reverse C Leftmost D Rightmost
Compiler-Design       Parsers       GATE 2019       Video-Explanation
Question 2 Explanation:
LR parsers have Rightmost derivation in reverse.
 Question 3

Consider the augmented grammar given below:

```    S' → S
S → 〈L〉 | id
L → L,S | S
```

Let I0 = CLOSURE ({[S’ → ·S]}). The number of items in the set GOTO (I0 , 〈 ) is: _____.

 A 4 B 5 C 6 D 7
Compiler-Design       Parsers       GATE 2019       Video-Explanation
Question 3 Explanation:
I0 = CLOSURE ({[S’ → ·S]}) Hence, the set GOTO (I0 , 〈 ) has 5 items.
 Question 4

Consider the following grammar and the semantic actions to support the inheritance type declaration attributes. Let X1, X2, X3, X4, X5 and X6 be the placeholders for the non-terminals D, T, L or L1 in the following table: Which one of the following are the appropriate choices for X1, X2, X3 and X4?

 A X1 = L, X2 = L, X3 = L1, X4 = T B X1 = L, X2 = T, X3 = L1, X4 = L C X1 = T, X2 = L, X3 = L1, X4 = T D X1 = T, X2 = L, X3 = T, X4 = L1
Compiler-Design       Synthesized-and-L-Attribute       GATE 2019       Video-Explanation
Question 4 Explanation:
Since the production,
L → L1, id {X3.type = X4.type } , this production has L and L1, hence X3 and X4 cannot be T.
So option 1, 3 and 4 cannot be correct.
 Question 5

Which one of the following statements is FALSE?

 A Context-free grammar can be used to specify both lexical and syntax rules. B Type checking is done before parsing. C High-level language programs can be translated to different Intermediate Representations. D Arguments to a function can be passed using the program stack.
Compiler-Design       Compilers       GATE 2018       Video-Explanation
Question 5 Explanation:
Type checking is done in semantic analysis phase after syntax analysis phase (i.e., after parsing).
 Question 6

Consider the following parse tree for the expression a#b\$c\$d#e#f, involving two binary operators \$ and #. Which one of the following is correct for the given parse tree?

 A \$ has higher precedence and is left associative; # is right associative B # has higher precedence and is left associative; \$ is right associative C \$ has higher precedence and is left associative; # is left associative D # has higher precedence and is right associative; \$ is left associative
Compiler-Design       Associativity-and-Precedence       GATE 2018       Video-Explanation
Question 6 Explanation:
Since \$ will be evaluated before # so \$ has higher precedence and the left \$ i.e., in b\$c\$d the left “\$” (i.e., b\$c) will be evaluated first so it is left associative, whereas # is right associative (as in d#e#f) , the right one (i.e., e#f) will be evaluated first.
 Question 7
A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}.
1: a?(b∣c)*aT
2: b?(a∣c)*bT
3: c?(b∣a)*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 processes by the analyzer, which one of the following is the sequence of tokens it outputs?
 A T1T2T3 B T1T1T3 C T2T1T3 D T3T3
Compiler-Design       Compilers       GATE 2018       Video-Explanation
Question 7 Explanation:
a? means either 0 or 1 occurrence of “a”, so we can write T1, T2 and T3 as:
T1 : (b+c)*a + a(b+c)*a
T2 : (a+c)*b + b(a+c)*b
T3 : (b+a)*c + c(b+a)*c
Now the string is: bbaacabc
Token that matches the longest possible prefix
We can observe that the longest possible prefix in string is : bbaac which can be generated by T3.
After prefix we left with “abc” which is again generated by T3 (as longest possible prefix).
 Question 8

Consider the following intermediate program in three address code

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

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

 A B C D Compiler-Design       Static-single-assignment       GATE 2017 [Set-1]       Video-Explanation
Question 8 Explanation:
Static Single Assignment is used for intermediate code in compiler design.
In Static Single Assignment form (SSA) each assignment to a variable should be specified with distinct names.
We use subscripts to distinguish each definition of variables.
In the given code segment, there are two assignments of the variable p
p = a-b
p = u*v
and two assignments of the variable q
q = p*c
q = p+q
So we use two variables p1, p2 for specifying distinct assignments of p and q1, q2 for each assignment of q.
Static Single Assignment form(SSA) of the given code segment is:
p1 = a-b
q1 = p1 * c
p2 = u * v
q2 = p2 + q1
Note:
As per options, given in GATE 2017 answer is B.
p3 = a – b
q4 = p3 * c
p4 = u * v
q5 = p4 + q4
 Question 9

Consider the following grammar: What is FOLLOW(Q)?

 A {R} B {w} C {w, y} D {w, \$}
Compiler-Design       First-and-Follow       GATE 2017 [Set-1]       Video-Explanation
Question 9 Explanation:
In the production: P → xQRS,
FIRST (R) = {w, ϵ} >br> Since FIRST (R) = {ϵ}, so FOLLOW (Q) → {w} ∪ FIRST(S)
FIRST(S) = {y}
So, FOLLOW (Q) = {w, y}
 Question 10
Consider the following grammar:
stmt    →  if expr then expr else expr; stmt | ȯ
expr    →  term relop term | term
term    →  id | number
id      →  a | bc
number  → [0-9]
where relop is a relational operator (e.g., <, >, …), ȯ refers to the empty statement, and if, then, else are terminals.
Consider a program 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, e1 e2 and e1 e3.

 A 1024 B 1025 C 1026 D 1027
Compiler-Design       Parsers       GATE 2017 [Set-1]       Video-Explanation
Question 10 Explanation:
To get 10 ‘if’ we need to use grammar to get,
if then else ; stmt
if then else ; if then else . stmt
:
:
:
(keep doing 10 times to get 10 ‘if’)
We know that every if statement has 2 control flows as given in question. Hence,
We have 2 control flow choices for 1st ‘if’
We have 2 control flow choices for 2nd ‘if’
:
:
:
We have 2 control flow choices for 10th ‘if’
Since all the choices are in one single structure or combination, so total choices are
2 × 2 × 2 × …….. 10 times = 210 = 1024
 Question 11

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) algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is ___________.

 A 2 B 3 C 4 D 5
Compiler-Design       Register-Allocation       GATE 2017 [Set-1]       Video-Explanation
Question 11 Explanation:
(a-1)*(((b+c)/3)+d) Question 12

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: A P→(ii), Q→(iii), R→(iv), S→(i) B P→(ii), Q→(i), R→(iii), S→(iv) C P→(iii), Q→(iv), R→(i), S→(ii) D P→(i), Q→(iv), R→(ii), S→(iii)
Compiler-Design       Compilers       GATE 2017 [Set-2]       Video-Explanation
Question 12 Explanation:
Character stream is input to lexical analyzer which produces tokens as output. So Q → (iv).
Token stream is forwarded as input to Syntax analyzer which produces syntax tree as output. So, S → (ii).
Syntax tree is the input for the semantic analyzer, So P → (iii).
Intermediate representation is input for Code generator. So R → (i).
 Question 13

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

I. Canonical LR is more powerful than SLR.

II. SLR is more powerful than LALR.

III. SLR is more powerful than Canonical LR.

 A I only B II only C III only D II and III only
Compiler-Design       Parsers       GATE 2017 [Set-2]       Video-Explanation
Question 13 Explanation:
Canonical LR is more powerful than SLR as every grammar which can be parsed by SLR parser, can also be parsed by CLR parser.
The power in increasing order is:
LR(0) < SLR < LALR < CLR
Hence only I is true.
 Question 14
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 equivalent to G?
 A B C D Compiler-Design       Left-Recursive-Grammar       GATE 2017 [Set-2]       Video-Explanation
Question 14 Explanation:
Consider the production (given below) which has left recursion.
S→Sα | β
The equivalent production (after removing left recursion) is
S→βS1
S1→αS1 | ϵ
Hence after removing left recursion from: E→ E-T | T, here α = -T and β = T
E→TE1
E1→ -TE1 | ϵ
After removing left recursion from: T→T+F | F, here α=+F and β=F
T→FT1
T1→ +FT1 | ϵ
Replace E1 = X and T1 = Y
We have,
E→TX
X→-TX | ϵ
T→FY
Y→+FY | ϵ
F→(E)| id
 Question 15
Consider the following code segment.
x = u – t;
y = x * v;
x = y + w;
y = t – z;
y = x * y;
The minimum number of  variables required to convert the above code segment to static single assignment form is ________.
 A 10 B 11 C 12 D 13
Compiler-Design       Static-single-assignment       GATE 2016 [Set-1]       Video-Explanation
Question 15 Explanation:
In Static Single Assignment form (SSA) each assignment to a variable should be specified with distinct names.
Generally, subscripts are used to distinguish each definition of variables.
In the given code segment, there are two assignments of the variable x
x = u – t;
x = y + w;
and three assignments of the variable y.
y = x * v;
y = t – z;
y = x * y
Hence, two variables viz x1, x2 should be used for specifying distinct assignments of x
and for y it is named as y1, y2 and y3 for each assignment of y.
Hence, total number of variables is 10 (x1, x2, y1, y2, y3, t, u, v, w, z), and there are 5 temporary variables.
Static Single Assignment form (SSA) of the given code segment is:
x1 = u – t;
y1 = x1 * v;
x2 = y1 + w;
y2 = t – z;
y3 = x2 * y2;
 Question 16

The attributes of three arithmetic operators in some programming language are given below.

```Operator      Precedence     Associativity     Arity
+             High            Left          Binary
−            Medium           Right         Binary
∗             Low             Left          Binary
```

The value of the expression 2 – 5 + 1 – 7 * 3 in this language is __________.

 A 9 B 10 C 11 D 12
Compiler-Design       Associativity-and-Precedence       GATE 2016 [Set-1]       Video-Explanation
Question 16 Explanation:
+ has highest precedence, so it will be evaluated first.
2 − 5 + 1 − 7 * 3 = 2 − (5 + 1) − 7 * 3 = 2 − 6 − 7 * 3
Now, − has more precedence than *, so sub will be evaluated before * and – has right associative so (6 − 7) will be evaluated first.
2 − 6 − 7 * 3 = (2 − (6 − 7)) * 3 = (2 – (−1)) * 3 = 3 * 3 = 9
 Question 17

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

```  S → aA   { print 1 }
S → a    { print 2 }
A → Sb   { print 3 }
```

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

 A 1 3 2 B 2 2 3 C 2 3 1 D syntax error
Compiler-Design       Syntax-Directed-Translation       GATE 2016 [Set-1]       Video-Explanation
Question 17 Explanation:
By using bottom up parser, the output will be “2 3 1” Question 18

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
```
 A P ↔ i, Q ↔ ii, R ↔ iv, S ↔ iii B P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv C P ↔ ii, Q ↔ iii, R ↔ i, S ↔ iv D P ↔ iv, Q ↔ i, R ↔ ii, S ↔ iii
Compiler-Design       Compilers       GATE 2016 [Set-2]       Video-Explanation
Question 18 Explanation:
Regular expressions are used in lexical analysis.
Top down parsing has left most derivation of any string.
Type checking is done in semantic analysis.
Activation records are loaded into memory at runtime.
 Question 19

Which one of the following grammars is free from left recursion?

 A B C D Compiler-Design       Left-Recursive-Grammar       GATE 2016 [Set-2]       Video-Explanation
Question 19 Explanation:
The grammar in option A has direct left recursion because of production (A→Aa).
The grammar in option C has indirect left recursion because of production, (S→Aa and A→Sc).
The grammar in option D also has indirect left recursion because of production, (A→Bd and B→Ae).
 Question 20

Which one of the following is True at any valid state in shift-reduce parsing?

 A Viable prefixes appear only at the bottom of the stack and not inside B Viable prefixes appear only at the top of the stack and not inside C The stack contains only a set of viable prefixes D The stack never contains viable prefixes
Compiler-Design       Parsers       GATE 2015 [Set-1]
Question 20 Explanation:
A handle is actually on the top of the stack.
A viable prefixes is prefix of the handle and so can never extend to the right of handle, i.e., top of stack.
So set of viable prefixes is in stack.
 Question 21

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 * 5 + u * v/w is _________.

 A 8 B 9 C 10 D 11
Compiler-Design       Static-single-assignment       GATE 2015 [Set-1]
Question 21 Explanation:
We will need one temporary variable for storing the result of every binary operation as Static Single Assignment implies the variable cannot be repeated on left hand side of assignment.
The given expression:
q+r/3+s−t∗5+u∗v/w
t1=r/3;
t2=t∗5;
t3=u∗v;
t4=t3/w;
t5=q+t1;
t6=t5+s;
t7=t6−t2;
t8=t7+t4;
So in total we need 8 temporary variables. If it was not mentioned as static single assignment then answer would have been 3 because we can re-use the same temporary variable several times.
 Question 22

Let an represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?

 A an-2 + an-1 + 2n-2 B an-2 + 2an-1 + 2n-2 C 2an-2 + an-1 + 2n-2 D 2an-2 + 2an-1 + 2n-2
Compiler-Design       Live-Variable       GATE 2015 [Set-1]
Question 22 Explanation:
For string of length 1, there is ‘0’ consecutive 1’s.
So, a1 = 0
For string of length 2,
a2 = 1
Similarly, a3 = 3
a4 = 8
Only (A) will satisfy the above values.
 Question 23

A variable x is said to be live at a statement Si in a program if the following three conditions hold simultaneously:

i. There exists a statement Sj that uses x
ii. There is a path from Si to Sj in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at Si and Sj The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are

 A p, s, u B r, s, u C r, u D q, v
Compiler-Design       Live-Variable       GATE 2015 [Set-1]
Question 23 Explanation:
In compilers, live variable analysis is a classic data flow analysis to calculate the variables that are live at each point in the program.
A variable is live at some point if it holds a value that may be needed in the future, of equivalently if its value may be read before the next time the variable is written to.
→ ‘1’ can be assigned by the p and s and there is no intermediate use of them before that.
→ And p and s are not to be live in the both 2 & 3.
→ And q also assigned to u not live in 2 & 3.
→ And v is live at 3 not at 2.
→ u is live at 3 and also at 2, if we consider a path of length 0 from 2-8.
Finally r, u is the correct one.
 Question 24

In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?

 A In both AST and CFG, let node, N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding in N1. B For any input program, neither AST nor CFG will contain a cycle C The maximum number of successors of a node in an AST and a CFG depends on the input program D Each node is AST and CFG corresponds to at most one statement in the input program
Compiler-Design       Syntax-tree-and-context-flow-graph       GATE 2015 [Set-2]
Question 24 Explanation:
Optional (A) is not true when CFG contains cycle
Option (B) is false as CFG can contain cycle
Option (D) is false as a single node can contain block of statements.
 Question 25

Match the following:

```(P) Lexical analysis       (1) Graph coloring
(Q) Parsing                (2) DFA minimization
(R) Register allocation    (3) Post-order traversal
(S) Expression evaluation  (4) Production tree
```
 A P-2, Q-3, R-1, S-4 B P-2, Q-1, R-4, S-3 C P-2, Q-4, R-1, S-3 D P-2, Q-3, R-4, S-1
Compiler-Design       Compilers       GATE 2015 [Set-2]
Question 25 Explanation:
P) Lexical analysis is related with FA and Regular expressions.
Q) Expression can be evaluated with postfix traversals.
R) Register allocation can be done by graph colouring.
S) The parser constructs a production tree.
Hence, answer is ( C ).
 Question 26

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

 A 5 and 7 B 6 and 7 C 5 and 5 D 7 and 8
Compiler-Design       Control-Flow-Graph       GATE 2015 [Set-2]
Question 26 Explanation: Question 27

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?

 A SLR, LALR B Canonical LR, LALR C SLR, canonical LR D LALR, canonical LR
Compiler-Design       Parsers       GATE 2015 [Set-3]
Question 27 Explanation:
SLR is very easy to implement and CLR is most powerful method.
 Question 28

Consider the following grammar G.

```  S → F ⎪ H
F → p ⎪ c
H → d ⎪ c```

Where S, F and H are non-terminal symbols, p, d and c are terminal symbols. Which of the following statement(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
 A Only S1 B Only S2 C Both S1 and S2 D Neither S1 nor S2
Compiler-Design       Parsers       GATE 2015 [Set-3]
Question 28 Explanation:
For LL(1),
For first production, So, there is ‘c’ common in both the first(s) in the production of S. So not LL(1).
For LR(1), Since R-R conflict is present. So, not LR(1).
Hence, Option (D) is the correct answer.
 Question 29

Which one of the following is FALSE?

 A A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. B Available expression analysis can be used for common subexpression elimination. C Live variable analysis can be used for dead code elimination. D x=4*5 ⇒ x=20 is an example of common subexpression elimination.
Compiler-Design       Code-Optimization       GATE 2014 [Set-1]
Question 29 Explanation:
x=4* 5 ⇒ x=20 is an example of common subexpression elimination is a false statement.
Common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.
For ex: Consider the following code:
m=y+z * p
n= y+z *k
The common subexpression is “y+z” we can be calculate it one time and replace in both expression
temp = y+z
m = temp*p
n = temp*k
 Question 30

A canonical set of items is given below

```S --> L. > R
Q --> R.```

On input symbol < the set has

 A a shift-reduce conflict and a reduce-reduce conflict. B a shift-reduce conflict but not a reduce-reduce conflict. C a reduce-reduce conflict but not a shift-reduce conflict. D neither a shift-reduce nor a reduce-reduce conflict.
Compiler-Design       Parsers       GATE 2014 [Set-1]
Question 30 Explanation:
The input symbol is “<” which is not in canonical set of item, so it is neither a shift-reduce nor a reduce-reduce conflict with reference to “<” symbol.
But if it would have asked about “>” then it will be a SR conflict.
 Question 31

Let L be a language and L’ be its complement. Which one of the following is NOT a viable possibility?

 A Neither L nor is recursively enumerable (r.e.). B One of L and is r.e. but not recursive; the other is not r.e. C Both L and are r.e. but not recursive. D Both L and are recursive.
Compiler-Design       Closure-Property       GATE 2014 [Set-1]
Question 31 Explanation:
If both L and L’ are recursively enumerable, then L must be recursive. Hence, both L and L´ are recursively enumerable, but not recursive is not a viable possibility.
 Question 32

Which of the regular expressions given below represent the following DFA? I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1
 A I and II only B I and III only C II and III only D I, II, and III
Compiler-Design       Regular-Expressions       GATE 2014 [Set-1]
Question 32 Explanation:
The DFA accepts the language “all strings ending with 1”.
So the regular expression corresponding to DFA is (0+1)*1.
Now, by using state elimination method,
So the DFA also has another equivalent regular expression: 0*1(1+00*1)*.
But the regular expression (0*1*1+11*0*1) is not equivalent to DFA, as the DFA also accept the string “11011” which cannot be generated by this regular expression.
 Question 33

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?

 A + is left associative, while ∗ is right associative B + is right associative, while ∗ is left associative C Both + and ∗ are right associative D Both + and ∗ are left associative
Compiler-Design       Associativity-and-Precedence       GATE 2014 [Set-2]
Question 33 Explanation:
In production: T ⟶ T * U, since T is left recursive, hence * is left associative.
P ⟶ Q + P, here P is right recursive, so + is right associative.
 Question 34

Which one of the following is NOT performed during compilation?

 A Dynamic memory allocation B Type checking C Symbol table management D Inline expansion
Compiler-Design       Run-Time-Environments       GATE 2014 [Set-2]
Question 34 Explanation:
Dynamic memory allocation is not performed during compilation, it occurs at run time only. At the time of compilation, compiler only compiles the instructions for dynamic memory allocation, like calloc, malloc….
 Question 35

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?

 A X is declared as “int X”. B X is declared as “int X”. C X is declared as “char X”. D X is declared as “char X”.
Compiler-Design       Intermediate-Code       GATE 2014 [Set-2]
Question 35 Explanation:
Consider a 3-D array: arr[i][j][k]
Arr, this 3-D array contains
1 two dimensional array as i value is zero (if i =1 then it has 2, two D array), & the two dimension array has 2 row and 3 column.
So, In a 3-D array, i represent number of 2D arrays, j represent number of rows and k represent number of columns.
Number of 2 D array (M)=1
Number of rows (R)=2
Number of columns (C)=3 As arrays are stored in row major order, so this 2 dimension array will be stored as: Assume base address of Arr is 1000. The address of required position is calculated as:
Arr[i][j][k]= Arr+ [i*(R*C)+(j*C)+k]*4 // multiplication to 4 is due to int takes 4 Bytes.
Arr = 1000+[0*(2*3)+(1*3)+1]*4
= 1000+[ 0+3+1 ]*4
= 1000+4*4
= 1016
As you can see that in the given example of row order storing of array also has address of Arr is 1016.
Now coming to the question:
X [ i ][ j ][ k ] is calculated by 3 address code X[t4]
X [ i ][ j ][ k ] = X [ t4 ] // by substituting in reverse
= X [ t3 + t2]
= X [ t1 + t0 + k*4]
= X [ t0 + t1 + k*4] // t0 and t1 swapped as swapping doesn’t have any impact
= X [ i*1024 + j*32 + k*4]
= X [ i*256 + j*8 +k] *4 // taking 4 (common) outside
= X [ i*(32*8)+ (j*8) +k] *4
By comparing the above line with ……. Arr[i][j][k] = Arr+ [i*(R*C)+(j*C)+k]*4
We get R=32, C=8
It means the the declared array has 32 rows and 8 columns and since multiplication by 4 (common outside) so it was declared as INT.
But how many number of 2D arrays in this 3D array, we don’t know.
Since option A is the only option with configuration: INT arr  . So it is right option.
 Question 36

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is _______. A 6 B 7 C 8 D 9
Compiler-Design       General       GATE 2014 [Set-2]
Question 36 Explanation:  Question 37

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

 A make parsing and semantic analysis simpler. B improve error recovery and error reporting. C increase the chances of reusing the machine-independent code optimizer in other compilers. D improve the register allocation.
Compiler-Design       Code-Generation-and-Code-Optimization       GATE 2014 [Set-3]
Question 37 Explanation:
Intermediate code is generated after semantic analysis. The intermediate code is independent of machine. By converting source code to intermediate code a machine independent code optimizer may be written. Thus increase the chances of reusing the machine-independent code optimizer in other compilers.
 Question 38

Which of the following statements are CORRECT?

1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursion.
4) Both heap and stack are essential to implement recursion.
 A 1 and 2 only B 2 and 3 only C 3 and 4 only D 1 and 3 only
Compiler-Design       General       GATE 2014 [Set-3]
Question 38 Explanation:
The statement, static allocation of all data areas by a compiler makes it impossible to implement recursion is true, as recursion requires memory allocation at run time, so it requires dynamic allocation of memory. Hence, Dynamic allocation of activation records is essential to implement recursion is also a true statement.
 Question 39

A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?

`4, 7, 6, 1, 7, 6, 1, 2, 7, 2`
 A 6 B 7 C 8 D 9
Compiler-Design       Page-Replacement-Algorithm       GATE 2014 [Set-3]
Question 39 Explanation:
6 page faults will occur using LRU.
 Question 40

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 A → є and A → a) to parse a string with n tokens?

 A n/2 B n-1 C 2n-1 D 2n
Compiler-Design       Parsers       GATE 2013
Question 40 Explanation:
Since it is given that the grammar cannot have:
1) epsilon production
2) production of the form A → a
Consider the grammar:
S → Sa | a
If we were to derive the string “aaa” whose length is 3 then the number of reduce moves that would have been required are shown below:
S → Sa
→ Saa
→ aaa
This shows us that it has three reduce moves. The string length is 3 and the number of reduce moves is also 3. So presence of such kinds of production might give us the answer “n” for maximum number of reduce moves. But these productions are not allowed as per the question.
Also note that if a grammar does not have unit production then the maximum number of reduce moves can not exceed “n” where “n” denotes the length of the string.
3) No unit productions
Consider the grammar:
S → A
A → B
B → C
C → a
If we were to derive the string “a” whose length is 1 then the number of reduce moves that would have been required are shown below:
S → A
A → B
B → C
C → a
This shows us that it has four reduce moves. The string length is 1 and the number of reduce moves is 4. So presence of such kind of productions might give us the answer “n+1” or even more, for maximum number of reduce moves. But these productions are not allowed as per the question.
Now keeping in view the above points suppose we want to parse the string “abcd”. (n = 4) using bottom-up parsing where strings are parsed finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving right most derivations only.
We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon- and unit-production (i.e., of type A → є and A → B) and no production of the form A → a) as follows:
S → aB
B → bC
C → cd
The Right Most Derivation for the above is:
S → aB (Reduction 3)
→ abC (Reduction 2)
→ abcd (Reduction 1)
We can see here the number of reductions present is 3.
We can get less number of reductions with some other grammar which also doesn’t produce unit or epsilon productions or production of the form A → a
S → abA
A → cd
The Right Most Derivation for the above is:
S → abA (Reduction 2)
→ abcd (Reduction 1)
Hence 2 reductions.
But we are interested in knowing the maximum number of reductions which comes from the 1st grammar. Hence total 3 reductions as maximum, which is (n – 1) as n = 4 here.
 Question 41

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.
 A 1 only B 2 only C 1 and 4 only D 1, 2, 3 and 4
Compiler-Design       Parsing-and-Syntax-Directed-Graph       GATE 2013
Question 41 Explanation:
The two sets in LR(1) items can be merged if they only differ with look aheads symbols, so statement 1 is false.
In the given LR(1) items there is not any reduce move, so after merging it will not have SR conflict and hence statement 2 and statement 3 are false.
Statement 4 is also wrong, because goto is carried on Non-Terminals symbols, not on terminal symbols, and c is a terminal symbol.
Hence all statements are false.
 Question 42

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 A21

Call A1;
End main.
```

Consider the calling chain : Main->A1->A2->A21->A1 The correct set of activation records along with their access links is given by:

 A B C D Compiler-Design       Run-Time-Environments       GATE 2012
Question 42 Explanation: Main → A1 → A2 → A21 → A1
Since, Activation records are created at procedure exit time.
A1 & A2 are defined under Main ( ). So A1 & A2 access links are pointed to main.
A21 is defined under A2, hence its access link will point to A2.
 Question 43

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 → aAbB | bAaB | ε
A → S
B → S``` The FIRST and FOLLOW sets for the non-terminals A and B are

 A FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b,\$} B FIRST(A) = {a,b,\$} FIRST(B) = {a,b,ε} FOLLOW(A) = {a,b} FOLLOW(B) = {\$} C FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = ∅ D FIRST(A) = {a,b} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b}
Compiler-Design       Parsers       GATE 2012
Question 43 Explanation:
FIRST (P): is the set of terminals that begin the strings derivable from non terminal P. If P derives epsilon then we include epsilon in FIRST(P).
FOLLOW(P): is the set of terminals that can appear immediately to the right of P in some sentential form.
FIRST(A) = FIRST (S)
FIRST (S) = FIRST (aAbB) and FIRST (bAaB) and FIRST (ϵ)
FIRST(S) = {a, b, ϵ}
FIRST (B) = FIRST (S) = {a, b, ϵ} = FIRST (A)
FOLLOW(A) = {b} // because of production S→a A b B
FOLLOW(A) = {a} // because of production S→ b A a B
So FOLLOW (A) = {a, b}
FOLLOW (B) = FOLLOW (S) // because of production S→ a A b B
FOLLOW (S) = FOLLOW (A) // because of production S → A
So FOLLOW (S) = {\$, a, b} = FOLLOW(B)
 Question 44

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 → aAbB | bAaB | ε
A → S
B → S``` The appropriate entries for E1, E2, and E3 are

 A E1: S → aAbB,A → S E2: S → bAaB,B→S E3: B → S B E1: S → aAbB,S→ ε E2: S → bAaB,S → ε E3: S → ε C E1: S → aAbB,S → ε E2: S → bAaB,S→ε E3: B → S D E1: A → S,S →ε E2: B → S,S → ε E3: B →S
Compiler-Design       Parsers       GATE 2012
Question 44 Explanation:
The entries in E1, E2 and E3 is related to S and B, so we have to take only those production which have S and B in LHS.
S→ aAbB | bAaB | ε
The production S→ aAbB will go under column FIRST (aAbB) = a, so S→ aAbB will be in E1.
S→ bAaB will go under column FIRST(bAaB) = b, so S→ bAaB will be in E2.
S→ ε will go under FOLLOW (S) = FOLLOW(B) = {a, b, \$ } , So S→ ε will go in E1, E2 and under column of \$.
So E1 will have: S→ aAbB and S→ ε.
E2 will have S→ bAaB and S→ ε.
Now, B→ S will go under FIRST (S) = {a, b, ε}
Since FIRST(S) = ε so B→ S will go under FOLLOW (B) = {a, b, \$}
So E3 will contain B→ S.
 Question 45

The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

 A Finite state automata B Deterministic pushdown automata C Non-Deterministic pushdown automata D Turing machine
Compiler-Design       Compilers       GATE 2011
Question 45 Explanation:
Lexical Analysis is implemented by finite automata.
 Question 46

In a compiler, keywords of a language are recognized during

 A parsing of the program B the code generation C the lexical analysis of the program D dataflow analysis
Compiler-Design       Compilers       GATE 2011
Question 46 Explanation:
Any identifier is also a token so it is recognized in lexical Analysis.
 Question 47

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)?

 A B C D Compiler-Design       Parsers       GATE 2011
Question 47 Explanation:
7 ↓ 3 ↑ 4 ↑ 3 ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
 Question 48

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e initially stored in memory. The binary operators used in this expression tree can be evaluate by the machine only when the operands are in registers. The instructions produce results only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression? A 2 B 9 C 5 D 3
Compiler-Design       Register-Allocation       GATE 2011
Question 48 Explanation:
Load R1, a ; R1 ← M[a]
Load R2, b ; R2 ← M[b]
Sub R1, R2 ; R1 ← R1 – R2
Load R2, c ; R2 ← M[c]
Load R3, d ; R3 ← M[d]
Add R2, R3 ; R2 ← R2 + R3
Load R3, e ; R3 ← M[e]
Sub R3, 3 ; R3 ← R3 – R2
Add R1, R3 ; R1 ← R1 + R3
Total 3 Registers are required minimum.
 Question 49

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

 A Abstract syntax tree B Symbol table C Semantic stack D Parse Table
Compiler-Design       Compilers       GATE 2010
Question 49 Explanation:
Symbol tables are data structures that are used by compilers to hold information about source-program constructs. The information is collected incrementally by the analysis phases of a compiler and used by the synthesis phases to generate the target code. Entries in the symbol table contain information about an identifier such as its character string (or lexeme) , its type, its position in storage, and any other relevant information.
 Question 50

Which languages necessarily need heap allocation in the runtime environment?

 A Those that support recursion B Those that use dynamic scoping C Those that allow dynamic data structures D Those that use global variables
Compiler-Design       Run-Time-Environments       GATE 2010
Question 50 Explanation:
Dynamic memory is allocated on the heap by the system. So the languages which allow dynamic data structure require heap allocation at runtime.
There are 50 questions to complete.

Register Now