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
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}
Hence Answer is : 31
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
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
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
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.
Hence, 2 is correct answer.
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
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
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}.

    T1: a?(b∣c)*a
    T2: b?(a∣c)*b
    T3: 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
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
Please NOTE:
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).
So, answer is T3T3.
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]
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]
Question 9 Explanation: 
In the production: P → xQRS,
FOLLOW (Q) = FIRST (R)
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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[32][32][8]”.
B
X is declared as “int X[4][1024][32]”.
C
X is declared as “char X[4][32][8]”.
D
X is declared as “char X[32][16][2]”.
       Compiler-Design       Intermediate-Code       GATE 2014 [Set-2]
Question 35 Explanation: 
Consider a 3-D array: arr[i][j][k]
Arr[0][1][2], 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[0][1][1] = 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[0][1][1] 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[32] [32] [8]. 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

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 40 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 41

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 41 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 42

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 42 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 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 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 43 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 44

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 44 Explanation: 
Lexical Analysis is implemented by finite automata.
Question 45

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 45 Explanation: 
Any identifier is also a token so it is recognized in lexical Analysis.
Question 46

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 46 Explanation: 
7 ↓ 3 ↑ 4 ↑ 3 ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
Question 47

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 47 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 48

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 48 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 49

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 49 Explanation: 
Dynamic memory is allocated on the heap by the system. So the languages which allow dynamic data structure require heap allocation at runtime.
Question 50

The program below uses six temporary variables a, b, c, d, e, f.

 
    a = 1
    b = 10
    c = 20
    d = a+b
    e = c+d
    f = c+e
    b = c+e
    e = b+f
    d = 5+e
    return d+f

Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

A
2
B
3
C
4
D
6
       Compiler-Design       Register-Allocation       GATE 2010
Question 50 Explanation: 
Here a, b, and c all have 3 different values so we need atleast 3 registers r1, r2 and r3.
Assume 'a' is mapped to r1, 'b' to r2 and 'c' to r3.
d = a + b, after this line if u notice 'a' is never present on right hand side, so we can map 'd' to r1.
e = c + d, after this line 'd' is never present on rhs, so we can map 'e' to r1.
at this time mapping is
r1 --- e
r2 --- b
r3 --- c
We have 3 registers for e, b and c.
f = c + e
b = c + e
These two are essentially doing same thing, after these two line 'b' and 'f' are same so we can skip computing 'f' or need not give any new register for 'f'. And wherever 'f' is present we can replace it with 'b', because neither of 'f' and 'b' are changing after these two lines, so value of these will be 'c+e' till the end of the program.
At second last line "d = 5 + e"
here 'd' is introduced, we can map it to any of the register r1 or r3, because after this line neither of 'e' or 'c' is required. Value of 'b' is required because we need to return 'd+f', and 'f' is essentially equal to 'b'
finally code becomes
r1 = 1
r2 = 10
r3 = 20
r1 = r1 + r2
r1 = r3 + r1
r2 = r3 + r1
r2 = r3 + r1
r1 = r2 + r2
r3 = 5 + r1
return r3 + r2
Therefore minimum 3 registers needed.
Question 51

The grammar S → aSa|bS|c is

A
LL(1) but not LR(1)
B
LR(1) but not LR(1)
C
Both LL(1) and LR(1)
D
Neither LL(1) nor LR(1)
       Compiler-Design       Parsers       GATE 2010
Question 51 Explanation: 
The LL(1) parsing table for the given grammar is:

As there is no conflict in LL(1) parsing table, hence the given grammar is LL(1) and since every LL(1) is LR(1) also, so the given grammar is LL(1) as well as LR(1).
Question 52

Match all items in Group 1 with correct options from those given in Group 2

       Group 1                     Group 2
P. Regular expression        1. Syntax analysis
Q. Pushdown automata         2. Code generation
R. Dataflow analysis         3. Lexical analysis
S. Register allocation       4. Code optimization
A
P-4, Q-1, R-2, S-3
B
P-3, Q-1, R-4, S-2
C
P-3, Q-4, R-1, S-2
D
P-2, Q-1, R-4, S-3
       Compiler-Design       Compilers       GATE 2009
Question 52 Explanation: 
Lexical analysis phase uses regular expression to identify the pattern of tokens, PDA is used in CFG and hence syntax analysis phase is related to PDA. Data flow analysis is done in code optimization phase and register allocation is related to code generation phase.
Question 53

Which of the following statements are TRUE?

    I.There exist parsing algorithms for some programming languages whose complexities are less than θ(n3).
    II.A programming language which allows recursion can be implemented with static storage.
    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.
A
I and II
B
I and IV
C
III and IV
D
I, III and IV
       Compiler-Design       Parsers       GATE 2009
Question 53 Explanation: 
Statement II is false, as a programming language which allows recursion requires dynamic storage allocation. Statement III is false, as L-attributed definition (assume for instance the L-attributed definition has synthesized attribute only) can be evaluated in bottom up framework.
Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Question 54

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

A
It is the position in a sentential form where the next shift or reduce operation will occur.
B
It is non-terminal whose production will be used for reduction in the next step.
C
It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur.
D
It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
       Compiler-Design       Parsers       GATE 2008
Question 54 Explanation: 
A handle is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
Question 55

Some code optimizations are carried out on the intermediate code because

A
They enhance the portability of the compiler to other target processors
B
Program analysis is more accurate on intermediate code than on machine code
C
The information from dataflow analysis cannot otherwise be used for optimization
D
The information from the front end cannot otherwise be used for optimization
       Compiler-Design       Compilers       GATE 2008
Question 55 Explanation: 
The code-optimization on intermediate code generation will always enhance the portability of the compiler to target processors. The main reason behind this is, as the intermediate code is independent of the target processor on which the code will be executed, so the compiler is able to optimize the intermediate code more conveniently without bothering the underlying architecture of target processor.
Question 56

Which of the following are true?

    I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation
    II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions
    III. Recursion in programming languages cannot be implemented with dynamic storage allocation
    IV. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records
    V.Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records
A
II and V only
B
I, III and IV only
C
I, II and V only
D
II, III and V only
       Compiler-Design       Run-Time-Environments       GATE 2008
Question 56 Explanation: 
II. Multilevel access link (or display) arrangement is needed to arrange Activation Records only if the programming language being implemented has nesting of procedures and functions.
V. PL’s which permits a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records.
II & V are True.
Question 57

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

A
the SLR(1) parser for G has S-R conflicts
B
the LR(1) parser for G has S-R conflicts
C
the LR(0) parser for G has S-R conflicts
D
the LALR(1) parser for G has reduce-reduce conflicts
       Compiler-Design       Parsres       GATE 2008
Question 57 Explanation: 
LALR(1) parser is obtained by minimizing the LR(1) parser and hence they both uses LR(1) items. Now consider if LR(1) parser has SR conflict, for ex:
Consider a state in LR(1) parser:
S-> x.yA, a
A-> x. , y
This has both shift and reduce conflict on symbol “y”.
Since LR(1) already has SR conflict , so resulting LALR(1) (after merging) will also have SR conflict.
Now if LR(1) doesn’t have SR conflict then it is guaranteed that the LALR(1) will never have SR conflict. The reason behind this is, as we merge those state only which has same set of canonical items except look ahead and the LR(1) canonical items has DFA (means from one state to other state the transition is from unique symbol) , so after merging also we will never see any shift conflict, only reduce-reduce may occur.
Hence An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if the LR(1) parser for G has S-R conflicts.
Question 58

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

A
Recursive descent parser.
B
Operator precedence parser.
C
An LR(k) parser.
D
An LALR(k) parser.
       Compiler-Design       Parsers       GATE 2007
Question 58 Explanation: 
Recursive descent parser is top down parser, while others are bottom up parser.
Question 59

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 --> iCtSS1|a
      S1 --> eS|ϵ
      C --> b

The grammar is NOT LL(1) because:

A
it is left recursive
B
it is right recursive
C
it is ambiguous
D
it is not context-free
       Compiler-Design       Parsers       GATE 2007
Question 59 Explanation: 
The given grammar is not left recursive and also it is context free (Type 2 grammar), so option A and D is wrong. Being a right recursive grammar is not an issue for LL(1) grammar. So even if given grammar is right recursive, this is not a reason for NOT LL(1).
This grammar has two parse tree for string “ibt ibt aea”.
Question 60

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?

A
Both P and Q are true
B
P is true and Q is false
C
P is false and Q is true
D
Both P and Q are false
       Compiler-Design       Parsers       GATE 2007
Question 60 Explanation: 
Every regular grammar is LL(1) is false, as the grammar may have left recursion or left factoring or also it is possible that grammar is ambiguous.
For ex: Consider a regular grammar
S -> aS | a | ϵ
this grammar is ambiguous as for string "a" two parse tree is possible.

Hence it is regular but not LL(1).
But every regular set has a language accept or as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
Question 61

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

S → aB        S → bA
B → b         A → a
B → bS        A → aS
B → aBB       A → bAA

Which of the following strings is generated by the grammar?

A
aaaabb
B
aabbbb
C
aabbab
D
abbbba
       Compiler-Design       Grammar       GATE 2007
Question 61 Explanation: 
The string “aabbab” can be derived by following steps:
S -> aB [Using S --> aB]
-> aaBB [Using B --> aBB]
-> aabB [Using B --> b]
-> aabbS [Using B --> bS]
-> aabbaB [Using S --> aB]
-> aabbab [Using B --> b]
Question 62

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

S → aB        S → bA
B → b         A → a
B → bS        A → aS
B → aBB       A → bAA

For the correct answer strings to Q.78, how many derivation trees are there?

A
1
B
2
C
3
D
4
       Compiler-Design       Grammar       GATE 2007
Question 62 Explanation: 
There exist two parse tree for the string “aabbab” using LMD (left most derivation)
Question 63

Consider the following grammar.

   S → S * E
   S → E
   E → F + E
   E → F
   F → id 

Consider the following LR(0) items corresponding to the grammar above.

(i) S → S * .E
(ii) E → F. + E
(iii) E → F + .E 

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
None of the above
       Compiler-Design       Parsers       GATE 2006
Question 63 Explanation: 
As we can see in the below given LR(0) items, that all three belongs to different state (sets).
Question 64

Consider these two functions and two statements S1 and S2 about them

int work1(int *a, int i, int j)          int work2(int *a, int i, int j)
{                                          {      
    int x = a[i+2];                            int t1 = i+2;
    a[j] = x+1;                                int t2 = a[t1]; 
    return a[i+2] – 3;                         a[j] = t2+1;
}                                              return t2 – 3; 
                                           } 
    S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1
    S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1
A
S1 is false and S2 is false
B
S1 is false and S2 is true
C
S1 is true and S2 is false
D
S1 is true and S2 is true
       Compiler-Design       Code-Optimization       GATE 2006
Question 64 Explanation: 
We cannot compare the program on the basis of runtime with respect to any inputs.
So, given statement is wrong.
S1: Let us assume an array = {1,2,3,4,5} and i=0.
Let j = i+2 = 0+2 = 2
For the respective example work1 and work2 results 1 and 0, so S1 statement is False.
Question 65

Consider the following grammar:

   S → FR
   R → S | ε
   F → id

In the predictive parser table, M, of the grammar the entries M[S,id] and M[R,$] respectively.

A
{S → FR} and {R → ε}
B
{S → FR} and { }
C
{S → FR} and {R → *S}
D
{F → id} and {R → ε}
       Compiler-Design       Parsers       GATE 2006
Question 65 Explanation: 
Predictive parsing table for the mentioned grammar:

The representation M[X,Y] means X represents Variable (rows) and Y represents terminals (columns).
The productions are filled in parsing table by the below mentioned rules:
For every production P → α, we have:
Rule 1: If P → α is a production then add this production for each terminal “t” which is in FIRST of [α] i.e., ADD P → α to M[P, a]
Rule 2: If “ϵ” belongs to FIRST of [P] then add P → α to M[P, b] where “b” represents terminals FOLLOW[P].
By the above rules, we can see that production S → FR will go M[S, a] where “a” is FIRST [FR] which is equal to FIRST[F] = id, So S → FR will go in M[S,id].
Since in the production R→ϵ , FIRST[ϵ] = ϵ, hence the production will go in M[R, b] where “b” represents terminals FOLLOW[R] and FOLLOW[R] = $, so production R→ϵ will go in M[R,$]
Question 66

Consider the following translation scheme.

   S → ER 
   R → *E{print("*");}R|ε 
   E → F + E {print("+");}|F 
   F → (S)|id {print(id.value);} 

Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints

A
2 * 3 + 4
B
2 * +3 4
C
2 3 * 4 +
D
2 3 4+*
       Compiler-Design       Syntax-Directed-Translation       GATE 2006
Question 66 Explanation: 

Now perform post order evaluation, you will get output as,
2 3 4 + *
Question 67

Consider the following C code segment.

for (i = 0, i < n; i++)  
{
    for (j = 0; j < n; j++)   
    {
        if (i%2)  
        {
            x += (4*j + 5*i);
            y += (7 + 4*j);
        }
    }
}

Which one of the following is false?

A
The code contains loop invariant computation
B
There is scope of common sub-expression elimination in this code
C
There is scope of strength reduction in this code
D
There is scope of dead code elimination in this code
       Compiler-Design       Code-Optimization       GATE 2006
Question 67 Explanation: 
→ 4*j is a common sub-expression. So there is a scope of elimination. So B is correct.
→ 5*i can be moved out of inner loop. So can be i%2, here loop invariant computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
Question 68

The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:

A
ambiguous
B
left-recursive
C
right-recursive
D
an operator-grammar
       Compiler-Design       Parsers       GATE 2005
Question 68 Explanation: 
The given grammar can be turned into a infinite parse tree. So it is ambiguous.
It have A → AA has left recursion.
Question 69

Consider the grammar:

  E → E + n | E × n | n 

For a sentence n + n × n, the handles in the right-sentential form of the reduction are:

A
n, E + n and E + n × n
B
n, E + n and E + E × n
C
n, n + n and n + n × n
D
n, E + n and E × n
       Compiler-Design       Grammar       GATE 2005
