Fall 1998

Final Examination

This is a take-home examination. Exams should be placed in my mailbox by Tuesday Dec. 22, 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. 1. Consider the grammar: A -> aAa | epsilon with one non-terminal and one terminal symbol. a) characterize the sentences in this language. b) Show that this language is not LL (1), by trying to build the corresponding parse table. c) A naive recursive descent parser for this grammar might be as follows: procedure A is begin if Next_Token = Token_a then Scan; -- skip over first a A; if Next_Token = Token_a then Scan; -- skip over second a else error; end if; else return; end if; end; Show that this does not work. (Trace the parser over some sentence in the language) This contrived example is often used in textbooks to argue that recursive descent is not a good parsing technique. d) How would you write a recognizer for the sentences in this language? 2. Consider the well-known syntactic ambiguity in C: (A)-X If A denotes a type, either built-in or declared by means of a typedef, then this expression is a cast. If A denotes a numeric variable, the expression is a substraction. How would you handle the disambiguation of this expression in a compiler? Describe what tree you would build, and how you might fix it up if need be. 3. a) Consider the following function in an ML-like language. Its purpose is to apply a given operation to all the elements in a list: func apply (op, l, val) = if null (l) then nil else cons ( op (hd (l), val), apply (op, tl (l), val)) Give the most general type expression for this function. b) The following function produces the partial application of a given operation to all the prefixes of a given list (eg. the partial sums of the first one, two, three ... elements of the list). In APL the corresponding operator is called expansion. func expand (op, l) = if null (l) then nil elsif null (tl (l)) then cons (hd (l), nil) else cons (hd (l), apply (op, expand (op, tl (l)), hd (l))) Give the most general type expression for expand. 4. Consider the following procedure, that computes the primes numbers up to some number N. 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. Describe what needs to be done for the function call to Sqrt and the procedure calls to Put and Put_Line. 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.