CompilerDesign
Question 1 
S → Aa A → BD B → b  ε D → d  εLet a, b, d, and $ be indexed as follows:
Compute the FOLLOW set of the nonterminal 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)
30  
31  
10  
21 
{Follow(B) = Follow(A) when D is epsilon}
Follow(B) = {d} Union {a} = {a,d}
Hence Answer is : 31
Question 2 
Leftmost in reverse  
Rightmost in reverse  
Leftmost  
Rightmost 
Question 3 
S' → S S → 〈L〉  id L → L,S  S
Let I_{0} = CLOSURE ({[S' → ·S]}). The number of items in the set GOTO (I_{0} , 〈 ) is: _____.
4  
5  
6  
7 
Hence, the set GOTO (I0 , 〈 ) has 5 items.
Question 4 
Consider the following grammar and the semantic actions to support the inheriteatd type declaration attributes. Let X_{1}, X_{2}, X_{3}, X_{4}, X_{5} and X_{6} be the placeholders for the nonterminals D, T, L or L_{1} in the following table:
Which one of the following are the appropriate choices for X_{1}, X_{2}, X_{3} and X_{4}?
X_{1} = L, X_{2} = L, X_{3} = L_{1}, X_{4} = T  
X_{1} = L, X_{2} = T, X_{3} = L_{1}, X_{4} = L  
X_{1} = T, X_{2} = L, X_{3} = L_{1}, X_{4} = T  
X_{1} = T, X_{2} = L, X_{3} = T, X_{4} = L_{1} 
L → L_{1}, id {X_{3}.type = X_{4}.type } , this production has L and L_{1}, hence X_{3} and X_{4} cannot be T.
So option 1, 3 and 4 cannot be correct.
Hence, 2 is correct answer.
Question 5 
S>aSB d
B>b
The number of reduction steps taken by a bottomup parser while accepting the string aaadbbb is _______.
7 
7 reductions total.
Question 6 
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 runtime 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?
II only  
I only
 
I and III only
 
None of I, II and III

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 nit syntax error.
Question 7 
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?
Only Rule 2 is Lattributed.  
Neither Rule 1 nor Rule 2 is Lattributed.
 
Both Rule 1 and Rule 2 are Lattributed.
 
Only Rule 1 is Lattributed.

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 8 
Contextfree grammar can be used to specify both lexical and syntax rules.
 
Type checking is done before parsing.  
Highlevel language programs can be translated to different Intermediate Representations.
 
Arguments to a function can be passed using the program stack.

Question 9 
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?
$ has higher precedence and is left associative; # is right associative
 
# has higher precedence and is left associative; $ is right associative
 
$ has higher precedence and is left associative; # is left associative  
# has higher precedence and is right associative; $ is left associative

Question 10 
A lexical analyzer uses the following patterns to recognize three tokens T_{1}, T_{2}, and T_{3} over the alphabet {a,b,c}.

T_{1}: a?(b∣c)*a
T_{2}: b?(a∣c)*b
T_{3}: c?(b∣a)*c
Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.
If the string bbaacabc is processes by the analyzer, which one of the following is the sequence of tokens it outputs?
T_{1}T_{2}T_{3}
 
T_{1}T_{1}T_{3}  
T_{2}T_{1}T_{3}  
T_{3}T_{3} 
T_{1} : (b+c)*a + a(b+c)*a
T_{2} : (a+c)*b + b(a+c)*b
T_{3} : (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 T_{3}.
After prefix we left with “abc” which is again generated by T_{3} (as longest possible prefix).
So, answer is T_{3}T_{3}.
Question 11 
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?
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 = ab
p = u*v
and two assignments of the variable q
q = p*c
q = p+q
So we use two variables p_{1}, p_{2} for specifying distinct assignments of p and q_{1}, q_{2} for each assignment of q.
Static Single Assignment form(SSA) of the given code segment is:
p_{1} = ab
q_{1} = p_{1} * c
p_{2} = u * v
q_{2} = p_{2} + q_{1}
Note:
As per options, given in GATE 2017 answer is B.
p_{3} = a  b
q_{4} = p_{3} * c
p_{4} = u * v
q_{5} = p_{4} + q_{4}
Question 12 
{R}  
{w}  
{w, y}  
{w, $} 
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 13 
Consider the following grammar:
stmt → if expr then expr else expr; stmt  ȯ expr → term relop term  term term → id  number id → a  b  c number → [09]
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 e_{1} then e_{2} else e_{3}
has 2 control flow paths, e_{1} → e_{2} and e_{1} → e_{3}.
1024  
1025  
1026  
1027 
if
if
:
:
:
(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 = 2^{10} = 1024
Question 14 
Consider the expression (a1)*(((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 ___________.
2  
3  
4  
5 
Question 15 
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:
P→(ii), Q→(iii), R→(iv), S→(i)  
P→(ii), Q→(i), R→(iii), S→(iv)  
P→(iii), Q→(iv), R→(i), S→(ii)  
P→(i), Q→(iv), R→(ii), S→(iii) 
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 16 
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.
I only  
II only  
III only  
II and III only 
The power in increasing order is:
LR(0) < SLR < LALR < CLR
Hence only I is true.
Question 17 
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?
S→Sα  β
The equivalent production (after removing left recursion) is
S→βS_{1}
S_{1}→αS_{1}  ϵ
Hence after removing left recursion from: E→ ET  T, here α = T and β = T
E→TE_{1}
E_{1}→ TE_{1}  ϵ
After removing left recursion from: T→T+F  F, here α=+F and β=F
T→FT_{1}
T_{1}→ +FT_{1}  ϵ
Replace E_{1} = X and T_{1} = Y
We have,
E→TX
X→TX  ϵ
T→FY
Y→+FY  ϵ
F→(E) id
Question 18 
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 ________.
10  
11  
12  
13 
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 19 
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 __________.
9  
10  
11  
12 
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 20 
Consider the following Syntax Directed Translation Scheme (SDTS), with nonterminals {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 bottomup parser, for the input aab is:
1 3 2  
2 2 3  
2 3 1  
syntax error 
Question 21 
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
P ↔ i, Q ↔ ii, R ↔ iv, S ↔ iii  
P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv  
P ↔ ii, Q ↔ iii, R ↔ i, S ↔ iv  
P ↔ iv, Q ↔ i, R ↔ ii, S ↔ iii 
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 22 
Which one of the following grammars is free from left recursion?
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 23 
Which one of the following is True at any valid state in shiftreduce parsing?
Viable prefixes appear only at the bottom of the stack and not inside
 
Viable prefixes appear only at the top of the stack and not inside  
The stack contains only a set of viable prefixes  
The stack never contains viable prefixes

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 24 
8  
9  
10  
11 
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 reuse the same temporary variable several times.
Question 25 
a_{n2}+a_{n1}+2^{n2}
 
a_{n2}+2a_{n1}+2^{n2}  
2a_{n2}+a_{n1}+2^{n2}  
2a_{n2}+2a_{n1}+2^{n2} 
So, a_{1} = 0
For string of length 2,
a_{2} = 1
Similarly, a_{3} = 3
a_{4} = 8
Only (A) will satisfy the above values.
Question 26 
1. There exists a statement Sj that uses x 2. There is a path from Si to Sj in the flow graph corresponding to the program 3. The path has no intervening assignment to x including at Si and Sj
p, s, u  
r, s, u  
r, u  
q, v 
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 28.
Finally r, u is the correct one.
Question 27 
In both AST and CFG, let node, N_{2} be the successor of node N_{1}. In the input program, the code corresponding to N_{2} is present after the code corresponding in N_{1}.
 
For any input program, neither AST nor CFG will contain a cycle
 
The maximum number of successors of a node in an AST and a CFG depends on the input program
 
Each node is AST and CFG corresponds to at most one statement in the input program

Option (B) is false as CFG can contain cycle
Option (D) is false as a single node can contain block of statements.
Question 28 
P2,Q3,R1,S4  
P2,Q1,R4,S3  
P2,Q4,R1,S3  
P2,Q3,R4,S1 
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 29 
5 and 7  
6 and 7  
5 and 5  
7 and 8 
Question 30 
SLR, LALR
 
Canonical LR, LALR
 
SLR, canonical LR
 
LALR, canonical LR 
Question 31 
S → F ⎪ H F → p ⎪ c H → d ⎪ cWhere S, F and H are nonterminal 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
Only S1  
Only S2  
Both S1 and S2  
Neither S1 nor S2 
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 RR conflict is present. So, not LR(1).
Hence, Option (D) is the correct answer.
Question 32 
A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.  
Available expression analysis can be used for common subexpression elimination.  
Live variable analysis can be used for dead code elimination.  
x=4*5⇒x=20 is an example of common subexpression elimination. 
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 33 
S > L. > R Q > R.On input symbol < the set has
a shiftreduce conflict and a reducereduce conflict.  
a shiftreduce conflict but not a reducereduce conflict.  
a reducereduce conflict but not a shiftreduce conflict.  
neither a shiftreduce nor a reducereduce conflict. 
But if it would have asked about “>” then it will be a SR conflict.
Question 34 
Neither L nor is recursively enumerable (r.e.).  
One of L and is r.e. but not recursive; the other is not r.e.  
Both L and are r.e. but not recursive.  
Both L and are recursive. 
Question 35 
I) 0*1(1+00*1)* II) 0*1*1+11*0*1 III) (0+1)*1
I and II only  
I and III only  
II and III only  
I, II, and III 
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 36 
S > T * P T > U  T * U P > Q + P  Q Q > Id U > IdWhich one of the following is TRUE?
+ is left associative, while ∗ is right associative  
+ is right associative, while ∗ is left associative  
Both + and ∗ are right associative  
Both + and ∗ are left associative 
P ⟶ Q + P, here P is right recursive, so + is right associative.
Question 37 
Dynamic memory allocation  
Type checking  
Symbol table management  
Inline expansion 
Question 38 
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?
X is declared as “int X[32][32][8]”.  
X is declared as “int X[4][1024][32]”.  
X is declared as “char X[4][32][8]”.  
X is declared as “char X[32][16][2]”. 
Arr[0][1][2], this 3D 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 3D 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[t_{4}]
X [ i ][ j ][ k ] = X [ t_{4} ] // by substituting in reverse
=X [ t_{3} + t_{2}]
=X [ t_{1} + t_{0} + k*4]
=X [ t_{0} + t_{1} + k*4] // t_{0} and t_{1} 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 ] [ 8]. So it is right option.
Question 39 
6  
7  
8  
9 
Question 40 
make parsing and semantic analysis simpler.  
improve error recovery and error reporting.  
increase the chances of reusing the machineindependent code optimizer in other compilers.  
improve the register allocation. 
Question 41 
1 and 2 only  
2 and 3 only  
3 and 4 only  
1 and 3 only 
Question 42 
6  
7  
8  
9 
Question 43 
n/2  
n1  
2n1  
2^{n} 
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 bottomup parsing where strings are parsed finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving right most derivations only.
We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon and unitproduction (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 44 
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?
 Cannot be merged since look aheads are different.
 Can be merged but will result in SR conflict.
 Can be merged but will result in RR conflict.
 Cannot be merged since goto on c will lead to two different sets.
1 only  
2 only  
1 and 4 only  
1, 2, 3 and 4 
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 NonTerminals symbols, not on terminal symbols, and c is a terminal symbol.
Hence all statements are false.
Question 45 
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 :
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 46 
FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b,$}  
FIRST(A) = {a,b,$} FIRST(B) = {a,b,ε} FOLLOW(A) = {a,b} FOLLOW(B) = {$}  
FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = ∅  
FIRST(A) = {a,b} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b} 
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 A → S
So FOLLOW (S) = {$, a, b}= FOLLOW(B)
Question 47 
E1: S → aAbB,A → S E2: S → bAaB,B→S E3: B → S  
E1: S → aAbB,S→ ε E2: S → bAaB,S → ε E3: S → ε  
E1: S → aAbB,S → ε E2: S → bAaB,S→ε E3: B → S  
E1: A → S,S →ε E2: B → S,S → ε E3: B →S 
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 48 
Finite state automata  
Deterministic pushdown automata  
NonDeterministic pushdown automata  
Turing machine 
Question 49 
parsing of the program  
the code generation
 
the lexical analysis of the program  
dataflow analysis 
Question 50 
⇒ 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
Question 51 
2  
9  
5  
3 
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 52 
Abstract syntax tree  
Symbol table  
Semantic stack  
Parse Table

Question 53 
Those that support recursion  
Those that use dynamic scoping
 
Those that allow dynamic data structures  
Those that use global variables

Question 54 
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+fAssuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
2  
3  
4  
6 
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 55 
LL(1) but not LR(1)  
LR(1) but not LR(1)  
Both LL(1) and LR(1)
 
Neither LL(1) nor LR(1) 
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 56 
P4, Q1, R2, S3
 
P3, Q1, R4, S2
 
P3, Q4, R1, S2  
P2, Q1, R4, S3

Question 57 
I and II
 
I and IV
 
III and IV
 
I, III and IV 
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 58 
It is the position in a sentential form where the next shift or reduce operation will occur.
 
It is nonterminal whose production will be used for reduction in the next step.  
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.
 
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.

Question 59 
They enhance the portability of the compiler to other target processors
 
Program analysis is more accurate on intermediate code than on machine code
 
The information from dataflow analysis cannot otherwise be used for optimization  
The information from the front end cannot otherwise be used for optimization

Question 60 
II and V only  
I, III and IV only
 
I, II and V only
 
II, III and V only 
V. PL’s which permits a function to return a function as its result cannot be implemented with a stackbased storage allocation scheme for activation records.
II & V are True.
Question 61 
the SLR(1) parser for G has SR conflicts
 
the LR(1) parser for G has SR conflicts
 
the LR(0) parser for G has SR conflicts  
the LALR(1) parser for G has reducereduce conflicts

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 reducereduce may occur.
Hence An LALR(1) parser for a grammar G can have shiftreduce (SR) conflicts if and only if the LR(1) parser for G has SR conflicts.
Question 62 
Recursive descent parser.
 
Operator precedence parser.  
An LR(k) parser.
 
An LALR(k) parser.

Question 63 
S > iCtSS_{1}a S_{1} > eSε C > bThe grammar is NOT LL(1) because:
it is left recursive
 
it is right recursive  
it is ambiguous
 
it is not contextfree 
This grammar has two parse tree for string “ibt ibt aea”.
Question 64 
P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammarWhich of the following is TRUE?
Both P and Q are true
 
P is true and Q is false
 
P is false and Q is true
 
Both P and Q are false

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 acceptor as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
Question 65 
S > aB S > bA B > b A > a B > bS A > aS B > aBB A > bAAWhich of the following strings is generated by the grammar?
aaaabb
 
aabbbb
 
aabbab  
abbbba 
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 66 
S > aB S > bA B > b A > a B > bS A > aS B > aBB A > bAAWhich of the following strings is generated by the grammar?
1  
2  
3  
4 
Question 67 
L (D) ⊂ L (G)  
L (D) ⊃ L (G)  
L (D) = L (G)  
L (D) is empty 
For example, by converting NFA to DFA language will not be changed.
Question 68 
S > S * E S > E E > F + E E > F F > idConsider the following LR(0) items corresponding to the grammar above.
(i) S > S * .E (ii) E > F. + E (iii) E > F + .EGiven the items above, which two of them will appear in the same set in the canonical setsofitems for the grammar?
(i) and (ii)
 
(ii) and (iii)  
(i) and (iii)  
None of the above

Question 69 
2 * 3 + 4
 
2 * +3 4
 
2 3 * 4 +
 
2 3 4+*

Now perform post order evaluation, you will get output as,
2 3 4 + *
Question 70 
for (i = 0, i<n; i++) { for (j=0; j<n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } } 
The code contains loop invariant computation
 
There is scope of common subexpression elimination in this code  
There is scope of strength reduction in this code
 
There is scope of dead code elimination in this code

→ 5*i can be moved out of inner loop. So can be i%2, here loopinvarient 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 71 
S → FR R → S  ε F → idIn the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $] respectively.
{S → FR} and {R → ε}
 
{S → FR} and { }  
{S → FR} and {R → *S}  
{F → id} and {R → ε} 
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 72 
subroutine swap(ix,iy) it = ix L1 : ix = iy L2 : iy = it end ia = 3 ib = 8 call swap (ia, 1b+5) print *, ia, ib endS1: The compiler will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the cell swap S2: On execution the code will generate a runtime error on line L1 S3: On execution the code will generate a runtime error on line L2 S4: The program will print 13 and 8 S5: The program will print 13 and 2 Exactly the following set of statement(s) is correct:
S1 is false and S2 is false
 
S1 is false and S2 is true
 
S1 is true and S2 is false
 
S1 is true and S2 is true

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 73 
ambiguous
 
leftrecursive  
rightrecursive  
an operatorgrammar

It have A → AA has left recursion.
Question 74 
E → number E.val = number. val  E '+' E E(1).val = E(2).val + E(3).val  E '×' E E(1).val = E(2).val × E(3).valThe 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?
It detects recursion and eliminates recursion
 
It detects reducereduce conflict, and resolves
 
It detects shiftreduce conflict, and resolves the conflict in favor of a shift over a reduce action
 
It detects shiftreduce conflict, and resolves the conflict in favor of a reduce over a shift action

Question 75 
E → number E.val = number. val  E '+' E E(1).val = E(2).val + E(3).val  E '×' E E(1).val = E(2).val × E(3).valAssume 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?
Equal precedence and left associativity; expression is evaluated to 7
 
Equal precedence and right associativity; expression is evaluated to 9
 
Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7
 
Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9

Hence, the answer is 9 and right associative.
Question 76 
int main ( ) { /* Line 1 */ int I, N; /* Line 2 */ fro (I = 0, I < N, I++); /* Line 3 */ } 
No compilation error
 
Only a lexical error
 
Only syntactic errors
 
Both lexical and syntactic errors

Question 77 
E → E + n  E × n  nFor a sentence n + n × n, the handles in the rightsentential form of the reduction are
n, E + n and E + n × n
 
n, E + n and E + E × n
 
n, n + n and n + n × n
 
n, E + n and E × n

→ E + n * n {Applying E → E + n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
Question 78 
S → (S)  aLet 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
n_{1} < n_{2} < n_{3}
 
n_{1} = n_{3} < n_{2}
 
n_{1} = n_{2} = n_{3}
 
n_{1} ≥ n_{3} ≥ n_{2} 
→ 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)
n_{1} = (n_{3}) < (n_{2})
Question 79 
(i) only
 
(i) and (iii) only
 
(ii) and (iii) only
 
(iii) and (iv) only

i) On RHS it contains two adjacent nonterminals.
ii) Have nullable values.
Question 80 
Edit time  
Compile time
 
Link time
 
Load time 
Question 81 
E_{1} should be evaluated first
 
E_{2} should be evaluated first
 
Evaluation of E_{1} and E_{2} should necessarily be interleaved
 
Order to evaluation of E_{1} and E_{2} is of no consequence

Question 82 
200  
180  
160  
40 
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 83 
{wN_{a}(w) > 3N_{b}(w)}
 
{wN_{b}(w) > 3N_{a}(w)}  
{wN_{a}(w) = 3k, k Î {0, 1, 2, ...}}
 
{wN_{b}(w) = 3k, k Î {0, 1, 2, ...}}

S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
N_{a}(w) > 3N_{b}(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
N_{b}(w) > 3N_{b}(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
N_{b}(w) = 3k
2 = 3k(✖️)
S = aA
S→aA
S→abA
S→abaB
S→abaa
n(a)=3
n(a)=3
→ Answer: Option C(✔️)
Question 84 
Removing left recursion alone
 
Factoring the grammar alone  
Removing left recursion and factoring the grammar  
None of the above 
Question 85 
n_{1} is necessarily less than n_{2}  
n_{1} is necessarily equal to n_{2}
 
n_{1} is necessarily greater than n_{2}
 
None of the above

Question 86 
always be evaluated
 
be evaluated only if the definition is Lattributed
 
be evaluated only if the definition has synthesized attributes
 
never be evaluated

LAttributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parsetree.
Question 87 
In statically typed languages, each variable in a program has a fixed type  
In untyped languages, values do not have any types  
In dynamically typed languages, variables have no types  
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

Question 88 
S → i E t S S'  a S' → e S  ε E → bIn the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are
{S'→e S} and {S'→ε}
 
{S'→e S} and { }  
{S'→ε} and {S'→ε}  
{S'→e S, S'→ε} and {S'→ε}

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 89 
S → C C C → c C  dThe grammar is
LL(1)
 
SLR(1) but not LL(1)
 
LALR(1) but not SLR(1)
 
LR(1) but not LALR(1)

Hence, it is LL(1).
Question 90 
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
9 + 5 + 2
 
9 5 + 2 +  
9 5 2 + +
 
+ + 9 5 2 
Now traverse the tree and whatever comes first to print, just print it.
Answer will be 9 5 + 2 +.
Question 91 
S → id : = E {gen (id.place = E.place;);} E → E1 + E2 {t = newtemp ( ); gen (t = El.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 3address code sequence generated by this definition is
X = Y + Z
 
t_{1} = Y + Z; X = t_{1}  
t_{1}= Y; t_{2} = t_{1} + Z; X = t_{2}  
t_{1} = Y; t_{2} = Z; t_{3} = t_{1} + t_{2}; X = t_{3}

Question 92 
Smaller sizes of executable files
 
Lesser overall page fault rate in the system
 
Faster program startup
 
Existing programs need not be relinked to take advantage of newer versions of libraries 
Question 94 
3  
26  
10  
21 
(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 
Leftmost derivation  
Leftmost derivation traced out in reverse  
Rightmost derivation  
Rightmost derivation traced out in reverse 
BottomUp parser  Reverse of rightmost derivation
Question 96 
* has higher precedence than +  
 has higher precedence than *  
+ and – have same precedence  
+ has higher precedence than * 
Order of precedence is *, +, .
Here * and + have equal preference, '' can have higher precedence than + and *.
Question 98 
LL (1)  
Canonical LR  
SLR  
LALR 
LR > LALR > SLR
Question 99 
3  
4  
5  
None of the above 
10 → 2
I → 3
= → 4
1.25 → 5
Question 100 
Assembler  
Linker  
Loader  
Compiler 
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 
SLR parser is more powerful than LALR  
LALR parser is more powerful than Canonical LR parser  
Canonical LR parser is more powerful than LALR parser  
The parsers SLR, Canonical CR, and LALR have the same power 
Canonical LR parser is more powerful than LALR parser.
Question 102 
lexical analysis  
syntax analysis  
syntax directed translation  
code optimization 
Question 103 
‘⊕’ is left associative while ‘*’ is right associative  
Both ‘⊕’ and ‘*’ is left associative  
‘⊕’ is right associative while ‘*’ is left associative  
None of the above 
⊕ 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 one of the following is true?
A compiler using static memory allocation can be written for L  
A compiler cannot be written for L; an interpreter must be used  
A compiler using dynamic memory allocation can be written for L  
None of the above 
Question 105 
test a condition during the execution of the expanded program  
to expand certain model statements depending upon the value of a condition during the execution of the expanded program  
to implement recursion  
to expand certain model statements depending upon the value of a condition during the process of macro expansion 
Question 106 
that support recursion  
that support dynamic data structures  
that use dynamic scope rules  
None of the above 
Question 107 
1, 2, 1, 2  
2, 1, 2, 1  
2, 1, 1, 2  
1, 2, 2, 2 
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 
(ii) only  
(i) only  
both (i) and (ii)  
None of the above 
Question 109 
Object code  
Relocation bits  
Names and locations of all external symbols defined in the object module
 
Absolute addresses of internal symbols

To link to external symbols it must know the location of external symbols.
Question 110 
23131  
11233  
11231  
33211 
⇒ 23131
Note SR is bottom up parser.
Question 111 
it makes implementation of lexical analysis and syntax analysis easier  
syntaxdirected translations can be written for intermediate code generation  
it enhances the portability of the front end of the compiler  
it is not possible to generate code for real machines directly from high level language programs

Question 112 
(i)  (d), (ii)  (a), (iii)  (b), (iv)  (c) 
Yacc (Yet Another Compiler Compiler) is a computer program for the UNIXoperating 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 
The program leads to compile time error  
The program leads to run time error  
The program outputs 5.2  
The program produces error relating to nil pointer dereferencing  
None of the above 
Question 114 
text editor  
assembler  
linker  
loader
 
none of the above 
Question 115 
The go to part of both tables may be different.  
The shift entries are identical in both the tables.  
The reduce entries in the tables may be different.  
The error entries in the tables may be different.  
B, C and D. 
Reduce entry and error entry may be different due to conflicts.
Question 116 
Assembly  
Parsing  
Relocation  
Symbol resolution 
Question 117 
An unambiguous grammar has same leftmost and rightmost derivation  
An LL(1) parser is a topdown parser  
LALR is more powerful than SLR  
An ambiguous grammar can never be LR(k) for any k 
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 119 
Theory Explanation is given below. 
Question 121 
3 , 4 
So, in total 3 registers are required and 6 memory operations in total to fetch all operands.
Question 122 
properly nested. 
Question 123 
matches the parameters of the macrodefinition with locations of the parameters of the macro call  
matches external names of one program with their location in other programs  
matches the parameters of subroutine definition with the location of parameters of subroutine call  
acts as link between text editor and the user  
acts as a link between compiler and user program. 
1) external symbol resolution
2) relocation
Question 124 
Recursive descent parsing cannot be used for grammar with left recursion.  
The intermediate form the representing expressions which is best suited for code optimization is the post fix form.
 
A programming language not supporting either recursion or pointer type does not need the support of dynamic memory allocation.  
Although C does not support call by name parameter passing, the effect can be correctly simulated in C.
 
No feature of Pascal violates strong typing in Pascal.  
A and D 
(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 125 
(a)  (q), (b)  (r), (c)  (s), (d)  (p) 
Activation record  Recursion
Repeat until  Nondeterministic loop
Coercion  Type conversion
Question 126 
(a)  (s), (b)  (p), (c)  (q), (d)  (r) 
Code optimization  DAG
Code generation  Syntax tree
Abelian groups  Push down automaton
Question 127 
ReduceReduce, ShiftReduce 
Question 128 
The code generator.  
The code optimiser.  
The lexical analyser.  
The syntax analyser. 
Question 129 
Bottomup parser.  
Topdown parser.  
Back tracking parser.  
None of the above. 
Question 130 
Somewhat slower compilation  
A program that is easier to understand  
An incorrect program  
None of the above 