CSI 311 SAMPLE EXAM QUESTIONS (Language Theory)
--------------------------------------------------------------------------
NOTE: Question 4 is on parameter passing protocols. If we have not
covered this material prior to Exam 1, it will not be on the exam.
In that case, however, it may be covered on Exam 2.
--------------------------------------------------------------------------
1. Consider the following BNF grammar, G1:
< XOR > ::= < XOR > + < XOR > | < id >
< id > ::= A | B | C | ... | Z
[a] Give TWO parse trees for U + V + W + X
[b] This grammar is ambiguous because there is more than
one [parse tree/cannonical derivation] for the sentence
of part [a]; how many distinct cannonical derivations
do, in fact, exist for that sentence?
[c] Give one non-cannonical derivation of the sentence of
part [a]. At each step, indicate the non-terminal to
which a rule is being applied by underlining it.
*** This topic will NOT be covered on Exam I.
2. You are given the following attribute grammer:
<exp> ::= <id> ^t
^t | <id> ^t1 * <exp> ^t2 combinetypes under: !t1 !t2 ^t
<id> ::= I ^"int" | J ^"int" | ... | N ^"int"
^t | A ^"real" | B ^"real" | ... | H ^"real"
| O ^"dbp" | P ^"dbp" | ... | Z ^"dbp"
Evaluation rule:
combinetypes under !arg1 !arg2 ^result ::=
if arg1 = "dbp" then result <-"dbp" else
if arg1 = "int" then result <-arg2 else
if arg2 = "dbp" then result <-"dbp" else result <-"real"
Note: we use `<-' for assignment in the evaluation rule.
we use `!' for inherited attributes (in place of down arrow)
we use `^' for synthesized attributes (in place of up arrow)
Draw a valid parse tree for "B * N * W" showing inherited
and synthesized attributes. (Valid means attribute values
are all computed and satisfy any required conditions.)
3. For this question, the axioms for composition and
assignment shown below may be helpful.
{P} S1 {Q}, {Q} S2 {R}
______________________________ {P[E/V]} V := E {P}
{P} S1 ; S2 {R}
Consider the following program:
{ } [a] Using the above axioms, show that if
S1: z := 0; the assertion A at the bottom of the loop
{ } holds, then A holds at the top of the loop.
S2: i := 0; I.e., {A} S3 ; S4 {A}. (Show your work;
{ } fill in the resulting answers between the
while i <= N do begin "{}" brackets at the relevant places in
{ } the algorithm. Ignore the loop test)
S3: i := i + 1;
{ }
S4: z := z + (2*i)
A == { z = i(i+1) }
end;
[b] If done successfully, part [a] shows that,
with respect to the above program fragment, A is
__________________
[c] We know that if A holds just before entering the loop,
i.e., just after S2, then A will hold at the bottom
(and top) of the loop throughout loop execution, and
therefore at the end of the algorithm. Derive an
assertion which, if true just prior to S1, will guaran-
tee that A is true just after S2. Furthermore, the
assertion required prior to S1 should always hold, just
by inspection. Again, show your work and fill in the
answers between the "{}" brackets at the relevant
places in the algorithm.
The answer is shown as assertions placed before statements S1 and S2.
Material on parameter passing mechanisms, if covered at all, will not be
covered in enough detail nor thoroughly enough to be included on Exam I.
*** This topic will NOT be covered on Exam I.
4. Consider the program below written in pseudocode,
in which parameter passing mechanisms are
explicitly specified:
program
I, J, K : integer;
R : array[1..20] of integer;
procedure PTEST( ________________ A, B, C : integer )
begin
I := C; C := B;
output( A, B, C, I );
end;
begin
I := 1; J := 2; K := 1;
while K <= 20 do
begin
R[K] := K; K := K+1;
end;
PTEST( I, R[I], R[J] );
end;
In the table below, the column on the left indicates a pos-
sible mode for the three parameters of procedure Q: one mode
for each of the four rows. The other four columns are for
the output values of A, B, C, and I, respectively. Fill in
the table to correctly account for the various parameter-
modes assumed.
A B C I
___________________________________________________
value ___ ___ ___ ___
reference ___ ___ ___ ___
val-result ___ ___ ___ ___
name ___ ___ ___ ___
**************************************************************************
ANSWERS TO QUESTIONS
__________________________
**************************************************************************
1. [a]
<XOR> <XOR>
<XOR> + <XOR> <XOR> + <XOR>
<XOR> + <XOR> <XOR> + <XOR> <XOR> + <XOR> <id>
<id> <id> <id> <id> <XOR> + <XOR> <id> X
U V W X <id> <id> W
U V
[b]
FIVE:
(U+(V+(W+X)))
(U+((V+W)+X))
((U+V)+(W+X))
((U+(V+W)+X))
(((U+V)+W)+X)
[c]
<XOR>
-----
<XOR> + <XOR>
-----
<XOR> + <XOR> + <XOR>
-----
<XOR> + <id> + <XOR>
-----
<XOR> + V + <XOR>
-----
<XOR> + V + <XOR> + <XOR>
-----
<XOR> + V + <id> + <XOR>
-----
<XOR> + V + W + <XOR>
-----
<id> + V + W + <XOR>
-----
U + V + W + <XOR>
-----
U + V + W + <id>
-----
U + V + W + X
2.
<exp>^"dbp"
<id>^"real" * <exp>^"dbp" combinetypes!"real" !"dbp" ^"dbp"
B^"real" <id>^"int" * <exp>^"dbp" combinetypes!"int" !"dbp" ^"dbp"
N^"int" <id>^"dbp"
W^"dbp"
3.
[a] and [c]: (The assertions are derived bottom-up here)
---------
{ 0 = 0 } (trivially true)
S1: z := 0;
{ z = 0(1) so z = 0
S2: i := 0;
{ z = i(i+1) } == A
while i <= N do begin
{ z = (i+1)^2 - (i+1) simplifies to z = i^2 + i, so z = i(i+1) = A }
S3: i := i + 1;
A' == { z + 2i = i(i+1) which simplifies to z = i^2 - i }
S4: z := z + (2*i)
A == { z = i(i+1) }
[b] A LOOP INVARIANT (Note that the loop test is not crucial here)
4.
A B C I
___________________________________________________
value 1 1 1 2
reference 2 1 1 2
val-result 1 1 1 2
name 2 2 2 2