Question 69 Explanation: 
E → E + n {Applying E → E+n}
→ E + E * n {Applying E → E * n}
→ E + n * n {Applying E → n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
Question 70

Consider the grammar:

   S → (S) | a 

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good:

A
n1 < n2 < n3
B
n1 = n3 < n2
C
n1 = n2 = n3
D
n1 ≥ n3 ≥ n2
       Compiler-Design       Parsers       GATE 2005
Question 70 Explanation: 
→ SLR(1) and LALR(1) both are be the states of LR(0) items then SLR(1) = LALR(1).
→ LR(1) be the states of LR(1) items.
→ LR(0) items never be greater than LR(1) items then SLR(1) = LALR(1) < LR(1)
n1 = (n3) < (n2)
Question 71

Consider line number 3 of the following C-program.

int main ( ) {                   /* Line 1 */
  int I, N;                      /* Line 2 */
  fro (I = 0, I < N, I++);       /* Line 3 */
} 

Identify the compiler's response about this line while creating the object-module:

A
No compilation error
B
Only a lexical error
C
Only syntactic errors
D
Both lexical and syntactic errors
       Compiler-Design       Compilers       GATE 2005
Question 71 Explanation: 
There is no error in the above code. Actually it is a link error. Here compiler fro is a function which is not declared. Hence, it will not produce any error. It will only throw a warning in C.
Question 72

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number 	 E.val = number. val
    |E '+' E 	 E(1).val = E(2).val + E>sup>(3).val
    |E '×' E	 E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

A
It detects recursion and eliminates recursion
B
It detects reduce-reduce conflict, and resolves
C
It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
D
It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
       Compiler-Design       Parsres       GATE 2005
Question 72 Explanation: 
Yacc favours shift move in case of SR conflict.
Question 73

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number 	 E.val = number. val
    |E '+' E 	 E(1).val = E(2).val + E>sup>(3).val
    |E '×' E	 E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

A
Equal precedence and left associativity; expression is evaluated to 7
B
Equal precedence and right associativity; expression is evaluated to 9
C
Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7
D
Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9
       Compiler-Design       Parsers       GATE 2005
Question 73 Explanation: 
First of all, it is ambiguous grammar. Hence, equal precedence and associativity. Now as Yacc resolved it with shift move we will shift until the last operator and then we will start reducing.

Hence, the answer is 9 and right associative.
Question 74

Which of the following grammar rules violate the requirements of an operator grammar? P,Q,R are nonterminals, and r,s,t are terminals.

    (i) P → Q R
    (ii) P → Q s R
    (iii) P → ε
    (iv) P → Q t R r
A
(i) only
B
(i) and (iii) only
C
(ii) and (iii) only
D
(iii) and (iv) only
       Compiler-Design       Parsers       GATE 2004
Question 74 Explanation: 
Operator values doesn't contains nullable values and two adjacent non-terminals on RHS production.
i) On RHS it contains two adjacent non-terminals.
ii) Have nullable values.
Question 75

Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2, the reference will be resolved at

A
Edit time
B
Compile time
C
Link time
D
Load time
       Compiler-Design       Compilers       GATE 2004
Question 75 Explanation: 
The link time can gives the reference to the executable file when the functions are present in the other modules.
Question 76

Consider the grammar rule E → E1 - E2 for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E1 and E2 do not have any common sub expression, in order to get the shortest possible code

A
E1 should be evaluated first
B
E2 should be evaluated first
C
Evaluation of E1 and E2 should necessarily be interleaved
D
Order to evaluation of E1 and E2 is of no consequence
       Compiler-Design       Target-Code-Generation       GATE 2004
Question 76 Explanation: 
After evaluating E2 first and then E1, we will have E2 in the register and then we can simply do SUB operation with E2 which will be in memory. And if we do E1 first and then E2, then we must move E2 to memory and again bring back E1 to the register before doing SUB operation, which will increase load.
Question 77

Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T     {E.value = E1.value * T.value}
    |    T     {E.value = T.value}
T → T1 & F     {T.value = T1.value + F.value}
    |    F     {T.value = F.value}
F → num        {F.value = num.value}  

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

A
200
B
180
C
160
D
40
       Compiler-Design       Grammar       GATE 2004
Question 77 Explanation: 
Given expression is
2 # 3 & 5 # 6 & 4
→ Here # means multiplication (*)
& means addition (+)
→ & is having more precedence because it is far from starting symbol, here # and & are left associatives.
2 # 3 & 5 # 6 & 4
⇒ (2 * (3+5)) * (6+4)
⇒ (2 * 8) * (10)
⇒ 16 * 10 = 160
Question 78

Consider the following grammar G:

S → bS| aA| b
A → bA| aB
B → bB| aS |a 

Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is

A
{w|Na(w) > 3Nb(w)}
B
{w|Nb(w) > 3Na(w)}
C
{w|Na(w) = 3k, k ∈ {0, 1, 2, ...}}
D
{w|Nb(w) = 3k, k ∈ {0, 1, 2, ...}}
       Compiler-Design       Grammar       GATE 2004
Question 78 Explanation: 
S→bS
S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
Na(w) > 3Nb(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
Nb(w) > 3Nb(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
Nb(w) = 3k
2 = 3k(✖️)
S = aA
S→aA
S→abA
S→abaB
S→abaa
n(a)=3
|n(a)|=3
→ Answer: Option C(✔️)
Question 79

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

A
Removing left recursion alone
B
Factoring the grammar alone
C
Removing left recursion and factoring the grammar
D
None of the above
       Compiler-Design       Grammar       GATE 2003
Question 79 Explanation: 
Left recursion removing (or) factoring the given grammar are not sufficient to convert an arbitrary CFG to an LL(1) grammar.
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 80

Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:

A
n1 is necessarily less than n2
B
n1 is necessarily equal to n2
C
n1 is necessarily greater than n2
D
None of the above
       Compiler-Design       Parsers       GATE 2003
Question 80 Explanation: 
No. of states in SLR and LALR are equal and no. of states in SLR and LALR are less than or equal to LR(1).
Question 81

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

A
always be evaluated
B
be evaluated only if the definition is L-attributed
C
be evaluated only if the definition has synthesized attributes
D
never be evaluated
       Compiler-Design       Syntax-Directed-Translation       GATE 2003
Question 81 Explanation: 
L-Attributed grammar can able to inherits either inherited attributes (or) synthesized attributes.
L-Attributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parse-tree.
Question 82

Which of the following statements is FALSE?

A
In statically typed languages, each variable in a program has a fixed type
B
In un-typed languages, values do not have any types
C
In dynamically typed languages, variables have no types
D
In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program
       Compiler-Design       Run-Time-Environments       GATE 2003
Question 82 Explanation: 
Dynamic typed languages are those languages in which variable must necessarily be defined before they are used. Then dynamic typed languages have types.
Question 83

Consider the grammar shown below

S → i E t S S' | a
S' → e S | ε
E → b 

In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are

A
{S'→e S} and {S'→ε}
B
{S'→e S} and { }
C
{S'→ε} and {S'→ε}
D
{S'→e S, S'→ε} and {S'→ε}
       Compiler-Design       Parsers       GATE 2003
Question 83 Explanation: 
First(S) = {1,a}
First(S') = {e,ε}
First(E) = {b}
Follow(S') = {e,$}
Only when 'First' contains ε, we need to consider FOLLOW for getting the parse table entry.

Hence, option (D) is correct.
Question 84

Consider the grammar shown below.

S → C C
C → c C | d

The grammar is

A
LL(1)
B
SLR(1) but not LL(1)
C
LALR(1) but not SLR(1)
D
LR(1) but not LALR(1)
       Compiler-Design       Parsers       GATE 2003
Question 84 Explanation: 

Hence, it is LL(1).
Question 85

Consider the translation scheme shown below.

S → T R
R → + T {print ('+');} R|ε
T → num {print(num.val);}

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will print

A
9 + 5 + 2
B
9 5 + 2 +
C
9 5 2 + +
D
+ + 9 5 2
       Compiler-Design       Syntax-Directed-Translation       GATE 2003
Question 85 Explanation: 

Now traverse the tree and whatever comes first to print, just print it.
Answer will be 9 5 + 2 +.
Question 86

Consider the syntax directed definition shown below.

S → id := E           {gen (id.place = E.place;);}
E → E1 + E2           {t = newtemp ( ); 
                      gen(t = E1.place + E2.place;); 
                      E.place = t}
E → id                {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti's are the temporary variable names generated by newtemp. For the statement 'X: = Y + Z', the 3-address code sequence generated by this definition is

A
X = Y + Z
B
t1 = Y + Z; X = t1
C
t1= Y; t2 = t1 + Z; X = t2
D
t1 = Y; t2 = Z; t3 = t1 + t2; X = t3
       Compiler-Design       Syntax-Directed-Translation       GATE 2003
Question 86 Explanation: 
Question 87

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

A
Smaller sizes of executable files
B
Lesser overall page fault rate in the system
C
Faster program startup
D
Existing programs need not be re-linked to take advantage of newer versions of libraries
       Compiler-Design       Run-Time-Environments       GATE 2003
Question 87 Explanation: 
Dynamic link libraries takes more time in program setup (in loading and linking phase to set up the global offset table and load and link the required libraries).
Question 88

(a) Construct all the parse trees corresponding to i + j * k for the grammar

      E → E+E
      E → E*E
      E → id  
    (b) In this grammar, what is the precedence of the two operators * and +?
    (c) If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is non-ambiguous?
A
Theory Explanation is given below.
       Compiler-Design       Descriptive       GATE 2002
Question 89

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

A
Assembly
B
Parsing
C
Relocation
D
Symbol resolution
       Compiler-Design       Run-Time-Environments       GATE 2001
Question 89 Explanation: 
Relocation can change the assigned address of data and code in the program.
Question 90

Which of the following statements is false?

A
An unambiguous grammar has same leftmost and rightmost derivation
B
An LL(1) parser is a top-down parser
C
LALR is more powerful than SLR
D
An ambiguous grammar can never be LR(k) for any k
       Compiler-Design       Parsers       GATE 2001
Question 90 Explanation: 
Option B: LL parser is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Left most derivation of the sentence.
Option C: LALR is more powerful than SLR.
Option D: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
Question 91

Consider the following grammar with terminal alphabet ∑{a,(,),+,*} and start symbol E. The production rules of the grammar are:

              E → aA
              E → (E)
              A → +E
              A → *E
              A → ε 

(a) Compute the FIRST and FOLLOW sets for E and A.
(b) Complete the LL(1) parse table for the grammar.

A
Theory Explanation is given below.
       Compiler-Design       Parsers       GATE 2001
Question 92

The syntax of the repeat-until statement is given by the gollowing grammar

   S → repeat S1 until E  

Where E stands for expressions, S and S1 stand for statement. The non-terminals S and S1 have an attribute code that represents generated code. The nonterminal E has two attributes. The attribute code represents generated code to evaluate the expression and store its truth value in a distinct variable, and the attribute varName contains the name of the variable in which the truth value is stored? The truth-value stored in the variable is 1 if E is true, 0 if E is false.

Give a syntax-directed definition to generate three-address code for the repeatuntil statement. Assume that you can call a function newlabel( ) that returns a distinct label for a statement. Use the operator ‘\\’ to concatenate two strings and the function gen(s) to generate a line containing the string s.

A
Theory Explanation is given below.
       Compiler-Design       Syntax-Directed-Translation       GATE 2001
Question 93

(a) Remove left-recursion from the following grammar:

    S → Sa| Sb | a | b 

(b) Consider the following grammar:

    S → aSbS| bSaS |ε  

Construct all possible parse trees for the string abab. Is the grammar ambiguous?

A
Theory Explanation is given below.
       Compiler-Design       Grammar       GATE 2001
Question 94

The number of tokens in the following C statement.

printf("i = %d, &i = %x", i, &i); 

is

A
3
B
26
C
10
D
21
       Compiler-Design       Compilers       GATE 2000
Question 94 Explanation: 
We have six different types of tokens are available
(i) Keyword
(ii) Identifier
(iii) Constant
(iv) Variable
(v) String
(vi) Operator
Print = Token 1
( = Token 2
"i=%d%x" = Token 3 [Anything inside " " is one Token]
, = Token 4
i = Token 5
, = Token 6
& = Token 7
i = Token 8
) = Token 9
; = Token 10
Here, totally 10 Tokens are present in the equation.
Question 95

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

A
Leftmost derivation
B
Leftmost derivation traced out in reverse
C
Rightmost derivation
D
Rightmost derivation traced out in reverse
       Compiler-Design       Parsers       GATE 2000
Question 95 Explanation: 
Top-down parser - Leftmost derivation
Bottom-Up parser - Reverse of rightmost derivation
Question 96

Given the following expression grammar:

    E → E * F | F + E | F
    F → F - F | id  

which of the following is true?

A
* has higher precedence than +
B
- has higher precedence than *
C
+ and – have same precedence
D
+ has higher precedence than *
       Compiler-Design       Grammar       GATE 2000
Question 96 Explanation: 
The operator which is in low level that can have high preference.
Order of precedence is *, +, -.
Here * and + have equal preference, '-' can have higher precedence than + and *.
Question 97

Consider the syntax directed translation scheme (SDTS) given in the following.
Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

 E → E1 * T {E.val = E1.val * T.val}
 E → T {E.val = T.val}
 T → F – T1{T.val = F.val – T1.val}
 T → F {T.val = F.val}
 F → 2 {F.val = 2}
 F → 4 {F.val = 4} 

(a) Using this SDTS, construct a parse tree for the expression
4 – 2 – 4 * 2
and also compute its E.val.

(b) It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find E.red, the number of reductions performed while reducing an input to E.

A
Theory Explanation is given below.
       Compiler-Design       Descriptive       GATE 2000
Question 98

Which of the following is the most powerful parsing method?

A
LL (1)
B
Canonical LR
C
SLR
D
LALR
       Compiler-Design       Parsers       GATE 1999
Question 98 Explanation: 
Canonical LR is most powerful.
LR > LALR > SLR
Question 99

The number of tokens in the Fortran statement DO 10 I = 1.25 is

A
3
B
4
C
5
D
None of the above
       Compiler-Design       Compile       GATE 1999
Question 99 Explanation: 
DO → 1
10 → 2
I → 3
= → 4
1.25 → 5
Question 100

In a resident – OS computer, which of the following systems must reside in the main memory under all situations?

A
Assembler
B
Linker
C
Loader
D
Compiler
       Compiler-Design       Run-Time-Environments       GATE 1998
Question 100 Explanation: 
In many operating system loader is permanently resident in memory.
Some OS may allow virtual memory may allow the loader to be located in a region of memory that is in page table.
Question 101

Which of the following statements is true?

A
SLR parser is more powerful than LALR
B
LALR parser is more powerful than Canonical LR parser
C
Canonical LR parser is more powerful than LALR parser
D
The parsers SLR, Canonical CR, and LALR have the same power
       Compiler-Design       Parsers       GATE 1998
Question 101 Explanation: 
LR > LALR > SLR
Canonical LR parser is more powerful than LALR parser.
Question 102

Type checking is normally done during

A
lexical analysis
B
syntax analysis
C
syntax directed translation
D
code optimization
       Compiler-Design       Compilers       GATE 1998
Question 102 Explanation: 
Type checking is normally done during syntax directed translation.
Question 103

In the following grammar

         X ::= X ⊕ Y/Y
         Y ::= Z * Y/Z
         Z ::= id  

Which of the following is true?

A
‘⊕’ is left associative while ‘*’ is right associative
B
Both ‘⊕’ and ‘*’ is left associative
C
‘⊕’ is right associative while ‘*’ is left associative
D
None of the above
       Compiler-Design       Grammar       GATE 1997
Question 103 Explanation: 

⊕ is left associative.
* is right associative.
Question 104

A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which of the following is true?

A
A compiler using static memory allocation can be written for L
B
A compiler cannot be written for L; an interpreter must be used
C
A compiler using dynamic memory allocation can be written for L
D
None of the above
       Compiler-Design       Run-Time-Environments       GATE 1997
Question 104 Explanation: 
Compiler is use dynamic memory allocation then the memory will be allocated to an array at runtime.
Question 105

The conditional expansion facility of macro processor is provided to

A
test a condition during the execution of the expanded program
B
to expand certain model statements depending upon the value of a condition during the execution of the expanded program
C
to implement recursion
D
to expand certain model statements depending upon the value of a condition during the process of macro expansion
       Compiler-Design       Macros       GATE 1997
Question 105 Explanation: 
Macro is expanded during the process of Macro expansion.
Question 106

Heap allocation is required for languages

A
that support recursion
B
that support dynamic data structures
C
that use dynamic scope rules
D
None of the above
       Compiler-Design       Run-Time-Environments       GATE 1997
Question 106 Explanation: 
Heap allocation is required for languages that support dynamic data structures.
Question 107

The pass number for each of the following activities

    1. Object code generation
    2. Literals added to literal table
    3. Listing printed
    4. Address resolution of local symbols

That occur in a two pass assembler respectively are

A
1, 2, 1, 2
B
2, 1, 2, 1
C
2, 1, 1, 2
D
1, 2, 2, 2
       Compiler-Design       Assembler       GATE 1996
Question 107 Explanation: 
The functionalities from pass 1 and pass 2 are:
Pass 1:
1) Assign addresses to all statements in the program.
2) Save the values assigned to all labels for use in pass 2.
3) Perform some processing of assembler directives.
Pass 2:
1) Assemble instructions.
2) Generate data values defined by BYTE, WORD etc.
3) Perform processing of assembler directives not done during pass 1.
4) Write the program and assembling listing.
Question 108

