CS/IT Gate Subject



Compiler Design GATE CS and IT previous year questions with answer


Ques 11 Gate 2016 Set-1

Consider the following code segment.

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


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


a is the correct answer.


Ques 12 Gate 2016 Set-1

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



Ques 13 Gate 2015 Set-3

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 G.

A

Only S1

B

Only S2

C

Both S1 and S2

D

Neither S1 and S2



Ques 14 Gate 2015 Set-3

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



Ques 15 Gate 2015 Set-2

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 to 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 in AST and CFG corresponds to at most one statement in the input program.



Ques 16 GATE 2015 SET-2

Match the following:

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



Ques 17 GATE 2015 SET-2

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



Ques 18 Gate 2015 Set-1

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



Ques 19 GATE 2015 SET-1

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



Ques 20 GATE 2015 SET-1

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 _______.