CS3723, Exam 2, 8 Apr 2013, Answers
  1. (15) Why can't we use a grammar rule like E ---> E + T  |  T in a recursive descent parser? Because a R-D parser would have a function E which first of all would call E recursively, producing an infinite recursive regression.

    What did we do to take care of this problem? (Explain with a bit of detail.) Our solution was to rewrite the grammar so as to eliminate the left recursion. (This is not always possible.) The new grammar rule replacing both rules above is E ---> T { + T }. The parse trees and derivations are in general different with this new rule, but the language generated is the same.

    We talked about how the change to E ---> T + E  |  T would work with a R-D parser, but this changes how + works, making + associate from right to left, which is unacceptable. [I gave part credit for this.]

  2. (20) Suppose that in clisp you submit the following two expressions (where '>' is the clisp prompt): 
      > (setq x '(a b c))
> (setq y '(d e))
    In each case below, give the result of the given expression (there are no errors): 
      > (cdr x) -> (B C)
> (car y) -> D
> (cons x y) -> ((A B C) D E)
> (cons (car x) (cdr x)) -> (A B C)  [I also accepted (A E) as the answer to (cons (car x) (cdr y))]
> (append x y) -> (A B C D E)
> (list x y) -> ((A B C) (D E))
> (mapcar '+ '(1 2 3) '(4 5 6)) -> (5 7 9) [which is ((+ 1 4) (+ 2 5) (+ 3 6))]

    With the following erroneous expression, explain (in some detail) what clisp tries to do with the expression and why it fails, that is, produces an error. (Well, it's an error if it is the only input.) 

      > (cdr (a b c)) -> *** - EVAL: undefined function A
      When Lisp evaluates (cdr (a b c)), it takes the car, which is the function cdr,so that's OK for the given input, since "cdr" is a built-in function. Then it takes each following S-expression, in this case there is only (a b c), and tries to evaluate it, which means using a as a function. But a is not a function, although of course we could define a function named a. So with no additional input this is an error. (If a were a function, b and c would have to have values, but Lisp doesn't get that far in this case.)

      There's nothing inherently wrong with this kind of call, just that a needs to be a function and b and c data that a can be applied to. (Some people said that the (a b c) wasn't a list or wasn't an S-expression, but it is both.) So for example: 

        > (setq b '(y))
(Y)
> (setq c '(z))
(Z)
> (defun a (x y)
    (append x y))
A
> (a b c)
(Y Z)
> (cdr (a b c))
(Z)

  3. (20) Write a recursive Lisp function with one parameter n that will add n terms of the series of squares of consecutive integers: 12 + 22 + 32 + ... + n2 = 1 + 4 + 9 + ... + n2. Call this function with n = 10. 
      > (defun sumsq (n)
    (cond ( (= n 1) 1)
          ( t (+ (* n n) (sumsq (- n 1)))) ))
SUMSQ
> (sumsq 10)
385

;;;;;;;;;;;;;;;;;;;;;; the first condition:
; Or ( (= n 0) 0) works for the first condition.
; (It turns out that this sum equals n*(n+1)*(2*n+1)/6.)
; 
; One student wanted to use an if, which we didn't study.  This would be:
> (defun sumsq (n)
    (if (= n 1)  ; start of if, plus test
       1  ; then part
       (+ (* n n) (sumsq (- n 1))) ; else part
    )  ; end of if
)  ; end of function
SUMSQ
> (sumsq 10)
385

  4. (20) Write a recursive Lisp function that will take a simple list of numbers and will add up all the positive numbers in the list, leaving the negative numbers out of the sum. Show how to call this function with the list (4 -2 0 -3 1 7 -1). (The answer would be 12. Of course it doesn't matter whether or not you add in entries equal to 0.) 
      > (defun add-pos (l)
    (cond ((null l) 0)
          ((< (car l) 0) (add-pos (cdr l)))
          (t (+ (car l) (add-pos (cdr l))))  ))
ADD-POS
> (add-pos '(4 -2 0 -3 1 7 -1))
12   or else
> (setq n '(4 -2 0 -3 1 7 -1))
(4 -2 0 -3 1 7 -1)
> (add-pos n)
12

;;;;;;;;;;;;;;;;;;;;;; notes about the function:
; If you try to write (cond ( (null l) nil), returning nil for a null list,
; then it becomes one of the "numbers" added up, but Lisp won't let
; you use nil as part of a sum, because "NIL is not a number".
; 
; If you don't have the first condition check ( (null l) 0) at all,
; then again the function tries to add in nil when it gets to the end of the list.
; 
;  ((< (car l) 0) 0) will not work because 0 would be returned by the
; function immediately at that point, without finishing the list.

;;;;;;;;;;;;;;;;;;;;;; here's another longer method:
> (defun drop-negs (l)
   (cond ( (null l) nil)
         ( (< (car l) 0) (drop-negs (cdr l)))
         ( t  (append (list (car l)) (drop-negs (cdr l)))) ))
DROP-NEGS
> (drop-negs '(4 -2 0 -3 1 7 -1))
(4 0 1 7)
> (defun addpos (l)
   (apply '+ (drop-negs l) ))
ADDPOS
> (addpos '(4 -2 0 -3 1 7 -1))
12

;;;;;;;;;;;;;;;;;;;;;; favorite function name by two students:
; possum (See Pogo Possum.)

  5. (25) This question concerns the series of recitations used to translate programs from the Tiny™ language to MIPS assembler code. The portion of the grammar for Tiny© that handles assignment statements is:

      A  --->  lower-case-letter '=' E ';'

    Here is my version of the portion of the parser needed to handle this assignment statement. (I removed two error checks to simplify the code.) I marked 3 "POSITIONS" in the code, locations to refer to below. This is just the bare parser, and you should realize that several additional features and statements must be added to this function to get the final compiler.

         void A() {
      // The first token of the assignment is already in
      // the variable next, and it is known to be a
      // lower-case letter.  This is why A was called.
           // POSITION 1
         scan();
      if (next == '=') scan();
           // POSITION 2
      E();
      if (next == ';') scan();
           // POSITION 3
   }

    Suppose the compiler is translating the statement: a = b + 3*c;

    1. The function A will directly output some MIPS statements while translating this assignment statement.
      To get full credit for this question, you need to show that you know roughly what the function A does as it translates any assignment statement. You would get most or all of the credit for part a just by saying:

      The function A outputs exactly two MIPS instructions at Position 3:
      • a Loadword that loads into a temporary register what is at the address returned by the call to E, followed by
      • a Storeword that stores the value in the temporary register into the location used by the letter at the left of the assignment statement, in the case an 'a'.

      In much more detail the two instructions are, in order:

      1. Loadword, which will use the address returned by E. This address gives an index into the M "array" used by the MIPS program. In my program, I had to multiply by 4 to get the actual address, although you may have done the multiplication earlier. This could be the address of a constant, a single variable, or of a temporary location holding the value of the expression recognized and processed by E. This instruction loads the value at the given address into a temporary register. In my examples I used $t1.

        Assuming E returns the address of the first temporary, it will be at index 36 in the M array, or at address 36*4=144. The actual MIPS instruction then might be: 

            lw      $t1, 144($s1)

      2. Storeword, which will use the address of the variable on the left side of the assignemnt. Here this is an 'a', so the address will be 10 past the start of M, or at index 10, with address 10*4 = 40. At run time, this will store the value of the expression recognized by E into the variable given by the left side of the assignment. Assuming this variable is an 'a', the actual MIPS instruction might then be: 
            sw      $t1, 40($s1)
        The letter or its address had to be saved at POSITION 1 so that it could be used at POSITION 3.

      That's all A does. It doesn't return anything. It does farm all the rest of the work out to E and the functions that E calls.

      1. What are the MIPS statements? (You can say roughly what the statements are, or what they do.)
      2. At what POSITION number will they be output?
      3. What information (returned or obtained) will be needed to output these statements? (Be careful, there are two pieces of information.)

    2. Somewhere MIPS statements to perform an add and a mul will have to be output.
      1. Which of these will come first in the MIPS code, the add instruction or the mul instruction? (Give a reason for your answer.) The "mul" will come before the "add" because of the precedence of these operators.

      2. How and where will these statements be output by the compiler? (You do not need to answer this in complete detail.) The "mul" and "add" MIPS instructions will be output during the course of the call to E( ). This will happen completely independently of A.

        In more detail, function E will call T, which will output 4 MIPS instructions to do the "mul" (2 to load the two operands, 1 to multiply, and 1 to store the result in a temporary). Then after returning to E, it will call T a second time to get a second operand to output 4 MIPS instructions for the "add" (2 to load the two operands, 1 to add, and 1 to store the result in a temporary).

      Actual Java code for the function A. This is from my own compiler, with additions to the "bare" parser shown in red.

      private void A() {
   int res = 0, res1 = 0;
   res1 = next - 'a' + 10;
   scan();
   if (next == '=') scan();
   else error(10);
   res = E();
   if (next == ';') scan();
   else error(11);
   comment("# M[" + res1 + "] = M[" + res + "]");
   emit("        lw      $t1, " + (res*4) + "($s1)");
   emit("        sw      $t1, " + (res1*4) + "($s1)");
}

      Note that the particular lower-case letter stored in next is not known until the function A is called. This variable's index in the M array is calculated and stored in res1. When the sw instruction is output (the second instruction below), that index value is multiplied by 4 and used in the sw instruction. When the specific sw is output, it has that specific integer constant as part of the instruction.

      Similarly, the particular temporary variable whose index in the M array is returned by E is not known until the function E returns a value stored in res. Again, when the lw instruction is output (the first instruction below), that index value is multiplied by 4 and used in the lw instruction. Similarly, when specific lw is output, it has that specific integer constant as part of the instruction.

      The two MIPS instructions implementing the assignment statement each always use the same temporary register $t1.

      All of the above takes place at compile time. The specific value that is assigned to the variable is not known until run time.