Which of the following macros can put a micro assembler into an infinite loop?

(i)  .MACRO M1 X
     .IF EQ, X      ;if X=0 then
      M1 X + 1
     .ENDC
     .IF NE X       ;IF X≠0 then
     .WORD X        ;address (X) is stored here
     .ENDC
     .ENDM
(ii) .MACRO M2 X
     .IF EQ X
      M2 X
     .ENDC
     .IF NE, X
     .WORD X+1
     .ENDC
     .ENDM 
A
(ii) only
B
(i) only
C
both (i) and (ii)
D
None of the above
       Compiler-Design       Macros       GATE 1996
Question 108 Explanation: 
If M2 macro is called with X=0, then it will go into an infinite loop.
Question 109

A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?

A
Object code
B
Relocation bits
C
Names and locations of all external symbols defined in the object module
D
Absolute addresses of internal symbols
       Compiler-Design       Run-Time-Environments       GATE 1995
Question 109 Explanation: 
In object module it includes names and locations of all external symbols defined in the object module.
To link to external symbols it must know the location of external symbols.
Question 110

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar

S → xxW {print "1"}
S → y {print "2"}
W → Sz {print "3"} 

What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

A
23131
B
11233
C
11231
D
33211
       Compiler-Design       Parsers       GATE 1995
Question 110 Explanation: 

⇒ 23131
Note SR is bottom up parser.
Question 111

Generation of intermediate code based on an abstract machine model is useful in compilers because

A
it makes implementation of lexical analysis and syntax analysis easier
B
syntax-directed translations can be written for intermediate code generation
C
it enhances the portability of the front end of the compiler
D
it is not possible to generate code for real machines directly from high level language programs
       Compiler-Design       Compilers       GATE 1994
Question 111 Explanation: 
In Intermediate code optimizations can also enhances the probability of optimizer.
Question 112

Match the following items

A
(i) - (d), (ii) - (a), (iii) - (b), (iv) - (c)
       Compiler-Design       General       GATE 1994
Question 112 Explanation: 
Backus Normal Form (BNF) is a notation technique for context free grammars, often used to describe the syntax of languages used in computing.
Yacc (Yet Another Compiler- Compiler) is a computer program for the UNIX operating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.
Question 113

Consider the following grammar.

     S → aSB|d
     B → b 

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is _______.

A
7
       Compiler-Design       Parsers       GATE 2020
Question 113 Explanation: 

7 reductions total.
Question 114

Consider the following statements.

    I. Symbol table is accessed only during lexical analysis and syntax analysis.
    II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
    III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.

Which of the above statements is/are TRUE?

A
II only
B
I only
C
I and III only
D
None of I, II and III
       Compiler-Design       Run-Time-Environment       GATE 2020
Question 114 Explanation: 
I is wrong as Symbol table is also accessed during semantic analysis phase.
II is wrong as compilers which supports recursion require stack memory in run time environment.
III is wrong “any variable must be declared before its use” is a semantic error and not syntax error.
Question 115

Consider the productions A⟶PQ and A⟶XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.

    Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
    Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i 

Which one of the following is TRUE?

A
Only Rule 2 is L-attributed.
B
Neither Rule 1 nor Rule 2 is L-attributed.
C
Both Rule 1 and Rule 2 are L-attributed.
D
Only Rule 1 is L-attributed.
       Compiler-Design       Synthesized-Attribute       GATE 2020
Question 115 Explanation: 
In rule 2 for production A -> XY the attribute “i” is calculated from the right sibling Y in X.i = A.i + Y.s which is violating the L attribute definition, as in L attribute calculating attribute vale from RHS sibling is not allowed.
Question 116

For the program segment given below, which of the following are true?

 program main (output);
 type link = ^data;
      data = record
         d : real;
         n : link
         end;
 var ptr : link;
 begin
    new (ptr);
    ptr:=nil;
    .ptr^.d:=5.2;
    write ln(ptr)
 end. 
A
The program leads to compile time error
B
The program leads to run time error
C
The program outputs 5.2
D
The program produces error relating to nil pointer dereferencing
E
None of the above
       Compiler-Design       Compilers       GATE 1993
Question 116 Explanation: 
Note: Out of syllabus.
Question 117

A part of the system software, which under all circumstances must reside in the main memory, is:

A
text editor
B
assembler
C
linker
D
loader
E
none of the above
       Compiler-Design       General       GATE 1993
Question 117 Explanation: 
In a program the loader that can loads the object of the program from secondary memory into the main memory to execute the corresponding program. Then the loader is to be resides in the main memory.
Question 118

Consider the SLR(1) and LALR (1) parsing tables for a context free grammar. Which of the following statements is/are true?

A
The go to part of both tables may be different.
B
The shift entries are identical in both the tables.
C
The reduce entries in the tables may be different.
D
The error entries in the tables may be different.
E
B, C and D.
       Compiler-Design       Parsers       GATE 1992
Question 118 Explanation: 
Goto parts and shift entry must be same.
Reduce entry and error entry may be different due to conflicts.
Question 119

The arithmetic expression : (a + b) * c - d / e * * f is to be evaluated on a two-address machine, where each operands, the number of registers required to evaluate this expression is ______. The number of memory access of operand is __________.

A
3, 4
       Compiler-Design       Operands       GATE 1991
Question 119 Explanation: 
** is used for exponentiation.
So, in total 3 registers are required and 6 memory operations in total to fetch all operands.
Question 120

A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is ________

A
properly nested.
       Compiler-Design       Precedence-Graph       GATE 1991
Question 120 Explanation: 
A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is properly nested.
Question 121

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: A “link editor” is a program that:

A
matches the parameters of the macro-definition with locations of the parameters of the macro call
B
matches external names of one program with their location in other programs
C
matches the parameters of subroutine definition with the location of parameters of subroutine call
D
acts as link between text editor and the user
E
acts as a link between compiler and user program
       Compiler-Design       Linker-Loader       GATE 1991
Question 121 Explanation: 
Linked editor can be able to perform
1) external symbol resolution
2) relocation
Question 122

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Indicate all the true statements from the following:

A
Recursive descent parsing cannot be used for grammar with left recursion.
B
The intermediate form the representing expressions which is best suited for code optimization is the post fix form.
C
A programming language not supporting either recursion or pointer type does not need the support of dynamic memory allocation.
D
Although C does not support call by name parameter passing, the effect can be correctly simulated in C.
E
No feature of Pascal violates strong typing in Pascal.
F
A and D
       Compiler-Design       Parsers       GATE 1991
Question 122 Explanation: 
(A) It is true. Left recursive grammar if used directly in recursive descent parsing causes an infinite loop. So, left recursion must be removed before giving to a recursive descent parser.
(B) False.
(C) It is false. The language can have dynamic data types which required dynamically growing memory when data type size increases.
(D) Is true and using macro we can do this.
(E) Out of syllabus now.
Question 123

Match the pairs in the following questions:

(a) Pointer data type       (p) Type conversion
(b) Activation record       (q) Dynamic data structure
(c) Repeat-until            (r) Recursion
(d) Coercion                (s) Non-deterministic loop
A
(a) - (q), (b) - (r), (c) - (s), (d) - (p)
       Compiler-Design       Match-the-Following       GATE 1990
Question 123 Explanation: 
Pointer data type - Dynamic data structure
Activation record - Recursion
Repeat until - Non-deterministic loop
Coercion - Type conversion
Question 124

Match the pairs in the following questions:

(a) Lexical analysis         (p) DAG's
(b) Code optimization        (q) Syntax trees
(c) Code generation          (r) Push down automaton
(d) Abelian groups           (s) Finite automaton
A
(a) - (s), (b) - (p), (c) - (q), (d) - (r)
       Compiler-Design       Match-the-Following       GATE 1990
Question 124 Explanation: 
Lexical analysis - Finite automaton
Code optimization - DAG
Code generation - Syntax tree
Abelian groups - Push down automaton
Question 125

Merging states with a common core may produce __________ conflicts and does not produce ___________ conflicts in an LALR purser.

A
Reduce-Reduce, Shift-Reduce
       Compiler-Design       Parsers       GATE 1989
Question 125 Explanation: 
Merge states with a common core may produce Reduce-Reduce conflicts and does not produce Shift-Reduce conflicts in an LALR parser.
Question 126

In a compiler the module the checks every character of the source text is called:

A
The code generator.
B
The code optimizer.
C
The lexical analyser.
D
The syntax analyser.
       Compiler-Design       Compilers       GATE 1987
Question 126 Explanation: 
Lexical analyzer phase checks every character of text to identify tokens.
Question 127

An operator precedence parser is a

A
Bottom-up parser.
B
Top-down parser.
C
Back tracking parser.
D
None of the above.
       Compiler-Design       Parsers       GATE 1987
Question 127 Explanation: 
An operator precedence parser is a Bottom-up parser.
Question 128

Using longer identifiers in a program will necessarily lead to:

A
Somewhat slower compilation
B
A program that is easier to understand
C
An incorrect program
D
None of the above
       Compiler-Design       Compilers       GATE 1987
Question 128 Explanation: 
Lexical analyzer will take more time to recognize the longer identifiers.
Question 129

Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?

A
L (D) ⊂ L (G)
B
L (D) ⊃ L (G)
C
L (D) = L (G)
D
L (D) is empty
       Compiler-Design       Grammar       GATE 2007-IT
Question 129 Explanation: 
By changing the corresponding grammar, the language will not be changed.
For example, by converting NFA to DFA language will not be changed.
Question 130
Which of the following comparisons between static and dynamic type checking is incorrect?
A
Dynamic type checking slows down the execution
B
Dynamic type checking offers more flexibility to the programmers
C
In contrast to Static type checking, dynamic type checking may cause failure in runtime due to type errors
D
Unlike static type checking, dynamic type checking is done during compilation
       Compiler-Design       Compilers       ISRO-2018
Question 130 Explanation: 
→ Type checking is the process of verifying and enforcing the constraints of types, and it can occur either at compile time (i.e. statically) or at runtime (i.e. dynamically).
→ Type checking is all about ensuring that the program is type-safe, meaning that the possibility of type errors is kept to a minimum.
→ A language is statically-typed if the type of a variable is known at compile time instead of at runtime. Common examples of statically-typed languages include Ada, C, C++, C#, JADE, Java, Fortran, Haskell, ML, Pascal, and Scala.
→ Dynamic type checking is the process of verifying the type safety of a program at runtime. Common dynamically-typed languages include Groovy, JavaScript, Lisp, Lua, Objective-C, PHP, Prolog, Python, Ruby, Smalltalk and Tcl.
Question 131
Incremental Compiler is a compiler
A
which is written in a language that is different from the source language
B
compiles the whole source code to generate object code afresh
C
compiles only those portion of source code that has been modified.
D
that runs on one machine but produces object code for another machine
       Compiler-Design       Compilers       ISRO-2018
Question 131 Explanation: 
Types of compilers

1. Incremental compiler: It rebuilds all program modules, incremental compiler re-compiles only those portions of a program that have been modified.
2. Cross-compiler: If the compiled program can run on a computer whose CPU or operating system is different from the one on which the compiler runs, the compiler is a cross-compiler.
3. A bootstrap compiler: is written in the language that it intends to compile. A program that translates from a low-level language to a higher level one is a decompiler.
4. Source-to-source compiler or transpiler: A program that translates between high-level languages is usually called a source-to-source compiler or transpiler.
Question 132
DU-chains(Definition-Use) in compiler design
A
Consist of a definition of a variable and all its uses, reachable from that definition
B
Are created using a form of static code analysis
C
Are prerequisite for many compiler optimization including constant propagation and common sub-expression elimination
D
All of the above
       Compiler-Design       Compilers       ISRO-2018
Question 132 Explanation: 
→ A Use-Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A definition can have many forms but is generally taken to mean the assignment of some value to a variable (which is different from the use of the term that refers to the language construct involving a data type and allocating storage).
→ A counterpart of a UD Chain is a Definition-Use Chain (DU Chain), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions.
→ Both UD and DU chains are created by using a form of static code analysis known as data flow analysis. Knowing the use-def and def-use chains for a program or subprogram is a prerequisite for many compiler optimizations, including constant propagation and common subexpression elimination.
Question 133
Which of the following comment about peephole optimization is true?
A
It is applied to a small part of the code and applied repeatedly
B
It can be used to optimize intermediate code
C
It can be applied to a portion of the code that is not contiguous
D
It is applied in the symbol table to optimize the memory requirements.
       Compiler-Design       Code-Optimization       ISRO-2018
Question 133 Explanation: 
→ Peephole optimization is a kind of optimization performed over a very small set of instructions in a segment of generated code. The set is called a "peephole" or a "window". It works by recognizing sets of instructions that can be replaced by shorter or faster sets of instructions.

Replacement Rules:
1. Null sequences – Delete useless operations.
2. Combine operations – Replace several operations with one equivalent.
3. Algebraic laws – Use algebraic laws to simplify or reorder instructions.
4. Special case instructions – Use instructions designed for special operand cases.
5. Address mode operations – Use address modes to simplify code.
Question 134
Relative to the program translated by a compiler, the same program when interpreted runs
A
Faster
B
Slower
C
At the same speed
D
May be faster or slower
       Compiler-Design       Compilers       ISRO CS 2008
Question 134 Explanation: 

→ Interpreter translates program one statement at a time. Scans the entire program and translates it as a whole into machine code. It takes less amount of time to analyze the source code but the overall execution time is slower.

→ Compiler scans the entire program and translates it as a whole into machine code. It takes large amount of time to analyze the source code but the overall execution time is comparatively faster.
Question 135
The output of a lexical analyzer is
A
A parse tree
B
Intermediate code
C
Machine code
D
A stream of tokens
       Compiler-Design       Compilers       ISRO-2017 May
Question 135 Explanation: 
Explanation: The output of a lexical analyzer is a stream of tokens.
Question 136
Which of the following class of statement usually produces no executable code when compiled?
A
declaration
B
assignment statements
C
input and output statements
D
structural statements
       Compiler-Design       Code-Optimization       ISRO CS 2008
Question 136 Explanation: 

Each statement is classified as executable or non-executable.

Executable Statements

1.Arithmetic, logical, statement label (ASSIGN), and character assignment statements

2.Unconditional GO TO, assigned GO TO, and computed GO TO statements

3.Arithmetic IF and logical IF statements

4.Block IF, ELSE IF, ELSE, and END IF statements

5.CONTINUE statement

6.STOP and PAUSE statements

7.DO statement

8.READ, WRITE, and PRINT statements

