Name___________________________________________________________
PART-A.
Multiple-Choice
(72 points)
Answer 18 questions in this
PART.
Choose the one BEST answer
in each question you answer by writing down a BIG Letter (in
Capital).
For the first four
questions, consider the following Boolean expression and the corresponding
sequence
of quadruples that can be
generated:
((A+B*C) AND (NOT D) AND E)
10:
=,
#1,`
0,
T4
11:
*,
B,
C,
T5
12:
+,
A,
T5,
T6
13:
BB,
T6,
X1,
X2
14:
BB,
D,
X3,
X4
15:
BB,
E,
X5,
X6
16:
=,
#0,
0,
T4
17: BEQ,
T4,
#0,
??
You
must assume the usual operator precedence:
That is, NOT, AND, and OR in that order.
1. The
values of X1 and X2 are, respectively,
a. 14 and
16.
b. 16 and
14.
c. 17 and
14.
d.
None.
2. The
values of X3 and X4 are, respectively,
a. 17 and
15
b. 16 and
15.
c.
16 and 15
d.
None.
3. Which
two values are the same?
a. X4 and
X6
b. X2
and X4
c.
Both.
d.
Neither
4. Which
two values are the same?
a.
X1 and X3
b.
X1 and X4
c.
X4 and X6.
d.
None.
Next three questions are
about the following sequence of quadruples generated for a boolean
expression:
20:
=
#1
0
T4
21:
BB
A
22
24
22:
BB
B
24
23
23:
BB
C
25
24
24:
=
#0
0
T5
25:
BEQ T4
#0
???
5.
The boolean expression is
a.
A AND B AND C
b.
A AND (NOT B) AND C
c.
A AND B OR C
d.
None above.
6.
Which call(s) to Merge() was made during the generation of these
codes?
a.
Merge (-21,22)
b.
Merge (-21,-23)
c.
both.
d.
neither.
7.
Exactly before quad #24 was about to be generated, which Fillin() call
was made?
a.
Fillin (-21)
b.
Fillin (-23)
c.
Fillin ( 23)
d.
none above.
For the next four questions,
consider the following array declaration:
Integer AA[1:10, 1:20, 1:30]
Assume that the Row-major
sequence is used and that the first array element, AA[1,1,1], is stored at
location 10000 and that each array element occupies exactly one memory location
for the sake of simplicity.
8. The
modified first address of this array is
a. 10000 -
(1+30+600+6000)
b. 10000 + (1+30+600)
c.
Neither
9. The
VarPart (offset(AA(Z,Y,X))) is
a.
X+30*Y+600*Z
b. 6000*Z+600*Y+30*X
c.
Neither
10. Which array
element has a smaller VarPart of its offset when the Row-major
sequence
is used than when the Column-major sequence is
used?
a. AA
[10,10,1]
b. AA
[1,10,30]
c. Both.
d.
Neither
11. The difference in
memory locations between AA[M, L-2,K] and AA[M,L,K] where
L>1
a.
1200
b.
60
c.
30
d.
None above.
E.
Cannot tell
For the next four questions,
refer to the following CFG for generating Boolean
expressions:
Bool -> BE
BE
-> BE OR
BT | BE AND BT | BT
BT
-> BF | NOT BE
BF
-> id | ( BE )
12.
NOT A OR B
According to the grammar, above has to be unambiguously equivalent
to
a. (NOT
A) OR B
b. NOT
(A OR B)
c. Both.
d.
Neither.
13.
A OR B AND C
According to the grammar, above has to be unambiguously equivalent
to
a. (A OR B)
AND C
b. A OR (B AND
C)
c. Both.
d.
Neither.
14.
A AND B AND C
According to the grammar, above has to be unambiguously equivalent
to
a. (A AND B) AND
C
b. A AND (B AND C)
c. Both.
d.
Neither.
15.
BT -> NOT BT
Suppose that above rule replaced the following rule of this
grammar:
BT -> NOT BE
a. (NOT A AND B) is ambiguous in the original
grammar before this replacement.
b. (NOT A AND B) is
ambiguous in the new resulting grammar after this
replacement.
c. Both.
d.
Neither.
16.
void BE (int& Tlink, int& Flink)
As presented in class, above function
a. may resolve one or more
F-links by itself
b. may merge two or more
T-links by itself.
c. Both.
d.
Neither.
17.
void BF (int& Tlink, int& Flink)
As presented in class, above function
a. always sets both its
parameters by itself (rather than resolving) regardless of what is being
generated.
b. may set both its
parameters by way of a function call depending upon what is being
derived.
c. both.
d.
neither.
18. Evaluating
loop parameters just once before the loop body execution
a. is more flexible and more
efficient (in speed) than otherwise.
b. is safer and less
efficient (in speed) than otherwise.
c. Both.
d. Neither.
19. In a top-down
error recovery, when a stack symbol is popped at the point of an error
detection,
a.
zero or more tokens are
inserted before the current token.
b.
one or more tokens are
inserted after the current token.
c.
Both.
d.
Neither.
20. Which error
processing requires exactly “Parsing the entire program in the face of some
errors”?
a.
error repair
b.
error recovery
c.
error detection/report
d.
none
above.
21. As
presented in class, the semantic routine that actually generates by itself
quadruples for ‘+’ is
a.
E()
b.
T()
c.
Both
d.
Neither.
22.
*
A
B
T5
*
T5
C
T6
+
T6
D
T7
Which will generate above sequence of quadruples?
a.
A*B*C+D
b.
(A*B*C)+D
c.
(A*B)*C+D
d.
all above
e.
two above.
f.
none above.
23.
void T(int &
loc)
As presented in class, above function always generates
a.
at least one quadruple for
‘*’ by itself.
b.
at least one quadruple for
‘+’ by itself.
c.
Both.
d.
neither.
24. As
presented in class, the semantic routine that actually generates by itself
quadruples for ‘*’ is
a.
E()
b.
T()
c.
F()
d.
all above.
e.
two above.
PART-B.
Other Problems
(28 points)
Do two problems in this
PART.
A. Give a semantic routine to translate a variable of the following form: Var -> id | id [ Elist ]
1. In the above rule, only "Var" and "Elist" are the nonterminals.
2. Assume that you have available a routine,
E(int& LOC), that translates an expression and returns a
memory location to contain the value of the expression.
3. “Elist” represents a list of one or more numerical expressions
separated by a comma and each expression is a subscript of an array
element.
And, give quadruples to be generated by the above routine for:
A[I,J] = X * B[I,J]
B. Give a semantic routine to translate the following “WHILE” loop:
While E <> E do S
Note that this loop iterates exactly as long as the two given expressions are
not the same and that it may not iterate even once.
And, give quadruples to be generated for:
while A+B <> C*D do
begin C = C+1;
A = A+C;
Print A*C end
C. Complete the following C++ function that resolves a given link field
which is the first one of any number of links already merged/linked together.
Void Fillin (int field) // note that the given field may be negative