GATE CS : Compiler Design Champion Quiz 4 for GATE & PSU CS Exams

Question 1

Given the relations employee (name, salary, deptno), and department (deptno, deptname, address)
Which of the following queries cannot be expressed using the basic relation alalgebra operations (σ,π,×, ,∪,∩,−)?

Question 2

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

Question 3

Which of the following can be used in syntax analysis to verify the syntax of programs?

Question 4

Consider the following grammar G.
S

AB|d
A

aA|b
B

bB|c
The grammar G is

Question 5

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?

Question 6

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 A2
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

Question 7

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 of 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

Question 8

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 of 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

Question 9

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

Question 10

Consider the following SDT.
E

E+T {E.x=E.x

T.x}
E

T {E.x=T.x}
T

T*F {T.x=T.x-F.x}
T

F {T.x=F.x-1}
F

id {F.x=5}
If bottom up parsing uses S-attributed definition then what is the value of attribute evaluated at root E for an input string " id+id*id "?