9.REWIND, BACKSPACE, ENDFILE, OPEN, CLOSE, and INQUIRE statements

10.CALL and RETURN statements

11.END statement

Non-executable Statements

1.PROGRAM, FUNCTION, SUBROUTINE, ENTRY, and BLOCK DATA statements

2.DIMENSION, COMMON, EQUIVALENCE, IMPLICIT, PARAMETER, EXTERNAL, INTRINSIC, and SAVE statements

3.INTEGER, REAL, DOUBLE PRECISION, COMPLEX, LOGICAL, and CHARACTER type-statements

4.DATA statement

5.FORMAT statement

6.Statement function statement
Question 137
The access time of the symbol table will be logarithmic if it is implemented by
A
Linear list
B
Search tree
C
Hash table
D
Self organization list
       Compiler-Design       Symbol-Table       ISRO-2016
Question 137 Explanation: 
Access time of the symbolic table will be logarithmic if it is implemented by search time.
Question 138
Recursive descent parsing is an example of
A
Top-down parsers
B
Bottom-up parsers
C
Predictive parsers
D
None of the above
       Compiler-Design       Parsers       ISRO-2016
Question 138 Explanation: 
→ A recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar.
→ Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.
Question 139
A top-down parser generates
A
Rightmost Derivation
B
Rightmost derivation in reverse
C
Leftmost derivation
D
Leftmost derivation in reverse
       Compiler-Design       Parsers       ISRO-2016
Question 139 Explanation: 
→ Top-down parsing can be viewed as an attempt to find leftmost derivations of an input-stream by searching for parse-trees using a top-down expansion of the given formal grammar rules.
→ The inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules.
Question 140
Peephole optimization is a form of
A
Loop optimization
B
Local optimization
C
Constant folding
D
Data flow analysis
       Compiler-Design       Code-Optimization       ISRO-2016
Question 140 Explanation: 
→ Peephole optimization technique works locally on the source code to transform it into an optimized code.
→ By locally, we mean a small portion of the code block at hand.
→ These methods can be applied on intermediate codes as well as on target codes.
Question 141
Substitution of values for names (whose values are constants) is done in
A
Local optimization
B
Loop optimization
C
Constant folding
D
Strength reduction
       Compiler-design       Code-Optimization       ISRO CS 2009
Question 141 Explanation: 
Expressions with constant operands can be evaluated at compile time, thus improving run-time performance and reducing code size by avoiding evaluation at compile-time.
Example:
In the code fragment below, the expression (3 + 5) can be evaluated at compile time and replaced with the constant 8.

int f (void)
{
return 3 + 5;
}

Below is the code fragment after constant folding.

int f (void)
{
return 8;
}
Question 142
Which one of the following is correct about the statements are given below? I.  All function calls are resolved at compile time in C language II. All function calls are resolved at compile time in C++ language
A
Only II is correct
B
Both I and II are correct
C
Only I is correct
D
Both I and II are incorrect
       Compiler-Design       Compilers       ISRO-2016
Question 142 Explanation: 
Both statements are wrong. I. Logical errors can’t solve in compile time. Like dividing by error.
II. In c++ also we have to write exceptions.
Question 143
A simple two-pass assembler does which of the following in the first pass:
A
Checks to see if the instructions are legal in the current assembly mode
B
It allocates space for the literals.
C
It builds the symbol table for the symbols and their values.
D
All of these
       Compiler-Design       Assembler       ISRO-2016
Question 143 Explanation: 
2-pass Assembler can perform all of above operations.
Question 144
In compiler terminology reduction in strength means
A
Replacing run time computation by compile time computation
B
Removing loop invariant computation
C
Removing common subexpressions
D
replacing a costly operation by a relatively cheaper one
       Compiler-Design       Code-Optimization       ISRO CS 2011
Question 144 Explanation: 
An optimization method in which an operator is changed to a less-expensive operator;
Example: Exponentiation is replaced by multiplication and multiplication is in return replaced by addition.(x * 2 becomes x + x)
Question 145
Which of the following statements about peephole optimization is False?
A
It is applied to a small part of the code
B
It can be used to optimize intermediate code
C
To get the best out of this, it has to be applied repeatedly
D
It can be applied to the portion of the code that is not contiguous
       Compiler-Design       Code-Optimization       ISRO CS 2011
Question 145 Explanation: 
Peephole optimization is a type of Code Optimization performed on a small part of the code. It is performed on the very small set of instructions in a segment of code.
It basically works on the theory of replacement in which a part of code is replaced by shorter and faster code without change in output.
Question 146
Which variable does not drive a terminal string in grammar?
S → AB
A → a
B → b
B → C
A
A
B
B
C
C
D
S
       Compiler-Design       Context-free-grammar       ISRO CS 2011
Question 146 Explanation: 
C is the useless variable as there is no production rule which replaces C with a terminal. Hence it does not derive any non terminal.
Question 147
Shift reduce parsing belongs to a class of
A
bottom up parsing
B
top down parsing
C
recursive parsing
D
predictive parsing
       Compiler-Design       Parsers       ISRO CS 2013
Question 147 Explanation: 
→ A shift-reduce parser is a class of efficient, table-driven bottom-up parsing methods for computer languages and other notations formally defined by a grammar.
→ The parsing methods most commonly used for parsing programming languages, LR parsing and its variations, are shift-reduce methods.

Question 148
Which of the following productions eliminate left recursion in the productions given below:
S → Aa | b
A → Ac | Sd | ε
A
S → Aa | b
A → bdA’
A’ → A’c
| A’ba | A | ε
B
S → Aa | b
A → A’ |
bdA’,
A’ → cA’
| adA’ | ε
C
S → Aa | b
A → A’c |
A’d
A’ → bdA’
| cA | ε
D
S → Aa | b
A → cA’ |
adA’ | bdA’
A’ → A | ε
       Compiler-Design       Parsers       ISRO CS 2013
Question 148 Explanation: 
Question 149

A bottom-up parser generates :

A
Leftmost derivation in reverse
B
Right-most derivation in reverse
C
Left-most derivation
D
Right-most derivation
       Compiler-Design       Syntax-tree-and-context-flow-graph       UGC-NET CS 2018 JUNE Paper-2
Question 149 Explanation: 
A bottom-up parser uses Right-most derivation in reverse order to decide “What to Reduce”.
Question 150
Identify the correct nodes and edges in the given intermediate code:
(1) i=1
(2) t1=5*I
(3) t2=4*t1
(4) t3=t2
(5) a[t3]=0
(6) i=i+1;
(7) if i<15 goto(2)
A
33
B
44
C
43
D
34
       Compiler-Design       Nielit Scentist-B [02-12-2018]
Question 150 Explanation: 
Step-1: Initialization we are taking one node
Step-2: From 2nd statement to 6th statement we are performing some tasks.
Step-3: It indicate if condition, so it’s another statement. And the back loop indicates goto statement.
Here, total 3 nodes and 3 edges using control flow graph.

In options they have to give like this
3 and 3
4 and 4
4 and 3
3 and 4
But they combines the node value and edge value. It seems different value.
Question 151
__number of queues are needed to implement symbol and is acting as permanent database
A
Variable Table
B
Terminal Table
C
Keyword Table
D
Identifier Table
       Compiler-Design       Nielit Scentist-B [02-12-2018]
Question 151 Explanation: 
Symbol Table is an important data structure created and maintained by the compiler in order to keep track of semantics of variable i.e. it stores information about scope and binding information about names, information about instances of various entities such as variable and function names, classes, objects, etc.
Symbol Table entries: Each entry in symbol table is associated with attributes that support
→ compiler in different phases.
→ Items stored in Symbol table:
→ Variable names and constants
→ Procedure and function names
→ Literal constants and strings
→ Compiler generated temporaries
→ Labels in source languages
Question 152
Identify the total number of tokens in the given statements printf(“A%B=”, &i);
A
7
B
8
C
9
D
13
       Compiler-Design       Nielit Scentist-B [02-12-2018]
Question 152 Explanation: 
The tokens are
Printf
(
“A%B=”
,
&
I
)
;
Question 153
Which of the following code replacements is an example of operator strength reduction?
A
Replace P^2 by P*P
B
Replace P*16 by P<< 4
C
Replace pow(P,3) by P*P*P
D
Replace (P <<5) -P by P*3
       Compiler-Design       Nielit Scentist-B [02-12-2018]
Question 153 Explanation: 
Strength Reduction :
It is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array addressing.
Examples:
Replacing a multiplication within a loop with an addition
Replacing an exponentiation within a loop with a multiplication
According to options, Option B is most suitable answer.
Question 154
____ merges the bodies of two loops.
A
Loop rolling
B
Loop folding
C
Loop merge
D
Loop jamming
       Compiler-Design       Nielit Scentist-B [02-12-2018]
Question 154 Explanation: 
→ Loop fusion (or loop jamming) is a compiler optimization and loop transformation which replaces multiple loops with a single one.
→ Loop fission (or loop distribution) is a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop's body.
Question 155
____ merges the bodies of two loops.
A
Loop rolling
B
Loop folding
C
Loop merge
D
Loop jamming
       Compiler-Design       Nielit Scentist-B [02-12-2018]
Question 155 Explanation: 
→ Loop fusion (or loop jamming) is a compiler optimization and loop transformation which replaces multiple loops with a single one.
→ Loop fission (or loop distribution) is a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop's body.
Question 156
Which of the following can be accessed by transfer vector approach of linking?
A
External data segments
B
External subroutines
C
data located in other procedure
D
All of these
       Compiler-Design       External-subroutines       Nielit Scientist-C 2016 march
Question 156 Explanation: 
● The transfer vector approach is straightforward, but requires additional memory at execution time for the transfer vector and additional time due to the indirect references. Indexing or indirection on externals may not occur correctly with the transfer vector approach.
● Data segment stores program data. This data could be in form of initialized or uninitialized variables, and it could be local or global.
● External subroutines are routines/procedures that are created and maintained separately from the program that will be calling them
Question 157
YACC builds up
A
SLR parsing table
B
Canonical LR parsing table
C
LALR parsing table
D
None of these
       Compiler-Design       Parsers       Nielit Scientist-C 2016 march
Question 157 Explanation: 
● YACC (Yet Another Compiler-Compiler) is a computer program.
● It is a Look Ahead Left-to-Right (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus–Naur Form (BNF)
Question 158
Micro program is
A
the name of source program in micro computers
B
the set of instructions indicating the primitive operations in a system
C
primitive form of macros used in assembly language programming
D
program of very small size
       Compiler-Design       Micro-Program       Nielit Scientist-C 2016 march
Question 158 Explanation: 
● Micro program is a set of microinstructions that defines the individual operations that a computer carries out in response to a machine-language instruction.
● A ​ microinstruction​ is a bit pattern in which each bit (or combination of bits) drives the control signals of the hardware.
Question 159
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       Nielit Scientist-B CS 22-07-2017
Question 159 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 rightmost 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 160
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       Nielit Scientist-B CS 22-07-2017
Question 160 Explanation: 
Lexical analysis is the first phase of a compiler. It takes the modified source code from language preprocessors that are written in the form of sentences.
The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.
In programming language, keywords, constants, identifiers, strings, numbers, operators and punctuations symbols can be considered as tokens.
Question 161
A system program that combines the separately compiled modules of a program into a form suitable for execution
A
Assembler
B
linking loader
C
cross compiler
D
load and go
       Compiler-Design       Linker-Loader       Nielit Scientist-B CS 22-07-2017
Question 161 Explanation: 
An assembler is a type of computer program that interprets software programs written in assembly language into machine language, code and instructions that can be executed by a computer.
A loader which combines the functions of a relocating loader with the ability to combine a number of program segments that have been independently compiled into an executable program.
A cross compiler is a compiler capable of creating executable code for a platform other than the one on which the compiler is running.
Question 162
Which of the following statements is false?
A
There exist parsing algorithms for some programming languages whose complexities are less than O(n3)
B
A programming language which allows recursion can be implemented with static storage allocation
C
L-attributed definition can be evaluated in the framework of bottom-up parsing
D
Code improving transformation can be performed at both source language and intermediate code level.
       Compiler-Design       Nielit STA [02-12-2018]
Question 162 Explanation: 
→ Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
→ Statement II is false, as a programming language which allows recursion requires dynamic storage allocation.
→ Statement III is True, as L-attributed definition (assume for instance the L-attributed definition has synthesized attribute only) can be evaluated in bottom up framework.
→ Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Question 163
In a single pass assembler, most of the forward references can be avoided by putting the restriction
A
on the number of strings/lifereacs
B
that the data segment must be defined after the code segment
C
on unconditional rump
D
that the data segment be defined before the code segment
       Compiler-Design       Assembler       Nielit Scientist-B CS 2016 march
Question 163 Explanation: 
Data segment − It is represented by .data section and the .bss. The .data section is used to declare the memory region, where data elements are stored for the program. This section cannot be expanded after the data elements are declared, and it remains static throughout the program.
The .bss section is also a static memory section that contains buffers for data to be declared later in the program. This buffer memory is zero-filled.
Code segment − It is represented by .text section. This defines an area in memory that stores the instruction codes. This is also a fixed area.
Question 164

The grammar S ⟶ (S) | SS | ∈ is not suitable for predictive parsing because the grammar is

A
An Operator Grammar
B
Right Recursive
C
Left Recursive
D
Ambiguous
       Compiler-Design       Parsers       UGC-NET CS 2018 DEC Paper-2
Question 164 Explanation: 
The grammar is ambiguous, as to derive string ( )( )( ) more than one parse tree exists.
Question 165
Pseudo-instructions are
A
assembler directives
B
instructions in any program that have no corresponding machine code instruction
C
instruction in any program whose presence or absence will not change the output for any input
D
none of these
       Compiler-Design       Assembler       NieLit STA 2016 March 2016
Question 165 Explanation: 
Pseudo Instructions are special commands to the assembler about the positioning of the program, the address the program should presumed to be assembled at, the name of the module, data declarations, the title and printing options for the program, defining and calling macros, macro looping and test, and end of source code. Unless a machine instruction is issued, these do not generate executable code.
Question 166

Consider the following Grammar G :

S➝ A | B
A➝ a | c
B➝ b | c

Where {S,A,B} is the set of non-terminals, {a,b,c} is the set of terminals.

Which of the following statement(s) is/are correct ?

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

Choose the correct answer from the code given below :

Code :
A
Both S1 and S2
B
Only S2
C
Neither S1 nor S2
D
Only S1
       Compiler-Design       Parsers       UGC-NET CS 2018 DEC Paper-2
Question 166 Explanation: 
For generating string “c” we have two different parse trees.

Since the grammar is Ambiguous so the strings generated by the grammar G can’t be parsed by LR(1) or LL(1) parser.
Question 167
The identification of common sub-expression and replacement of run time computations by compile-time computations is:
A
Local optimization
B
Constant folding
C
Loop Optimization
D
Data flow analysis
       Compiler-Design       Code Optimization       Nielit Scientist-B CS 4-12-2016
Question 167 Explanation: 
● Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime.It can more accurately propagate constants and simultaneously remove dead code
● Global optimization refers to finding the optimal value of a given function among all possible solution whereas local optimization finds the optimal value within the neighboring set of candidate solution.
● Loop optimization is the process of increasing execution speed and reducing the overheads associated with loops. It plays an important role in improving cache performance and making effective use of parallel processing capabilities. Most execution time of a scientific program is spent on loops; as such, many compiler optimization techniques have been developed to make them faster.
● Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program.
Question 168
The structure or format of data is called:
A
Syntax
B
Struct
C
Semantic
D
none of the above
       Compiler-Design       Basics       Nielit Scientist-B CS 4-12-2016
Question 168 Explanation: 
Semantics defines how a particular pattern to be interpreted, and what action is to be taken based on that interpretation.
Question 169
The graph that shows basic blocks and their successor relationship is called:
A
DAG
B
Control graph
C
Flow graph
D
Hamiltonian graph
       Compiler-Design       Code-Optimization       Nielit Scientist-B CS 4-12-2016
Question 169 Explanation: 
→ Flow graph shows the basic blocks
→ A flow graph is a form of digraph associated with a set of linear algebraic or differential equations.
Definition: "A signal flow graph is a network of nodes (or points) interconnected by directed branches, representing a set of linear algebraic equations. The nodes in a flow graph are used to represent the variables, or parameters, and the connecting branches represent the coefficients relating these variables to one another. The flow graph is associated with a number of simple rules which enable every possible solution [related to the equations] to be obtained."
Question 170
A top down parser generates:
A
Leftmost derivation
B
rightmost derivation
C
Leftmost derivation in reverse
D
Rightmost derivation in reverse
       Compiler-Design       Compilers       Nielit Scientist-B CS 4-12-2016
Question 170 Explanation: 
● When the parser starts constructing the parse tree from the start symbol and then tries to transform the start symbol to the input, it is called top-down parsing.
● Top-down parsing can be viewed as an attempt to find leftmost derivations of an input-stream by searching for parse-trees using a top-down expansion of the given formal grammar rules.
Question 171
Syntax directed translation scheme is desirable because:
A
It is based on the syntax
B
It is easy to modify
C
Its description is independent of any implementation
D
All of these
       Compiler-Design       Syntax-Directed-Translation       Nielit Scientist-B CS 4-12-2016
Question 171 Explanation: 
Syntax-directed translation refers to a method of compiler implementation where the source language translation is completely driven by the parser.
A common method of syntax-directed translation is translating a string into a sequence of actions by attaching one such action to each rule of a grammar.
Question 172
The output of lexical analyzer is:
A
A set of regular expressions
B
Strings of character
C
Syntax tree
D
Set of tokens
       Compiler-Design       Compilers       Nielit Scientist-B CS 4-12-2016
Question 172 Explanation: 
● Lexical analysis is the first phase of a compiler. It takes the modified source code from language preprocessors that are written in the form of sentences.
● The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.
Question 173
Given the following expression grammar:
E→ E*F | F+E |F
F→ F-F | id
Which of the following is true?
A
* has higher precedence than +
B
– has higher precedence than *
C
+ and – have same precedence
D
+ has higher precedence than *
       Compiler-Design       Associativity-and-Precedence       ISRO CS 2015
Question 173 Explanation: 
The operator which is in low level that can have high preference.
Order of precedence is *, +, -.
Here * and + have equal preference, '-' can have higher precedence than + and *.
Question 174
The number of tokens in the following C statement is
printf(“i=%d, &i=%x”, i&i);
A
13
B
6
C
10
D
0
       Compiler-Design       Compilers       ISRO CS 2015
Question 174 Explanation: 

Question 175
Which grammar rules violate the requirement of the operator grammar? A, B, C are variables and a, b, c are terminals 1) A → BC 2) A → CcBb 3) A → BaC 4) A → ε
A
1 only
B
1 and 2 only
C
1 and 3 only
D
1 and 4 only
       Compiler-Design       Parsers       ISRO CS 2015
