CD |Gate-2017| Compiler Design
1. 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? [GATE – 2017]
a. p1 = a-b
q1 = p1 * c
p1 = u*v
q1 = p1 + q1
b. p3 = a-b
q4 = p3 * c
p4 = u*v
q5 = p4 + q4
c. p1 = a-b
q1 = p2 * c
p3 = u*v
q2 = p4 + q3
d. p1 = a-b
q1 = p * c
p2 = u*v
q2 = p + q
Answer : b)
2. Consider the following grammar:
P → xQRS
Q → yz|z
R →w| ε
S → y
What is FOLLOW(Q)? [GATE – 2017]
a. {R}
b. {w}
c. {w, y}
d. {w, $}
Answer : c)
3. 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 → [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. [GATE – 2017]
a. 1024
b. 1025
c. 1026
d. 1027
Answer : a)
CD |Gate-2017|
4. 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 ___________. [GATE – 2017]
a. 2
b. 3
c. 4
d. 5
Answer : a)
5. Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: [GATE – 2017]
| (P) Syntax tree | (i) code generator |
| (Q) Character stream | (ii) syntax analyzer |
| (R) Intermediate representation | (iii) semantic analyzer |
| (S) Token Stream | (iv) lexial analyzer |
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)
Answer : c)
6. Which of the following statements about parser is/are CORRECT? [GATE – 2017]
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
Answer : a)