Test 1 Compiler Design | Computer Science

The following program fragment is written in a programming language that allows global
variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {P(i + j);}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

The following program fragment is written in a programming language that allows global
variables and does not allow nested declarations of functions.
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {P(i + j);}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are

Consider the following translation scheme.
S$\rightarrow$ER
R$\rightarrow$E {print (''); R}$\epsilon$
E $\rightarrow$F + E {print ('+');} F
F$\rightarrow$ (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

Consider the following grammar.
S $\rightarrow$S * E
S $\rightarrow$E
E $\rightarrow$F + E
E $\rightarrow$F
F $\rightarrow$id
Consider the following LR (0) items corresponding to the grammar above.
(i) S $\rightarrow$ S *.E
(ii) E $\rightarrow$ F. + E
(iii) E $\rightarrow$ 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?

Consider the syntax directed definition shown below,
S $\rightarrow$ id : = E {gen (id.place = E.place;);}
E $\rightarrow$ E₁ + E₂ {t = newtemp( );
gen(t = E1.place + E2.place;);
E.place = t;}
E $\rightarrow$ 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

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

Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.

Class P {
  Class Q subclass of P {
    void f(int i) {
      void f(int i) {
        print(i);
        print(2 * i);
      }
    }
  }
}

Now consider the following program fragment:
Px = new Q()
Qy = new Q();
Pz = new Q();
x.f(1); ((P)y).f(1); z.f(1);
Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment
will be

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$\rightarrow$ a B S $\rightarrow$bA
B $\rightarrow$b A$\rightarrow$ a
B $\rightarrow$bS A $\rightarrow$aS
B $\rightarrow$aBB S$\rightarrow$ bAA

Which of the following strings is generated by the grammar?

Which of the following statements are TRUE?
I. There exist parsing algorithms for some programming languages whose complexities are less than $\theta$(n³).
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.

In a simplified computer the instructions are:
OP R_j , R_i - Performs R_j OP R_i and stores the result in register . R_i
OP m, R_i - Performs val i OP R_i and stores the result in R_i. val denotes the content of memory location m.
MOV m, R_i - Moves the content of memory location m to register R_i
MOV R_i , m - Moves the content of register R_i to memory location m.
The computer has only to registers, and OP is either ADD or SUB. Consider the following basic block:
t₁ = a + b
t₂ = c + d
t₃ = e - t₂
t₄ = t₁ - b
Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

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 ^{_{$\rightarrow$}} aB S ^{_{$\rightarrow$}} bA
B ^{_{$\rightarrow$}} b A ^{_{$\rightarrow$}} a
B ^{_{$\rightarrow$}} bS A ^{_{$\rightarrow$}} aS
B ^{_{$\rightarrow$}} aBB S ^{_{$\rightarrow$}} bAA

How many derivation trees are there?