Question 175 Explanation: 
Operator values doesn't contains nullable values and two adjacent non-terminals on RHS production.
i) On RHS it contains two adjacent non-terminals.
ii) Have nullable values.
Question 176
Which one of the following is a top-down parser?
A
Recursive descent parser
B
Shift left associative parser
C
SLR(k) parser
D
LR(k) parser
       Compiler-Design       Parsers       ISRO CS 2015
Question 176 Explanation: 

Question 177
YACC stands for
A
yet accept compiler constructs
B
yet accept compiler compiler
C
yet another compiler construct
D
yet another compiler compiler
       Compiler-Design       Parsers       ISRO CS 2015
Question 177 Explanation: 
→ Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson.
→ It is a Look Ahead Left-to-Right (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus-Naur Form (BNF)
Question 178
Which statement is true?
A
LALR parser is more powerful and costly as compare to other parsers
B
All CFG’s are LP and not all grammars are uniquely defined
C
Every SLR grammar is unambiguous but not every unambiguous grammar is SLR
D
LR(K) is the most general backtracking shift reduce parsing method
       Compiler-Design       Parsers       ISRO CS 2015
Question 178 Explanation: 

Option-A: LR > LALR > SLR

Canonical LR parser is more powerful than LALR parser. So, it FALSE

Option-B: Here, LP is linear precedence. Every grammar generated by LP are CFG but all CFG's are not LP. So, it is false

Option-C: TRUE

Option-D: LR(K) is general non backtracking shift reduce parsing method. So, It is false
Question 179

With respect to compiler design, "recursive descent" is a ____ parsing technique that reads the inputs from ____.

A
top-down, right to left
B
top-down, left to right
C
bottom up, right to left
D
bottom up, left to right
       Compiler-Design       Parsers       JT(IT) 2018 PART-B Computer Science
Question 179 Explanation: 
A recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.
→ Top down parsers reads the input from left to right and bottom up parsers are reads the input from left to right and reverse.
Question 180

Which of the following is NOT a bottom up, shift reduce parser?

A
LR parser
B
LL parser
C
SLR parser
D
LALR parser
       Compiler-Design       Parsers       JT(IT) 2018 PART-B Computer Science
Question 180 Explanation: 
Bottom Up SR Parsers are:
1. SLR
2. LALR
3. CLR
4. LR(0)
Top Down parser:
1. Recursive descent
2. Non Recursive descent(LL(1))
Question 181
Which of the following is machine independent optimization?
A
Loop optimization
B
Redundancy Elimination
C
Folding
D
All of the options
       Compiler-Design       Nielit Scientist-B 17-12-2017
Question 181 Explanation: 

Question 182
Which of the following statements is/ are false?
S1: LR(0) grammar and SLR(1) grammar are equivalent
S2: LR(1) grammar are subset of LALR(1) grammars
A
S1 only
B
S1 and S2 both
C
S2 only
D
None of the options
       Compiler-Design       Nielit Scientist-B 17-12-2017
Question 182 Explanation: 
The space of grammars:
FALSE: S1: LR(0) grammar and SLR(1) grammar are equivalent
FALSE: S2: LR(1) grammar are subset of LALR(1) grammars
Question 183
The optimization phase in a compiler gererally:
A
Reduces the space of the code
B
Optimization the code to reduce execution time
C
Both (A) and (B)
D
Neither (A) nor (B)
       Compiler-Design       Nielit Scientist-B 17-12-2017
Question 183 Explanation: 
→ An optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program.
→ The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied.
→ The growth of portable computers has created a market for minimizing the power consumed by a program
Question 184

Which of the following phases of the compilation process is also known as parsing?

A
Lexical analysis
B
Code optimization
C
Syntax analysis
D
Semantic analysis
       Compiler-Design       Parsers       JT(IT) 2018 PART-B Computer Science
Question 184 Explanation: 
Parsing, syntax analysis, or syntactic analysis is the process of analysing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term parsing comes from Latin pars (orationis), meaning part (of speech).
Question 185
Resolution of externally defined symbols is performed by____
A
Linker
B
Loader
C
Compiler
D
Editor
       Compiler-Design       Linker       KVS 22-12-2018 Part-B
Question 185 Explanation: 
→ A linker is a computer utility program that takes one or more object files generated by a compiler and combines them into a single executable file, library file, or another 'object' file.
→ A loader is a major component of an operating system that ensures all necessary programs and libraries are loaded, which is essential during the startup phase of running a program.
→ It places the libraries and programs into the main memory in order to prepare them for execution.
Question 186
Which of the following are language processor?
A
Assembler and editor
B
Compiler and word processor
C
Only Assembler and compiler
D
Assembler,Compiler and Interpreter
       Compiler-Design       Compilers-and-Parsers       KVS 22-12-2018 Part-B
Question 186 Explanation: 
→ Compiler : Compilers are used to convert high level languages (like C, C++ ) into machine code Example : gcc , Microsoft Visual Studio
→ Assembers : Assembler are used to convert assembly language code into machine code.
→ Interpreter : An interpreter is a computer program which executes a statement directly (at runtime).
→ Examples: python , LISP
Question 187
Synthesized attribute can easily be simulated by an
A
LL grammar
B
ambiguous grammar
C
LR grammar
D
none of the above
       Compiler-Design       Syntax-Directed-Translation       Nielit Scientific Assistance CS 15-10-2017
Question 187 Explanation: 
● A ​ Synthesized attribute ​ is an attribute of the nonterminal on the left-hand side of a production.
● Synthesized attributes represent information that is being passed up the parse tree.
● LR-attributed grammars allow the attributes to be evaluated on LR parsing. As a result, attribute evaluation in LR-attributed grammars can be incorporated conveniently in bottom-up parsing.
Question 188
Consider an ε-tree CFG. If for every pair of productions A → u and A → v
A
if FIRST(u) ∩ FIRST(v) is empty then the CFG has to be LL(1)
B
If the CFG is LL(1) then FIRST(u) ∩ FIRST(v) has to be empty
C
Both (A) and (B)
D
None of the above
       Compiler-Design       Parsers       Nielit Scientific Assistance CS 15-10-2017
Question 188 Explanation: 
The condition for a grammar to be LL(1)
Theorem: A context free grammar G=(V​ T​ , V​ N​ , S,P) is LL(1) if and if only if for every nonterminal A and every strings of symbols ⍺,β such that ⍺≠β and A → ⍺,β we have
1. First(⍺) ∩ First (β) ∩ Follow(A)=Θ.
2. If ⍺ *⇒ ε then First(β) ∩ Follow(A)= Θ.
If grammar is epsilon free then condition 2 is not required.
Now as per condition 1, for every non-terminal A, if we have A → u and A→v
And First(u) First(v) = φ and CFG is epsilon free then it must be LL(1) and if epsilon free CFG is LL(1) then it must satisfy the condition 1.
Question 189

Which of the following checks are not included in semantic analysis done by the compiler:

A
Type checks
B
Spelling checks
C
Uniquencess checks
D
Flow of control checks
       Compiler-Design       Compilers       JT(IT) 2016 PART-B Computer Science
Question 189 Explanation: 
The following tasks should be performed in semantic analysis:
1. Scope resolution
2. Type checking
3. Array-bound checking
Question 190
In a computer, keywords of a language are recognized during
A
Parsing of the program
B
Code generation
C
Lexical analysis of the program
D
Data flow diagrams
       Compiler-Design       Compilers-and-Parsers       KVS 30-12-2018 Part B
Question 190 Explanation: 
Lexical analyzer reads the characters from source code and convert it into tokens.
Different tokens or lexemes are:
→Keywords
→Identifiers
→Operators
→Constants
Question 191
Match the description of several parts of a classic optimizing compiler in List - I, with the names of those parts in List - II:
A
(a)-(iii), (b)-(iv), (c)-(ii), (d)-(i)
B
(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
C
(a)-(ii), (b)-(iv), (c)-(i), (d)-(iii)
D
(a)-(ii), (b)-(iv), (c)-(iii), (d)-(i)
       Compiler-Design       Compilers       UGC NET CS 2017 Nov- paper-2
Question 191 Explanation: 
Parser→ A part of a compiler that is responsible for recognizing synta
Scanner→ An IR-to-IR transformer that tries to improve the IR program in some way (Intermediate representation)
Semantic Analysis→ A part of a compiler that understand the meaning of variable names and other symbols and checks that they are used in ways consistent with their definitions
Optimizer→ An IR-to-IR transformer that tries to improve the IR program in some way (Intermediate representation)
Question 192
In Distributed system, the capacity of a system to adapt the increased service load is called __________ .
A
Tolerance
B
Scalability
C
Capability
D
Loading
       Compiler-Design       Linker-Loader       UGC NET CS 2017 Nov- paper-2
Question 192 Explanation: 
→ The capacity of a system to adapt the increased service load is called scalability.
→ Scalability is the capability of a system, network, or process to handle a growing amount of work, or its potential to be enlarged to accommodate that growth.
Note: A scalable system is any system that is flexible with its number of components.
Question 193
Consider the following statements related to compiler construction :
I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata.
II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine.
Which of the above statement(s) is/are correct ?
A
Only I
B
Only II
C
Both I and II
D
Neither I nor II
       Compiler-Design       Compilers       UGC NET CS 2017 Jan -paper-2
Question 193 Explanation: 
FALSE: Lexical Analysis is specified by regular grammars and implemented by finite automata.
FALSE: Syntax Analysis is specified by context-free grammars and implemented by pushdown automata.
Question 194
In compiler optimization, operator strength reduction uses mathematical identities to replace slow math operations with faster operations. Which of the following code replacements is an illustration of operator strength reduction ?
A
Replace P + P by 2 * P or Replace 3 + 4 by 7.
B
Replace P * 32 by P << 5
C
Replace P * 0 by 0
D
Replace (P << 4) – P by P * 15
       Compiler-Design       Code-Optimization       UGC NET CS 2016 Aug- paper-2
Question 194 Explanation: 
Option (A)​ is not correct because multiplication operation can be performed faster using Left-Shift(<<) operator instead of "+" operator and "3+4=7" is the example of Folding machine independent optimization method instead of operator strength reduction .
Option(B)​ is correct because here to speedup the multiplication operation, * operator is replaced by Left-Shift operator.
Option(C)​ is not correct because the method used for compiler optimization is not correct. For given statements to perform compiler optimization, we simply eliminate such statements from the code and this method of elimination is called as Algebraic Simplification.
Option(D)​ is also not correct because bitwise operator is more faster than multiplication.
Question 195
Which of the following are the principles tasks of the linker?
I. Resolve external references among separately compiled program units.
II. Translate assembly language to machine code.
III. Relocate code and data relative to the beginning of the program.
IV. Enforce access-control restrictions on system libraries
A
I and II
B
I and III
C
II and III
D
I and IV
       Compiler-Design       Linker-Loader       UGC NET CS 2016 Aug- paper-2
Question 195 Explanation: 
Linker:
A linker or link editor is a computer utility program that takes one or more object files generated by a compiler and combines them into a single executable file, library file, or another 'object' file.
Principles:
1. Resolve external references among separately compiled program units
2. Relocate code and data relative to the beginning of the program.
→ Assembler, Translate assembly language to machine code.
Question 196
In _______, the bodies of the two loops are merged together to form a single loop provided that they do not make any references to each other.
A
Loop unrolling
B
Strength reduction
C
Loop concatenation
D
Loop jamming
       Compiler-Design       Code-Optimization       UGC NET CS 2016 July- paper-2
Question 196 Explanation: 
Loop Unrolling:​ Loop unrolling refers to method of decreasing the number of time a loop is executed.
Strength reduction:​ It is a machine independent code optimization technique in which a costly operation(operation which takes more time to execute) is replaced with the cheaper. operation(operation which takes less execution time)
Loop Jamming:​ It is a loop optimization technique in which bodies of two loops are combined together to decrease the number of loops.
Question 197
​Which of the following is not typically a benefit of dynamic linking?
I. Reduction in overall program execution time.
II. Reduction in overall space consumption in memory.
III. Reduction in overall space consumption on disk.
IV. Reduction in the cost of software updates.
A
I and IV
B
I only
C
II and III
D
IV only
       Compiler-Design       Linker-Loader       UGC NET CS 2016 July- paper-2
Question 197 Explanation: 
TRUE: Reduction in overall program execution time.
FALSE: Reduction in overall space consumption in memory.
FALSE: Reduction in overall space consumption on disk.
FALSE: Reduction in the cost of software updates.
Note: Except statement-I remaining all statements are not related to dynamic linking.
Question 198
Which of the following is FALSE?
A
The grammar S → a Sb |bSa|SS|∈, where S is the only non-terminal symbol and ∈ is the null string, is ambiguous.
B
SLR is powerful than LALR.
C
An LL(1) parser is a top-down parser.
D
YACC tool is an LALR(1) parser generator.
       Compiler-Design       Parsers       UGC NET CS 2016 July- paper-2
Question 198 Explanation: 
A grammar is said to be ambiguous if and only if it can generate parse trees of both ​ Left ​ Most Derivation or Right Most Derivation.
In this grammar we are having two different parse trees For string "aabb" using leftmost derivation only.

Statement B is wrong because in LALR we use lookahead symbols to put the reduce entries into the parsing table. Because of which number of blank entries in LALR parser are more than that of SLR parser which in turn increases the error detection capability of LALR parser. So LALR parser is more powerful than SLR.
Statement C is true because LL(1) parser is a top-down parser
Statement D is also true because YACC(Yet Another Compiler Compiler) is a tool which generates LALR parser for a given grammar.
Question 199
Loop unrolling is a code optimization technique:
A
that avoids tests at every iteration of the loop.
B
that improves performance by decreasing the number of instructions in a basic block.
C
that exchanges inner loops with outer loops
D
that reorders operations to allow multiple computations to happen in parallel
       Compiler-Design       Code-Optimization       UGC NET CS 2015 Dec- paper-2
Question 199 Explanation: 
→ Loop unrolling is a code optimization technique that avoids tests at every iteration of the loop.
→ The goal of loop unwinding is to increase a program's speed by reducing (or) eliminating instructions that control the loop, such as pointer arithmetic and "end of loop" tests on each iteration.
Question 200
The translator which performs macro calls expansion is called:
A
Macro processor
B
Micro preprocessor
C
Macro preprocessor
D
Dynamic Linker
       Compiler-Design       Pre-Processor       UGC NET CS 2015 Jun- paper-2
Question 200 Explanation: 
→ The C preprocessor is a macro preprocessor (allows you to define macros) that transforms your program before it is compiled. These transformations can be inclusion of header file, macro expansions,etc,...
→ All preprocessing directives begins with a # symbol. For example,
#define PI 3.14
Question 201
Which one from the following is false?
A
LALR parser is Bottom up parser
B
A parsing algorithm which performs a left to right scanning and a right most deviation is RL (1)
C
LR parser is Bottom up parser.
D
In LL(1), the 1 indicates that there is a one - symbol look - ahead.
       Compiler-Design       Parsers       UGC NET CS 2015 Jun- paper-2
Question 201 Explanation: 
TRUE: LALR parser is Bottom up parsers.
TRUE: LR parser is Bottom up parser. It has SLR, LALR and SLR.
TRUE: In LL(1), the 1 indicates that there is a one - symbol look - ahead.
FALSE: A parsing algorithms scans right to left and reverse order.
Question 202
Which phase of compiler generates stream of atoms?
A
Syntax Analysis
B
Lexical Analysis
C
Code Generation
D
Code Optimization
       Compiler-Design       Phases-of-Compilers       UGC NET CS 2015 Jun- paper-2
Question 202 Explanation: 
Syntax analysis: understanding the structure of the source code
1. Tokenizing: creating a stream of “atoms”
2. Parsing: matching the atom stream with the language grammar
XML output = one way to demonstrate that the syntax analyzer works
Question 203
Which activity is not included in the first pass of two pass assemblers ?
A
Build the symbol table
B
Construct the intermediate code
C
Separate mnemonic opcode and operand fields
D
None of the above
       Compiler-Design       Assembler       UGC NET CS 2004 Dec-Paper-2
Question 203 Explanation: 
Two Pass Assemblers:
Pass-1:
1. Assign addresses to all statements in the program
2. Save the values assigned to all labels for use in Pass2
3. Perform some processing of assembler directives
Pass-2:
1. Assemble instructions Generate data values defined by BYTE,WORD
2. Perform processing of assembler directives not done in Pass 1
3. Write the object program and the assembly listing
Question 204
Code optimization is responsibility of :
A
Application programmer
B
System programmer
C
Operating system
D
All of the above
       Compiler-Design       Code-Optimization       UGC NET CS 2004 Dec-Paper-2
Question 204 Explanation: 
Code optimization is responsibility of system programmer.
Question 205
Which activity is included in the first pass of two pass assemblers ?
A
Build the symbol table
B
Construct the intermediate code
C
Separate mnemonic opcode and operand fields
D
None of these
E
A,B and C
       Compiler-Design       Assembler       UGC NET CS 2004 Dec-Paper-2
Question 205 Explanation: 
Two Pass Assemblers:
Pass-1:
1. Assign addresses to all statements in the program
2. Save the values assigned to all labels for use in Pass2
3. Perform some processing of assembler directives
Pass-2:
1. Assemble instructions Generate data values defined by BYTE,WORD
2. Perform processing of assembler directives not done in Pass-1
3. Write the object program and the assembly listing.
Activities:
1. Build the symbol table
2. Construct the intermediate code
3. Separate mnemonic opcode and operand fields
Question 206
In two pass assembler the symbol table is used to store :
A
Label and value
B
Only value
C
Mnemonic
D
Memory Location
       Compiler-Design       Assembler       UGC NET CS 2004 Dec-Paper-2
Question 206 Explanation: 
In two pass assembler the symbol table is used to store memory location.
Question 207
A Top-down Parser generates :
A
Leftmost derivation
B
Rightmost derivation
C
Rightmost derivation in reverse
D
Leftmost derivation in reverse
       Compiler-Design       Parsers       UGC NET CS 2005 Dec-Paper-2
Question 207 Explanation: 
→ Top-down parsing can be viewed as an attempt to find leftmost derivations of an input-stream by searching for parse-trees using a top-down expansion of the given formal grammar rules.
→ Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules.
Question 208
A general macroprocessor is an in built function of :
A
Loader
B
Linker
C
Editor
D
Assembler
       Compiler-Design       Assembler       UGC NET CS 2005 Dec-Paper-2
Question 208 Explanation: 
→ A macro processor is a program that copies a stream of text from one place to another, making a systematic set of replacements as it does so.
→ Macro processors are often embedded in other programs, such as assemblers and compilers. Sometimes they are standalone programs that can be used to process any kind of text.
Question 209
Which activities is not included in the first pass of two pass assembler ?
A
build the symbol table
B
construct the Intermediate code
C
separate mnemonic opcode and operand field.
D
none of these
       Compiler-Design       Assembler       UGC NET CS 2005 Dec-Paper-2
Question 209 Explanation: 
Two Pass Assemblers:
Pass-1:
1. Assign addresses to all statements in the program
2. Save the values assigned to all labels for use in Pass2
3. Perform some processing of assembler directives
Pass-2:
1. Assemble instructions Generate data values defined by BYTE,WORD
2. Perform processing of assembler directives not done in Pass 1
3. Write the object program and the assembly listing
Question 210
Which of the statements related to Compilers is wrong ?
A
Lexical analysis is breaking the input into tokens
B
Syntax analysis is for parsing the phrase
C
Syntax analysis is for analyzing the semantic
D
None of these
       Compiler-Design       Compilers       UGC NET CS 2005 june-paper-2
Question 210 Explanation: 
TRUE: Lexical analysis is breaking the input into tokens
TRUE: Syntax analysis is for parsing the phrase
FALSE: Syntax analysis is for analyzing the semantic. For analysing semantics we are using semantic analysis but not syntax analysis
Question 211
The dynamic binding occurs during the :
A
Compile time
B
Run time
C
Linking time
D
Pre-processing time.
       Compiler-Design       Run-Time-Environment       UGC NET CS 2005 june-paper-2
Question 211 Explanation: 
The dynamic binding occurs during the run time. The method being called upon an object or the function being called with arguments is looked up by name at runtime.
Question 212
Symbol Table can be used for :
A
Checking type compatibility
B
Suppressing duplication of error message
C
Storage allocation
D
All of these
       Compiler-Design       Symbol-Table       UGC NET CS 2005 june-paper-2
Question 212 Explanation: 
A symbol table can be used for
1. To store the names of all entities in a structured form at one place.
2. To verify if a variable has been declared.
3. To implement type checking, by verifying assignments and expressions in the source code are semantically correct.
4. To determine the scope of a name (scope resolution).
Question 213
A compiler for a high level language that runs on one machine and produces code for a different machine is called :
A
Optimizing
B
One pass compiler
C
Cross compiler
D
Multipass compiler
       Compiler-Design       Compilers       UGC NET CS 2006 Dec-paper-2
Question 213 Explanation: 
→ Incremental compiler: The compiler which compiles only the changed lines from the source code and update the object code
→ Threaded code compiler: The compiler which simply replace a string by an appropriate binary code.
→ Cross compiler: The compiler used to compile a source code for different kinds platform.
**One pass assembler and two pass assemblers are available.
Question 214
The ‘K’ in LR(R) cannot be :
A
0
B
1
C
2
D
None of these
       Compiler-Design       Parsers       UGC NET CS 2006 Dec-paper-2
Question 214 Explanation: 
→ The name LR is often followed by a numeric qualifier, as in LR(1) or sometimes LR(k). To avoid backtracking or guessing, the LR parser is allowed to peek ahead at k lookahead input symbols before deciding how to parse earlier symbols.
→ Typically k is 1 and is not mentioned. The name LR is often preceded by other qualifiers, as in SLR and LALR. The LR(k) condition for a grammar was suggested by Knuth to stand for "translatable from left to right with bound k."
Question 215
Peer-hole optimization is a form of :
A
loop optimization
B
local optimization
C
constant folding
D
data flow analysis
       Compiler-Design       Code-Optimization       UGC NET CS 2006 Dec-paper-2
Question 215 Explanation: 
→ Peephole optimization is a kind of optimization performed over a very small set of instructions in a segment of generated code. The set is called a "peephole" or a "window". It works by recognizing sets of instructions that can be replaced by shorter or faster sets of instructions.
Common techniques:
Null sequences
Combine operations
Algebraic laws
Special case instructions
Address mode operations
Constant folding
Question 216
A permanent database of a general model of compiler is ____________ .
A
Identifier table
B
Page map table
C
Literal table
D
Terminal table
       Compiler-Design       Compilers       UGC NET CS 2006 Dec-paper-2
Question 216 Explanation: 
A permanent database of a general model of compiler is terminal table. A permanent database that has entry for each terminal symbols such as arithmetic operators, keywords, punctuation characters such as ‘;’, ‘,’etc Fields: Name of the symbol.
Question 217
Tasks done in parsing are :
A
Check the validity of a source string
B
Determine the syntactic structure of a source string
C
Both (A) and (B)
D
None of these
       Compiler-Design       Parsers        UGC NET CS 2006 June-Paper-2
Question 217 Explanation: 
Tasks done in parsing are check the validity of a source string and determine the syntactic structure of a source string.
Question 218
YACC builds up __________ parsing table.
A
LALR
B
LR
C
SLR
D
LLR
       Compiler-Design       Parsers       UGC NET CS 2006 June-Paper-2
Question 218 Explanation: 
Yacc (Yet Another Compiler-Compiler):
It is a Look Ahead Left-to-Right (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus–Naur Form (BNF).
**YACC builds up LALR parsing table.
Question 219
The action of passing the source program into the proper syntactic class is known as :
A
Syntax analysis
B
Lexical analysis
C
Interpretation analysis
D
Uniform symbol generation
       Compiler-Design       Parsers       UGC NET CS 2006 June-Paper-2
Question 219 Explanation: 
Lexical analysis is the first phase of a compiler. It takes the modified source code from language preprocessors that are written in the form of sentences. The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.
Question 220
The dynamic binding occurs during the :
A
Compile time
B
Run time
C
Linking time
D
Pre - processing time
       Compiler-Design       Run-Time-Environment       UGC NET CS 2006 June-Paper-2
Question 220 Explanation: 
The dynamic binding occurs during the run time. The method being called upon an object or the function being called with arguments is looked up by name at runtime.
Question 221
Shift-Reduce parsers perform the following :
A
Shift step that advances in the input stream by K(K > 1) symbols and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
B
Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
C
Shift step that advances in the input stream by K(K = 2) symbols and Reduce step that applies a completed grammar rule to form a single tree.
D
Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree.
       Compiler-Design       Parsers       UGC NET CS 2014 Dec-Paper-2
Question 221 Explanation: 
Shift-Reduce parsers perform shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
Question 222
Which of the following is true ?
A
Canonical LR parser is LR (1) parser with single look ahead terminal
B
All LR(K) parsers with K > 1 can be transformed into LR(1) parsers.
C
Both (A) and (B)
D
None of the above
       Compiler-Design       Parsers       UGC NET CS 2014 Dec-Paper-2
Question 222 Explanation: 
TRUE: Canonical LR parser is LR (1) parser with single look ahead terminal
TRUE: All LR(K) parsers with K > 1 can be transformed into LR(1) parsers.
Question 223
In a two-pass assembler, symbol table is
A
Generated in first pass
B
Generated in second pass
C
Not generated at all
D
Generated and used only in second pass
       Compiler-Design       Symbol-table       UGC NET CS 2014 Dec-Paper-2
Question 223 Explanation: 
→ In a two-pass assembler, symbol table is generated in first pass.
→ The first pass of the assembler reads and processes the assembly program one line at a time. In processing a single line of the assembly program the assembler can make addition(s) to the symbol table, add a (possibly partial) SML instruction to the Simpletron's memory.
→ The purpose of the second pass is to complete the partial instructions written in the first pass.
Question 224
Debugger is a program that
A
allows to examine and modify the contents of registers
B
does not allow execution of a segment of program
C
allows to set breakpoints, execute a segment of program and display contents of register
D
All of the above
       Compiler-Design       Debugger       UGC NET CS 2014 Dec-Paper-2
Question 224 Explanation: 
Debugger is a program that allows to set breakpoints, execute a segment of program and display contents of register.
Question 225
A grammar G is LL(1) if and only if the following conditions hold for two distinct productions A → α | β
  1. First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the grammar.
  2. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow (A) = φ if λ ∈ First (β)
A
I and II
B
I and III
C
II and III
D
I, II and III
       Compiler-Design       Parsers       UGC NET CS 2014 June-paper-2
Question 225 Explanation: 
A grammar G is LL(1) if and only if the following conditions hold for two distinct productions:
A → α | β
1. First (α) and First (β) must be disjoint if none of α and β contains NULL move.
2. At most one of the strings α or β can drive NULL move i.e. α → NULL(since First (α) and First (β) are disjoint). In this case, First (β) and Follow(A) must be disjoint.
Hence the answer is option(D).
Question 226
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar ?
A
Removing left recursion alone
B
Removing the grammar alone
C
Removing left recursion and factoring the grammar
D
None of the above
       Compiler-Design       Parsers       UGC NET CS 2014 June-paper-2
Question 226 Explanation: 
→ Left recursion removing (or) factoring the given grammar are not sufficient to convert an arbitrary CFG to an LL(1) grammar.
→ To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 227
A shift reduce parser suffers from
A
shift reduce conflict only
B
reduce reduce conflict only
C
both shift reduce conflict and reduce reduce conflict
D
shift handle and reduce handle conflicts
       Compiler-Design       Parsers       UGC NET CS 2014 June-paper-2
Question 227 Explanation: 
→ A shift-reduce parser scans and parses the input text in one forward pass over the text, without backing up. (That forward direction is generally left-to-right within a line, and top-to-bottom for multi-line inputs.) The parser builds up the parse tree incrementally, bottom up, and left to right, without guessing or backtracking.
A shift-reduce parser works by doing some combination of Shift steps and Reduce steps, hence the name.
→ A Shift step advances in the input stream by one symbol. That shifted symbol becomes a new single-node parse tree.
→ A Reduce step applies a completed grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol.
*** A shift reduce parser suffers from both shift reduce conflict and reduce reduce conflict.
Question 228
The grammar S ⟶ (S) | SS | ∈ is ​ not​ suitable for predictive parsing because the grammar is
A
An Operator Grammar
B
Right Recursive
C
Left Recursive
D
Ambiguous
       Compiler-Design       Parsers       UGC NET CS 2018-DEC Paper-2
Question 228 Explanation: 
The grammar is ambiguous, as to derive string ()()() more than one parse tree exists.
Question 229
Consider the following Grammar G :
S ➝ A | B
A➝ a | c
B➝ b | c
Where {S,A,B} is the set of non-terminals, {a,b,c} is the set of terminals.
Which of the following statement(s) is/are correct ?
S​ 1​ : LR(1) can parse all strings that are generated using grammar G.
S​ 2​ : LL(1) can parse all strings that are generated using grammar G.
A
Both S​ 1​ and S​ 2
B
Only S​ 2
C
Neither S​ 1​ nor S​ 2
D
Only S​ 1
       Compiler-Design       Parsers       UGC NET CS 2018-DEC Paper-2
Question 229 Explanation: 
For generating string “c” we have two different parse trees.

Since the grammar is Ambiguous so the strings generated by the grammar G can’t be parsed by LR(1) or LL(1) parser.
Question 230
Consider the following two Grammars :
G1 : S → SbS|a
G2 : S → aB|ab, A→GAB|a, B→ABb|b
Which of the following option is correct ?
A
Only G1 is ambiguous
B
Only G2 is ambiguous
C
Both G1 and G2 are ambiguous
D
Both G1 and G2 are not ambiguous
       Compiler-Design       Ambiguous-and-Unambiguous-Grammar       UGC NET CS 2018 JUNE Paper-2
Question 230 Explanation: 
A grammar is said to be ambiguous if we get two different parse trees using either Leftmost derivation only or Rightmost derivation only.
To generate string “ababa” using G1 grammar the two different parse tree possible are:
Question 231
A bottom-up parser generates :
A
Leftmost derivation in reverse
B
Right-most derivation in reverse
C
Left-most derivation
D
Right-most derivation
       Compiler-Design       Parsers       UGC NET CS 2018 JUNE Paper-2
Question 231 Explanation: 
A bottom-up parser uses Right-most derivation in reverse order to decide “What to Reduce”.
Question 232
In compiler design ‘reducing the strength’ refers to
A
reducing the range of values of input variables.
B
code optimization using cheaper machine instructions.
C
reducing efficiency of program.
D
None of the above
       Compiler-Design       Compilers       UGC NET CS 2012 Dec-Paper-2
Question 232 Explanation: 
In compiler design ‘reducing the strength’ refers to code optimization using cheaper machine instructions.
Example:
Dividing by 2→ Use right shift by 2.
Multiplication by 2→ Use left shift by 2.
Question 233
Given the following expressions of a grammar
E → E * F / F + E / F
F → F – F / id
Which of the following is true ?
A
* has higher precedence than +
B
– has higher precedence than *
C
+ and – have same precedence
D
+ has higher precedence than *
       Compiler-Design       Grammars       UGC NET CS 2012 Dec-Paper-2
Question 233 Explanation: 
The operator which is in low level that can have high preference.
Order of precedence is *, +, -.
Here * and + have equal preference, '-' can have higher precedence than + and *.
Question 234
Which of the following is true while converting CFG to LL(I) grammar ?
A
Remove left recursion alone
B
Factoring grammar alone
C
Both of the above
D
None of the above
       Compiler-Design       Parsers       UGC NET CS 2012 Dec-Paper-2
Question 234 Explanation: 
→ A grammar could be LL(1) if and only if it is unambiguous and is not left recursive and left factoring grammar.
→ Since for converting a grammar to LL(1) 3 conditions mentioned above are required.
→ Unambiguous grammar is not mentioned in options. So option (D) is the correct.
Question 235
Which of the following is the most powerful parsing method ?
A
LL(I)
B
Canonical LR
C
SLR
D
LALR
       Compiler-Design       Parsers       UGC NET CS 2012 Dec-Paper-2
Question 235 Explanation: 
Canonical LR is most powerful.
LR > LALR > SLR.
But real time compilers using LALR only
Question 236
Given the following statements :
S1: SLR uses follow information to guide reductions. In case of LR and LALR parsers, the lookaheads are associated with the items and they make use of the left context available to the parser.
S2: LR grammar is a larger subclass of context free grammar as compared to that SLR and LALR grammars.
Which of the following is true ?
A
S1 is not correct and S2 is not correct.
B
S1 is not correct and S2 is correct.
C
S1 is correct and S2 is not correct.
D
S1 is correct and S2 is correct.
       Compiler-Design       Parsers       UGC NET CS 2013 Dec-paper-2
Question 237
Which of the following derivations does a top-down parser use while parsing an input string? The input is scanned from left to right.
A
Leftmost derivation
B
Leftmost derivation traced out in reverse
C
Rightmost derivation traced out in reverse
D
Rightmost derivation
       Compiler-Design       Parsers       UGC NET CS 2013 Dec-paper-2
Question 237 Explanation: 
→ Top down parsers using leftmost derivation and the input is scanned from left to right.
→ Bottom up parsers using rightmost derivation in reverse.
Question 238
The scheme of which interpreter translates the source program is known as
A
Paragraph by paragraph
B
Instruction by instruction
C
Line by line
D
None of the above
       Compiler-Design       Interpreter       UGC NET CS 2011 June-Paper-2
Question 238 Explanation: 
→ Compiler translates the entire source program into once. So, it is faster than interpreter.
→ Interpreter translates the source program into line by line. So, it is slower than compiler.
Question 239
Portable program means
A
Program with wheels
B
Independent from its authors
C
Independent of platform
D
None of the above
       Compiler-Design       Compilers       UGC NET CS 2011 June-Paper-2
Question 239 Explanation: 
Portable program means independent of platform. We can run same program in any operating system like windows,linux,unix,etc..,
Question 240
Which of the following permanent database that has an entry for each terminal symbol ?
A
Literal table
B
Identifier table
C
Terminal table
D
Source table
       Compiler-Design       Symbol-Table       UGC NET CS 2011 June-Paper-2
Question 240 Explanation: 
Terminal table is permanent database that has an entry for each terminal symbol.
Question 241
In which way(s) a macro processor for assembly language can be implemented ?
A
Independent two-pass processor
B
Independent one-pass processor
C
Expand macro calls and substitute arguments
D
All of the above
       Compiler-Design       Assembler       UGC NET CS 2011 June-Paper-2
Question 241 Explanation: 
Different ways a macro processor for assembly language can be implemented.
1. Independent two-pass processor
2. Independent one-pass processor
3. Expand macro calls and substitute arguments
Question 242
Given the production rules of a grammar G1 as
S1 → AB | aaB
A → a | Aa
B → b
and the production rules of a grammar G2 as
S2 → aS2bS2 | bS2aS2 | λ
Which of the following is correct statement ?
A
G1 is ambiguous and G2 is not ambiguous.
B
G1 is ambiguous and G2 is ambiguous.
C
G1 is not ambiguous and G2 is ambiguous.
D
G1 is not ambiguous and G2 is not ambiguous.
       Compiler-Design       Ambiguous-and-Unambiguous-Grammar       UGC NET CS 2013 June-paper-2
Question 242 Explanation: 

Question 243
Given a grammar : S1 → Sc, S → SA | A, A → aSb | ab, there is a rightmost derivation
     S1 ⇒ Sc ⇒ SAC ⇒ SaSbc
Thus, SaSbc is a right sentential form, and its handle is
A
SaS
B
bc
C
Sbc
D
aSb
       Compiler-Design       Handles       UGC NET CS 2013 June-paper-2
Question 243 Explanation: 
A “handle” of a string is a substring that matches the RHS of a production and whose reduction to the non-terminal (on the LHS of the production) represents one step along the reverse of a rightmost derivation toward reducing to the start symbol.
And in above question aSb is a handle because it's reduction to the LHS of production A → aSb represents one step along the reverse of a rightmost derivation toward reducing to the start symbol.
Question 244
The equivalent production rules corresponding to the production rules S → Sα1 | Sα2 | β1 | β2 is
A
S → β1 | β2, A → α1A | α2A | λ
B
S → β1| β2 | β1A | β2A, A → α1A | α2A
C
S → β1 | β2, A → α1A | α2A
D
S → β1 | β2 | β1A | β2A, A → α1A | α2A | λ
       Compiler-Design       Grammars       UGC NET CS 2013 June-paper-2
Question 244 Explanation: 
Given grammar can generate { β1, β2 , β2α2, , β2 α1, , β1α2, , β1α1 , β1 α1α2..................}
Option A can generate only {β1, β2} so it is not a correct option.
Option B is not correct because it have no terminating point strings containing {α1 , α2}
Option C is not correct because it can generate only {β1, β2}
Option D is correct answer because it can generate all the strings generated by given grammar.
Question 245
Which is the correct statement(s) for Non Recursive predictive parser ?
S1 : First(α) = { t | α⇒ *tβ for some string β}⇒ *tβ
S2 : Follow(X) = { a | S⇒ *αXaβ for some strings α and β}
A
Both statements S1 and S2 are incorrect.
B
S1 is incorrect and S2 is correct.
C
S1 is correct and S2 is incorrect.
D
Both statements S1 and S2 are correct.
       Compiler-Design       Parsers       UGC NET CS 2013 June-paper-2
Question 245 Explanation: 
Statement-1: → See the symbol (⇒ *) means after some step , here * represent an arbitrary number of steps. * is not part of terminal.
→ So if alpha after some step has t as first symbol (terminal) in some sentential form , then first(alpha) must be {t}
Statement-2:
α→∗tβ Here First(α) = {*} .
S→∗αXaβ
Follow(X) = {a}
So Statement S2 is correct.
Question 246
‘Macro’ in an assembly level program is _______.
A
sub program
B
a complete program
C
a hardware portion
D
relative coding
       Compiler-Design       Macros       UGC NET CS 2010 Dec-Paper-2
Question 246 Explanation: 
→ A macro is a sequence of instructions, assigned by a name and could be used anywhere in the program.
→ A macro is an extension to the basic ASSEMBLER language. They provide a means for generating a commonly used sequence of assembler instructions/statements.
→ The sequence of instructions/statements will be coded ONE time within the macro definition. Whenever the sequence is needed within a program, the macro will be "called".
Question 247
Grammar of the programming is checked at ________ phase of compiler
A
semantic analysis
B
code generation
C
syntax analysis
D
code optimization
       Compiler-Design       Phases-of-Compilers       UGC NET CS 2010 Dec-Paper-2
Question 247 Explanation: 
→ Grammar of the programming is checked at syntax phase of compiler.
→ logical errors will checked in semantic analysis.
→ Code optimization and code generation is not related to checking errors. It is reducing statement or performing optimization.
Question 248
Macro-processors are ______.
A
Hardware
B
Compiler
C
Registers
D
None of the above
       Compiler-Design       Macros       UGC NET CS 2010 Dec-Paper-2
Question 248 Explanation: 
→ A macro processor is a program that copies a stream of text from one place to another, making a systematic set of replacements as it does so.
→ Macro processors are often embedded in other programs, such as assemblers and compilers.
Question 249
Which of the following expression is represented by the parse tree ?

A
(A + B) * C
B
A + * BC
C
A + B * C
D
A * C + B
       Compiler-Design       Parsers       UGC NET CS 2010 June-Paper-2
Question 249 Explanation: 
Parse tree is always following inorder traversal. It visit left,root and right.

Question 250
Consider the following left associative operators in decreasing order of precedence :
– subtraction (highest precedence)
* multiplication
$ exponentiation (lowest precedence)
What is the result of the following expression ?
3 – 2 * 4 $ | * 2**3
A
– 61
B
64
C
512
D
4096
       Compiler-Design       Compiler-Design       UGC NET CS 2010 June-Paper-2
Question 250 Explanation: 
Actually they are given in wrong order.
But according to given question, we are giving precedence is
(((3 – 2) *) 4 $ | * (2**3))
Step-1: 3-2=1
Step-2: 1*4=4
Step-3: 2*3=6
Step-4: 46=4096
Note: When we are assuming ** is single(*) and there is no |* are useless symbols.
Question 251
Which of the following is used for grouping of characters into tokens(in a computer)?
A
A parser
B
Code optimizer
C
Code generator
D
Scanner
       Compiler-Design       Phases-of-Compilers       UGC NET CS 2010 June-Paper-2
Question 251 Explanation: 
Lexical analysis(or Scanner) used for grouping of characters into tokens.
Question 252
A compiler that runs on one machine and produces code for a different machine is called:
A
Cross compilation
B
One pass compilation
C
Two pass compilation
D
None of the above
       Compiler-Design       Compilers       UGC NET CS 2009-June-Paper-2
Question 252 Explanation: 
Cross compiler: The compiler used to compile a source code for different kinds platform.
Note: We have an one and two pass assemblers but not compilers.
Question 253
In an absolute loading scheme which loader function is accomplished by assembler ?
A
re-allocation
B
allocation
C
linking
D
loading
       Compiler-Design       Compilers       UGC NET CS 2009 Dec-Paper-2
Question 253 Explanation: 
→ Loader loads the executable code into memory, program and data stack are created, register gets initialized.
→ Re-allocation is an absolute loading scheme which loader function is accomplished by assembler
Question 254
Which of the following grammar is LR (1) ?
A
A → a A b, A → b A b, A → a , A →b
B
A → a A a, A → a A b, A → c
C
A → A + A, A → a
D
Both (A) and (B)
       Compiler-Design       Parsers       UGC NET CS 2009 Dec-Paper-2
Question 254 Explanation: 
LR(1)is default name of CLR(1). Hence LR(1) and CLR(1) is same.
Option(A):
Since here we are having no Reduce-reduce OR shift-reduce conflict so it is CLR(1).




Question 255
A shift-reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of the grammar.
S → x x W [ print “1”]
S → y [print “2”]
W → S2 [print “3”]
what is the translation of “x x x x y z z” ?
A
1 1 2 3 1
B
1 1 2 3 3
C
2 3 1 3 1
D
2 3 3 2 1
       Compiler-Design       Syntax-Directed-Translation       UGC NET CS 2009 Dec-Paper-2
Question 255 Explanation: 

⇒ 23131
SR is bottom up parser.
Note : Instead of Sz they given S2 and what operation will perform they are not mentioned
Question 256
Synthesized attribute can be easily simulated by a
A
LL grammar
B
Ambiguous grammar
C
LR grammar
D
None of the above
       Compiler-Design       Synthesized-Attribute       UGC NET CS 2009 Dec-Paper-2
Question 256 Explanation: 
→ Synthesized Attributes are such attributes that depend only on the attribute values of children nodes. It can be easily simulated by LR grammar
→ Inherited Attributes are such attributes that depend on parent and/or siblings attributes.
Question 257
An assembly program contains :
A
imperative and declarative statements
B
imperative statements and assembler directives
C
imperative and declarative statements as well as assembler directives
D
declarative statements and assembler directives
       Compiler-Design       Assembler       UGC NET CS 2008 Dec-Paper-2
Question 257 Explanation: 
An assembly program contains imperative and declarative statements as well as assembler directives.
Question 258
Which of the following are Assembler Directives ?
(i) EQU
(ii) ORIGIN
(iii) START
(iv) END
A
(ii), (iii) and (iv)
B
(i), (iii) and (iv)
C
(iii) and (iv)
D
(i), (ii), (iii) and (iv)
       Compiler-Design       Assembler       UGC NET CS 2008 Dec-Paper-2
Question 258 Explanation: 
Basic Assembly directives:
1. EQU→ Equate
2. ORIGIN→ Origin
3. START→ Start
4. END→ End
Question 259
Assembler program is :
A
dependent on the operating system
B
dependent on the compiler
C
dependent on the hardware
D
independent of the hardware
       Compiler-Design       Assembler       UGC NET CS 2008-june-Paper-2
Question 259 Explanation: 
→ Assembler program is dependent on the hardware.
→ An assembler program creates object code by translating combinations of mnemonics and syntax for operations and addressing modes into their numerical equivalents.
Question 260
At the end of parsing,
A
tokens are identified.
B
set of instructions are identified.
C
the syntactic groups are identified.
D
machine instructions are identified
       Compiler-Design       Parsers       UGC NET CS 2008-june-Paper-2
Question 260 Explanation: 
At end of parsing whether it is syntactically correct or not is identified So at end of parsing
1. tokens are identified
2. whether the given code is syntactically correct or not is identified.
Question 261
Dead-code elimination in machine code optimization refers to :
A
removal of all labels.
B
removal of values that never get used.
C
removal of function which are not involved.
D
removal of a module after its use.
       Compiler-Design       Code-Optimization       UGC NET CS 2008-june-Paper-2
Question 261 Explanation: 
→ Dead code elimination in machine code optimization refers to removal of values that never get used.
→ Dead code includes code that can never be executed (unreachable code), and code that only affects dead variables (written to, but never read again), that is, irrelevant to the program.
Question 262
A parse tree is an annotated parse tree if :
A
it shows attribute values at each node.
B
there are no inherited attributes.
C
it has synthesized nodes as terminal nodes.
D
every non-terminal nodes is an inherited attribute.
       Compiler-Design       Parsers       UGC NET CS 2008-june-Paper-2
Question 262 Explanation: 
A parse tree is an annotated parse tree if it shows attribute values at each node.
Features:
1. High level specification
2. Hides implementation details
3. Explicit order of evaluation is not specified
Question 263
In a two pass compiler, during the first pass :
A
user defined address symbols are correlated with their binary equivalent
B
the syntax of the statement is checked and mistakes, if any, are listed
C
object program is generated
D
semantic of the source program is elucidated.
       Compiler-Design       Compilers       UGC NET CS 2007-Dec-Paper-2
Question 263 Explanation: 
→ In a two pass compiler, during the first pass, user defined address symbols are correlated with their binary equivalent.
→ During first pass in two pass compilers contain lexical,syntactic,semantic and intermediate code generator are in front end.
→ During second pass in two pass compilers contain code optimization and code generator are in back end.
Question 264
A single instruction in an assembly language program contains :
A
one micro operation
B
one macro operation
C
one instruction to be completed in a single pulse
D
one machine code instruction
       Compiler-Design       Compilers       UGC NET CS 2007-Dec-Paper-2
Question 264 Explanation: 
A single instruction in an assembly language program contains one macro operation.
Question 265
Absolute loader demands that the programmer needs to know the :
A
start address of the available main memory
B
total size of the program
C
actual address of the data location
D
absolute values of the operands used
       Compiler-Design       Linker-Loader       UGC NET CS 2007-Dec-Paper-2
Question 265 Explanation: 
Absolute loader demands that the programmer needs to know the start address of the available main memory.
Question 266
Top-down parsers are predictive parsers, because :
A
next tokens are predicted.
B
length of the parse tree is predicted beforehand
C
lowest node in the parse tree is predicted.
D
next lower level of the parse tree is predicted.
       Compiler-Design       Parsers       UGC NET CS 2007-Dec-Paper-2
Question 266 Explanation: 
→ Top-down parsers are predictive parsers, because next tokens are predicted.
→ Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string.
→ The predictive parser does not suffer from backtracking.
→ Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree.
Question 267
In the context of compiler design, “reduction in strength” refers to :
A
code optimization obtained by the use of cheaper machine instructions
B
reduction in accuracy of the output
C
reduction in the range of values of input variables
D
reduction in efficiency of the program
       Compiler-Design       Code-Optimization       UGC NET CS 2007-Dec-Paper-2
Question 267 Explanation: 
In the context of compiler design, “reduction in strength” refers to code optimization obtained by the use of cheaper machine instructions.
Question 268
The parsing technique that avoids backtracking is :
A
Top - down parsing
B
Recursive - descent parsing
C
Predicative
D
Syntax tree
       Compiler-Design       Parsers       UGC NET CS 2007 June-Paper-2
Question 268 Explanation: 
→ Top-down parsers are predictive parsers, because next tokens are predicted.
→ Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string.
→ The predictive parser does not suffer from backtracking.
→ Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree.
Question 269
A Top down Parser generates :
A
Rightmost derivation.
B
Rightmost derivation, in reverse.
C
Leftmost derivation.
D
Leftmost derivation in reverse.
       Compiler-Design       Parsers       UGC NET CS 2007 June-Paper-2
Question 269 Explanation: 
→ A Top down Parser generates leftmost derivation.
→ A bottom up parser generates rightmost derivation, in reverse.
Question 270
Symbol table can be used for :
A
Checking type compatibility
B
Suppressing duplication of error message
C
Storage allocation
D
All of these above
       Compiler-Design       Symbol-Table       UGC NET CS 2007 June-Paper-2
Question 270 Explanation: 
Symbol table can be used for
1. Checking type compatibility
2. Suppressing duplication of error message
3. Storage allocation
Question 271
Heap allocation is required for languages that
A
use dynamic scope rules
B
support dynamic data structures
C
support recursion
D
support recursion and dynamic data structures
       Compiler-Design       Run-Time-Environment       UGC NET CS 2017 Nov- paper-3
Question 271 Explanation: 
→ Heap allocation is required for languages that support dynamic data structures. The heap is managed via calls to new, delete, callac, realloc, malloc, free, etc.
→ Stack allocation is required for local variables. Space on the stack is reserved for local variables when they are declared.
Question 272
Replacing the expression 4*2.14 by 8.56 is known as
A
Constant folding
B
Induction variable
C
Strength reduction
D
Code reduction
       Compiler-Design       Code-Optimization       UGC NET June-2019 CS Paper-2
Question 272 Explanation: 
Take variable i=4*2.14
We are simply folding the value into 8.56 because to avoid multiplication costly operation.
Question 273
Which data structure is used by the compiler for managing variables and their attributes?
A
Binary tree
B
link list
C
Symbol table
D
Parse table
       Compiler-Design       Symbol-Table       UGC NET June-2019 CS Paper-2
Question 273 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 contains information about an identifier such as its character string (or lexeme) , its type,its position in storage, and any other relevant information.
Question 274
Shift-reduce parser consists of
(a) input buffer
(b) stack
(c) parse table
choose the correct option from those given below:
A
(a) and (b) only
B
(a) and (c) only
C
(c) only
D
(a), (b) and (c)
       Compiler-Design       Parsers       UGC NET June-2019 CS Paper-2
Question 274 Explanation: 
Shift-reduce parser consists of
(a) input buffer
(b) stack
(c) parse table
Question 275
On translating the expression given below into quadruple representation, how many operations are required? (i*j)+(e+f)*(a*b+c)
A
5
B
6
C
3
D
7
       Compiler-Design       Intermediate-code-generator       UGC NET June-2019 CS Paper-2
Question 275 Explanation: 
T1 = (i*j)
T2=(e+f)
T3=(a*b)
T4= (T3+c)
T5=T2 * T4
T6=T1 + T5
Hence 6 operations are required.
Question 276

Which of the following is/are FALSE?

I) Operator precedence parser works on ambiguous grammar

II) Top-down parser works on left recursive, unambiguous and deterministic grammar

III) LL(I) is a non-recursive descent parser

