Spring 2000

Final Examination

This is a take-home examination. Exams should be placed in my mailbox by Mednesday May. 10, 5 pm. You are welcome to use any references and texts, and to discuss the questions with your colleagues, but the work you hand in should be strictly yours. Needless to say, this also applies to the final project, which is due at the end of business, May 12. 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 --------- Your project implemented parameter-passing by value for scalar types. Suppose we want to implement parameter-passing by reference for arrays, and be able to write the usual: 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 variable 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?