Some sample questions from previous final examinations. Some of these are
from take-home examinations, and therefore much too long for an in-class
test, but they are an indication of what I hope you will have learned
in the course (i.e. might remember more than 24 hours after the final!).
Problem 1
---------
Consider the language of the alphabet { 0, 1}, which consists of strings
with the same number of 0'a and 1's.
a) Is the grammar for this language regular? Explain.
b) Sketch a parsing algorithm for this language (No need to find a grammar
for the language).
c) (Optional) write a grammar for this language.
Problem 2
---------
Suppose we want to implement parameter-passing by reference for arrays (you
may have done this in your project), and be able to write the usual (in
Ada syntax):
type t is array (integer range <>) of integer;
...
function sum (arg : t) return integer is
result : integer := 0;
begin
for J in arg'first .. arg'last loop
result := result + arg (J); -- line (A)
end loop;
return result;
end sum;
Somewhere else we call this function:
table : t (1..N) := ....
X : Integer;
...
X := sum (table); -- line (B)
a) Indicate what quadruples and what assembly (for your chosen target machine)
would be generated for line (A). You can assume that the bounds of the array
are stored at locations 0 and 1, so the data itself starts at offset 2 from
the array base.
b) What code (quadruples and assembly) needs to be generated for the
assignment at (B)?
Problem 3
---------
Consider the following procedure, that computes the primes numbers up
to some number N.
with text_io; use text_io;
procedure Sieve (N : integer) is
table : array (1..10000) of boolean;
begin
for I in table'range loop
table (I) := True;
end loop;
for I in 2 .. Integer (Sqrt (N)) loop
if table (I) then -- I is a prime
for J in 2 .. Table'Last loop
exit when I * J > Table'Last;
Table (I * J) := False; -- multiple of I
end loop;
end if;
end loop;
for I in 2 . Table'Last loop
if Table (I) then
put (I); put_line (" is a prime");
end if;
end loop;
end sieve;
a) Write the quadruples corresponding to this procedure. If your compiler
can process this example you can use it as a guide. Describe what needs to be
done for the function call to Sqrt.
b) Show the basic blocks of this procedure.
c) Show the flow graph for this procedure.
d) Identify the loop-invariant computations, if any, and move them out of
loops if possible.
e) are there induction variables present? If so, can their use be optimized?
Problem 4
---------
An expression E is said to be very busy at point P if on all paths from P
the expression E is evaluated before any of its operands is redefined. Note
that this definition means that E itself is not necessarily evaluated at P,
only that E is evaluated downstream on all possible paths from P. If an
expression is very busy at P, it may be advantageous to compute it once at
P, rather than at each downstream place where it is currently computed (this
optimization is called hoisting. For example, if the expression is evaluated
on two branches of an if-statement, it saves space to evaluate it once before
the conditional).
Give a data-flow algorithm to determine whether an expression is very busy at
at a point. As usual, assume that you have the program graph and its basic
blocks, functions Busy_in and Busy_out, and local functions Gen and Kill.
Define in a few words what each of these represent, and how they are computed.
Is this a forward or backwards algorithm, and does it use union or intersection?
Problem 5
---------
Some languages, such as Ada, support slices and slice assignment: it is
possible to retrieve and assign to a contiguous portion of a one-dimensional
array. The syntax is:
Target (low1 .. high1) = Source (low2 .. high2);
The lengths of the two slices must be equal. assuming that the bounds are
all variables, write the quadruples for such an assignment.
b) Slice assignment requires that the length of the source and the target of
the expression be equal. Given the assignment:
S1 (x .. y) := S2 (a .. b);
write down the quadruples and the assembly (for the machine of your choice)
that must be generated for this assignment. Assume that Constraint_Error must
be raised if the length of the slices on the left and right don't match.
Problem 6.
----------
Consider the following in a language allowing nested procedures
procedure a is
x : integer;
procedure b is
y : integer;
procedure c is
z : integer;
begin
print (x + y + z);
..
end c;
begin
...
c;
end b;
begin
...
b;
end a;
The two most common methods of handling the evaluation of x+y+z in procedure c
are the global display method and the static chain method.
Answer the following questions about these methods:
c) How is the global display updated when a calls b, and when b calls c?
a) What is the state of the global display at the point of evaluating x+y+z?
b) How is the global display used to evaluate x+y+z, that is to say, what
code is generated to load the operands (in the assembly of your choice)?
d) How is the static chain updated when a calls b, and when b calls c?
e) What is the state of the static chain at the point of evaluating x+y+z?
Sketch the contents of the stack.
f) How is the static chain used to evaluate x+y+z, that is to say. what
code is generated to load the operands?
Problem 7.
----------
In some plausible programming language, the loop construct has the form:
for I in Expr1 to Expr2 by Expr3 loop
Statement_List;
end loop;
{loop, for, in, to, by} are keywords. Expr1, Expr2, Expr3 are general
expresssions. The semantics of the loop is described informally as follows:
a) If Expr3 is positive the loop variable I takes on the sequence of values:
Expr1, Expr1 + Expr3, Expr1 + 2 * Expr3 ... . The last value of the
sequence is smaller or equal to Expr2. If Expr1 > Expr2 the loop is not
executed at all.
b) If Expr3 is negative the loop variable takes on the decreasing sequence
Expr1, Expr1 + Expr3 ... etc. The last value of sequence is larger or equal
to Expr2. If Expr1 < Expr2 the loop is not executed at all.
Write the quadruples needed to implement the general form of the loop, i.e.
when Expr1, Expr2 and Expr3 are general run-time expressions (not constants).
Indicate how the code simplifies if some of them are static constants.
Problem 8.
----------
Write a simple sorting routine (bubble or selection sort) in Ada or C++.
Write the quadruples for it, indicate the basic blocks, and draw the flow
graph. The argument is a one-dimensional array whose size in not known at
compile-time. In Ada or Java, the attribute Length will be used in the code.
In C/C++ the size will be passed as an explicit additional parameter.
Problem 9.
----------
In Ada, the notation A (X) can have several different meanings:
a) A can be a function, in which case this is a function call.
b) A can be an array and X a variable, in which case it is an indexed
component.
c) a can be an array and X can be a subtype declaration, as is
subtype tiny is integer range 1..5;
in which case A(X) is the slice A (1..5).
These ambiguities cannot be resolved in the grammar. Sketch the kind of
semantic analysis that would be necessary to resolve the meaning of this
construct.