IV) CLR(I) is the most powerful parser
A
Only II
B
I, II, III and IV
C
ll and IV
D
I, III and IV
       Compiler-Design       Parsers       CIL Part - B
Question 276 Explanation: 
I) TRUE: Operator precedence parser works on ambiguous grammar
II) FALSE: Top-down parser works on left recursive, unambiguous and deterministic grammar
Ill) TRUE: LL(I) is a non-recursive descent parser
IV) TRUE: CLR(I) is the most powerful parser
Question 277
What will be the "First" and "Follow" of E and F for the following grammar?
E->TE’
E’->+TE’/ε
T->FT’
T’->*FT’/ε
F->id/(E)
A
First(E)={id, (,ε},follow(E)={ε,) }, First(F)={id,),$}, Follow(F)={*,$,(}
B
First(E)={id, ( },follow(E)={$,) }, First(F)={id,(}, Follow(F)={*,$,),+}
C
First(E)={id, (,ε},follow(E)={ε,) }, First(F)={id,)}, Follow(F)={*,$,(,+ }
D
First(E)={id, )},follow(E)={$,) }, First(F)={id,(,$}, Follow(F)={*,$,),+}
       Compiler-Design       Parsers       CIL Part - B
Question 277 Explanation: 

First (∊) = { id, ( }

Follow (∊) = { $, ) }

First (F) = { id, ( }

Follow (F) = { *, +, $, ) }
Question 278

Which of the following statements is TRUE for the grammar given below?

S->(L)/a

L->L.S/S
A
The grammar can be parsed by LR(0) parser only
B
The grammar can be parsed by LR(0) and SLR(1) parsers
C
The grammar can be parsed by LL(1) parser only
D
The grammar can be parsed by LL(1) and LR(0) parsers
       Compiler-Design       Parsers       CIL Part - B
Question 278 Explanation: 
→ The given grammar can be parsed by LR(0) grammar because there is no S-R conflict or R-R conflict. → Since the grammar can be parsed by LR(0) parser hence we can say SLR(1) parser can also parse it.
Question 279

The number of tokens in the following

“C” language statement is:

printf(“The number of tokens are %d”, &tcount);
A
8
B
9
C
10
D
11
       Compiler-Design       Parsers       CIL Part - B
Question 279 Explanation: 

Question 280
The number of tokens in the following C code segment is
switch(inputvalue)
{
case 1;b=c*d; break;
Default : b = b++ ; break;
}
A
27
B
29
C
26
D
24
       Compiler-Design       Lexical-Analyzer       ISRO CS 2020
Question 280 Explanation: 
Switch1(2 inputvalue3 )4
{5
Case6 17 :8 b9 =10 c11 *12 d13 ;14 break15 ;16
Default17 :18 b19 =20 b21 ++22 ;23 break24 ;25
}26
Question 281
In a two-pass assembler, resolution of subroutine calls and inclusion of labels in the symbol table is done during
A
Second pass
B
First pass and second pass respectively
C
Second pass and first pass respectively
D
First pass
       Compiler-Design       Assembler       ISRO CS 2020
Question 281 Explanation: 
In two pass assembler, each pass scans the program, the first pass generates the symbol table and the second pass generates the machine code.
So, inclusion of labels in symbol table is done in first pass and resolution of subroutine is done in second pass.
Question 282
Which of the following is a type of out-of-order execution, with the reordering done by a compiler
A
Loop unrolling
B
Dead code elimination
C
Strength reduction
D
Software pipelining
       Compiler-Design       Code-Optimization       ISRO CS 2020
Question 282 Explanation: 
In computer engineering, out-of-order execution, is a technique used in most high-performance microprocessors to make use of cycles that would otherwise be wasted by a certain type of costly delay. Most modern CPU designs include support for out of order execution.
This technique is similar to loop unrolling concept in code optimization.
Question 283
A given grammar is called ambiguous if
A
two or more production have the same non-terminal on the left hand side
B
A derivation tree has more than one associated sentence
C
there is a sentence with more than one derivation tree corresponding to it
D
Brackets are not present in the grammar
       Compiler-Design       Ambiguous-and-Unambiguous-Grammar       ISRO CS 2020
Question 283 Explanation: 
A grammar is ambiguous if any string generated by the grammar has more than one parse tree (derivation tree)
Question 284
Which one indicate a technique of building cross compilers?
A
Beta cross
B
Canadian cross
C
Mexican cross
D
X-cross
       Compiler-Design       Compilers       ISRO CS 2020
Question 284 Explanation: 
Canadian cross is a famous technique of building cross compilers.
Question 285
Given the grammar
s→ T*S | T
T → U + T | U
U → a | b
Which of the following statements is wrong?
A
Grammar is not ambiguous
B
Priority of + over * is ensured
C
Right to left evaluation of * and + happens
D
None of these
       Compiler-Design       Parsers       ISRO CS 2020
Question 285 Explanation: 
The grammar is unambiguous as it can be parsed by CLR(1) parser.
S-> T*S , since S has right recursion so * is right associative
T-> U+T , since T has right recursion so + is right associative
Hence right to left evaluation of * and + will happen.
+ is having more precedence than * so the precedence of + and * is clearly defined.
Question 286
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 -- > iCtSS1|a S1 -- > eS | • C -- > b The grammar is NOT LL(1) because:
A
It is left recursive
B
It is right recursive
C
It is ambiguous
D
It is not context-free
       Compiler-Design       Parsers       APPSC-2016-DL-CS
Question 286 Explanation: 
Question 287
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. If the empty strinp, $indicates end of input, and, | separates alternate right hand sides of productions S->aAbB|bAaB|ε A->S B->S
a b $
S E1 E2 S->ε
A A->S A->S error
B B->S B->S E3
 
A
FIST(A)=(a,b,$) FIRST(A)={A,B} FIRST(B) = {a,b,ε} FOLLOW(A)={A,B} FOLLOW(A) = {A,b} FOLLOW(B)={A,b,$) FOLLOW(B) = {$} FIRST(B) = {a,b,ε} FOLLOW(A) = {A,b}
B
FOLLOW(B) = {$}
C
FIRST(A) = {a,b,ε} = FIRST(B)
D
FIRST(A) = {A,B} = FIRST(B) FOLLOW(A)={a,b} FOLLOW(A)={a,b}
       Compiler-Design       Parsers       APPSC-2016-DL-CS
Question 288
Which of the following combinations of statements is TRUE? I. There exist parsing algorithms for some programming languages whose complexities are less than O(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.
A
I and II
B
I and IV
C
III and IV
D
I, III and IV
       Compiler-Design       Run-Time-Environment