Answers are in red. Total points: 150.

1. (30) Grammars and Syntax-directed Translation:

   Consider the following Java parser, with runs to the right.

   Parser

   Runs

   /* Gramm.java: simple parser * grammar: P ---> S '$' * S ---> A | '(' Op S S ')' * Op ---> '+' | '-' | '*' | '/' * A ---> digit */ import java.io.*; class Lisp { private char next; private int P() { int res = S(); scan(); if (next != '$') return error(1); else return res; } private int S() { scan(); int res; if (Character.isDigit(next)) { res = (next - '0'); return res; } else if (next == '(') { scan(); char op = next; int arg1 = S(); int arg2 = S(); scan(); /* to ')' */ if (next != ')') return error(2); res = apply(op, arg1, arg2); return res; } else return error(3); } private int apply(char op, int arg1, int arg2) { switch (op) { case '+': return arg1 + arg2; case '-': return arg1 - arg2; case '*': return arg1 * arg2; case '/': return arg1 / arg2; default: return error(4); } } private void scan() { do { try { next = (char)System.in.read(); } catch (IOException e) { System.out.println("Excp"); } } while (Character.isWhitespace(next)); } private int error(int n) { System.out.println("*** ERROR: " + n); //System.exit(1); return 0; } public static void main(String[] args) { Lisp lisp = new Lisp(); System.out.println(lisp.P()); } }

   % javac Lisp0.java % java Lisp0 6 $ Success % java Lisp0 (+ 6 7) $ Success % java Lisp0 (* (+ 2 3) (- 5 2)) $ Success % java Lisp0 (* (+ 2 (/ 6 2))(- (* 3 2) 4))$ Success % java Lisp0 (+ 6 7 $ *** ERROR: 3 ------------------------------- % javac Lisp.java % java Lisp 6 $ 6 % java Lisp (+ 6 7) $ 13 % java Lisp (* (+ 2 3) (- 5 2)) $ 15 % java Lisp0 (* (+ 2 (/ 6 2))(- (* 3 2) 4))$ 10

   The program Lisp0.java is a parser for the grammar in comments at the top of the program code. Sample runs are given at the upper right.

   Answer the following questions:

   1. What kind of parser is this? Recursive descent.

   2. Give the parse tree for the sentence (* (+ 2 3) (- 5 2)) $.

      
                                                      P
                                                      |
                                   +------------------+----------------+
                                   |                                   |
      +----+--------------+--------+---------------+--------------+    |
      |    |              |                        |              |    |
      |    Op             S                        S              |    |
      |    |              |                        |              |    |
      |    |    +----+----+----+----+    +----+----+----+----+    |    |
      |    |    |    |    |    |    |    |    |    |    |    |    |    |
      |    |    |    Op   S    S    |    |    Op   S    S    |    |    |
      |    |    |    |    |    |    |    |    |    |    |    |    |    |
      |    |    |    |    A    A    |    |    |    A    A    |    |    |
      |    |    |    |    |    |    |    |    |    |    |    |    |    |
      (    *    (    +    2    3    )    (    -    5    2    )    )    $
      

   3. An early scan scans as early as possible, while a late scan scans as late as possible. Which kind of scan is this? Give one example from the code supporting your answer.

      What is the advantange of this kind of scan (which is actually not being utilized here)? This is a late scan. For example, inside the S function, there is no scan right after handling a digit. The scan doesn't occur until the begining of S, when the next s-expression is parsed (at the last possible time). Similarly, in S at the end, there is no scan after handling the ')'. Finally, the code doesn't immediately scan after seeing an operator, but it waits until the following s-expression is parsed by S, where a scan is required to tell if the s-expression is a digit or a parenthesized expression.

      With this type of scan, we don't need the '$' at the end of an s-expression, since when it handles the last token of an s-expression (a digit or a ')'), it won't be trying to scan for another token. If we were handling a sequence of s-expressions, the next token starting the next s-expression wouldn't be scanned until the start of the S function.

      Stated more forcefully, a late scan is correct and an early scan is incorrect, although sometimes it doesn't matter, and we've sometimes used an early scan since it is easier to implement and to understand. Early scan: scan immediately after you've made a decision based on the token. Late scan: scan only when you can't proceed without the next token.

   4. Is the input to this program legal Lisp (assuming the '$' is dropped off)? (Yes or No)

   5. Add code to this program so that it becomes the program Lisp.java with runs shown at the right above. This should be evaluating the results of the inputs, where the evaluation should be done in the obvious way. (Be careful with the code you add -- there are several things needed.) Code in red above.

2. (25) The Tiny Translation:

   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 '=' E ';'
   

   Here is my version of the portion of the parser needed to handle this assignment statement. I removed three occurrences of else error(9) in order to simplify the code. I also marked 4 "POSITIONS" in the code, locations to refer to below. This is just the bare parser, and you should realize that a number of additional features and statements must be added to this function to get the final compiler.

   
      private void A() {
         // here have already scanned for the first token of A
              // POSITION W
         if (Character.isLowerCase(next)) {
              // POSITION X
            scan();
         }
         if (next == '=') scan();
              // POSITION Y
         E();
         if (next == ';') scan();
              // POSITION Z
      }
   

   Suppose your program is translating the following statement:

   
      a = b + 3*c;
   

   6. The function A will directly output one or more MIPS statements while translating this assignment statement. In order to get full credit for this problem, you need to realize that A only outputs two MIPS instructions at the end: a lw followed by a sw, using information provided earlier. No other instructions are output directly by A.

      Stated another way, the function A has no way to know what is on the right side of the assignment operator, only that it is an expression and that the address where the value of the expression will be found is returned into A.

      1. What is(are) the MIPS statement(s)? The function A is very simple. It needs to save the location of the variable name corresponding to the lower-case letter. Then it needs to save the memory location returned by the call to E (where the value of E will be at run-time). Finally (after the call to E) it will output a loadword instruction (to load the result of the E() call), and then it will output a storeword instruction, to store the result in the memory location corresponding to the lower-case variable name.

      2. At what POSITION(S) will it(they) be output? They need to be output after the call to E, that is, in position Z.

      3. What information (returned or obtained) will be needed to output this(these) statement(s)? As stated above, the loadword needs the memory address returned from E that gives the location where the value of E will be at run-time.
         The storeword instruction needs the memory address where the variable represented by the lower-case letter is to be stored at run-time.

   7. There will have to be MIPS statements to perform an "add" and a "mul".
      1. Which of these will come first, the "add" instruction or the "mul" instruction? The "mul" will come before the "add" because of the precedence of these operators.

      2. How will these statements be output by the compiler? The "mul" and "add" MIPS instructions will be output during the course of the call to E(). This will happen completely independently of A.

      3. Between which pair of "POSITIONS" will the "add" and "mul" MIPS statements end up getting output? So these end up getting output during the call to E, that is, between POSITION Y and POSITION Z.

   ---

   3. (30) Lisp:
      8. In each case say what the Lisp interpreter would produce when it evaluates the given input (there are no errors):
         1. (car '((a ) b c d (e))) (A)
         2. (cdr '(a b (c d))) (B (C D))
         3. (cdr (car '((a b) c d))) (B)
         4. (cons '(a) '(b c)) ((A) B C)
         5. (list '(a) '(b c)) ((A) (B C))
         6. (append '(a) '(b c)) (A B C)
         7. (cond ((= 6 (* 2 3)) 47)
                   (> 6 (+ 2 1)) 55)
                   (t 72)) 47
         8. () NIL

      9. Write a recursive Lisp function mul that will multiply the numbers in its argument list, so that (mul '(2 4 3)) should return the value 24.

         
         > (defun mul (x)
               (cond ((null x) 1)
                   (t (* (car x) (mul (cdr x))))))
         MUL
         > (mul ())
         1
         > (mul '(3))
         3
         >  (mul '(2 4 3))
         24
         > (mul 4)
         *** - CAR: 4 is not a LIST
         ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
         > (defun mul (x)
               (cond ((null x) "Error-1")
                   ((atom x) "Error-2")
                   ((null (cdr x)) (car x))
                   (t (* (car x) (mul (cdr x))))))
         MUL
         > (mul ())
         "Error-1"
         > (mul 4)
         "Error-2"
         > (mul '(3))
         3
         > (mul '(2 4 3))
         24
         

      10. Write a recursive Lisp function length that will return the number of elements at the top level in its argument list, so that
          (length '(a b c)) should return 3,
          (length '()) should return 0, and
          (length '((a b) c (d e f))) should return 3.

          
          > (defun length0 (x)
                (cond ((null x) 0)
                   (t (+ 1 (length0 (cdr x))))))
          LENGTH0
          > (length0 '(a b c))
          3
          > (length0 '())
          0
          > (length0 '((a b) c (d e f)))
          3
          > (length0 '(((((x))))))
          1
          

   ---

   4. (25) Postscript:

      The following Postscript code draws an elipse.

      
      %!PS-Adobe-2.0
      /inch {72 mul} def
      /elipse {
         gsave
            1 2 scale
            newpath
            0  0  1.5 inch 0 360 arc
            stroke
         grestore
      } def
      elipse
      showpage
      

      Here x y r ang1 ang2 arc creates an arc of a circle, centered at x and y, with radius r, counterclockwise from angle ang1 to ang2. Remember that gsave and grestore save and restore the graphics state.

      11. Describe carefully what this elipse will look like on the page. It is centered at the origin (lower left), so only a quarter of it appears on the page. It extends 1.5 inches along the x-axis and 3 inches along the y-axis. (The actual elipse is 3 inches by 6 inches.)

      12. Use a translate operator outside this function, and without changing the function, to draw the elipse exactly centered on an 8.5 by 11 inch sheet.

          
          %!PS-Adobe-2.0
          /inch {72 mul} def
          /elipse {
             gsave
                1 2 scale
                newpath
                0  0  1.5 inch 0 360 arc
                stroke
             grestore
          } def
          
          8.5 2 div inch 11 2 div inch
          translate
          elipse
          showpage
          

      13. Add code to draw 36 elipses the same as above, only each rotated from the previous one by 10 degrees. [You must use a loop for this: a for loop takes the form: init incr final { body } for, where init is the initial value of the loop variable, incr is the increment, and final is the final value.]

          
          %!PS-Adobe-2.0
          /inch {72 mul} def
          /elipse {
             gsave
                1 2 scale
                newpath
                0  0  1.5 inch 0 360 arc
                stroke
             grestore
          } def
          
          /elipses {
             0 10 360 {
                pop
                10 rotate
                elipse
             } for
          } def
          
          8.5 2 div inch 11 2 div inch
          translate
          elipses
          showpage
          

      14. Give Postscript code to print your own name at any height on a page, but exactly centered on an 8.5 inch wide sheet. [The code /Times-Bold findfont 20 scalefont setfont gives a font, and (xyz) stringwidth pop gives the horizontal extent of the the string "xyz".]

          
          %!PS-Adobe-2.0
          /inch {72 mul} def
          /Times-Bold findfont 20 scalefont setfont
          /namewidth (Neal R. Wagner) stringwidth pop def
          
          8.5 inch namewidth sub 2 div 11 inch 2 div moveto
          (Neal R. Wagner) show
          
          showpage
          

   ---

   5. (25) Ruby:
      15. This part asks about some random features of Ruby that you should have looked at:
          1. What token is used to terminate many Ruby control structures (such as "if-elsif-else", "while")? end

          2. What token does a function definition start with? def

          3. Because Ruby allows programmers to leave off various tokens at the end of lines, how does Roby know that a 2-line statement is continued onto the next line? (There are two ways.) Either the line is not syntatically complete, or it ends with a backslash.

          4. What is the name of the method in a Ruby class that does the initialization (in place of the constructors in Java and C++)? initialize

          5. The class Date in Recitation 13 had the following line as the second line attr_reader :year, :month, :day. What is the purpose of this line (what do you get from it)? This is shorthand to define an instance variable named @year and to define a method named year giving read access to the variable:

             
             def year
                @year
             end
             

             Similarly for month and day.

          6. How does Ruby declare that a class is extending another class. [For example, in Recitation 14, Date was the superclass, and Time inherited from it, that is, Time extended Date. What notation said to do this inheritance?] Use the following at the start of the declaration for the date class:

             class Time < Date

          7. What do global variables start with? $

          8. What do constants start with? uppercase letter

      16. This question is about Ruby regular expressions, used in an object-oriented fashion, as you were supposed to work with in Recitation 13. Suppose you have input data giving student names and student numbers in the following form:

          
          17 Cerica S. Johnson  @00022222
          18 Alejandro Juarez  @00111111
          19 Erhan J. Kartaltepe  @00777777
          

          We want to rewrite these in a different way. This assumes that the last name is always followed by one or more blanks and then an '@' character. There may or may not be a middle initial. You should drop the initial number, write the student number without leading 0's, and write the last name first, followed by a comma, followed by a blank and the rest of the name, as shown below:

          
          22222 Johnson, Cerica S.
          111111 Juarez, Alejandro
          777777 Kartaltepe, Erhan J.
          

          Write a Ruby program using Ruby code and regular expressions to do this translation. If you have forgotten various items, just fake it as best you can, but you are not supposed to be using Perl for this problem. If you didn't do Recitation 13 the way I suggested but used some method of your own, then you should mention this.

      Here is one solution:

      
      #!/usr/local/bin/ruby
      
      while line = gets
          # main RE
          re = /^(\d+)\s+([a-zA-Z]+)\s+([.a-zA-Z]+)\s*([a-zA-Z]*)\s*@(\d+).*$/
          m = re.match(line) # match line with RE
          
          # output new line
          newline = m[5] + " "
          if m[4] == ""
             newline += m[3] + ", " + m[2]
          else 
             newline += m[4] + ", " + m[2] + " " + m[3]
          end
          newline += "\n"
          print newline
      end
      % p16.rb < p16.txt
      00022222 Johnson, Cerica S.
      00111111 Juarez, Alejandro
      00777777 Kartaltepe, Erhan J.
      

      Here is a debug run of this:

      
      #!/usr/local/bin/ruby
      
      while line = gets
          print "Input line:  \"" + line.chomp + "\"\n"
          # main RE
          re = /^(\d+)\s+([a-zA-Z]+)\s+([.a-zA-Z]+)\s*([a-zA-Z]*)\s*@(\d+).*$/
          m = re.match(line) # match line with RE
          
          # debug output
          debugout = "Debug output: "
          for i in (1...m.length)
             debugout += " m[" + i.to_s + "]:\"" + m[i] + "\","
          end
          debugout += "\n"
          print debugout
          
          # output new line
          newline = "Output line: \"" + m[5] + " "
          if m[4] == ""
             newline += m[3] + ", " + m[2]
          else 
             newline += m[4] + ", " + m[2] + " " + m[3]
          end
          newline += "\"\n"
          print newline
          print "\n"
      end
      
      % p16debug.rb < p16.txt
      Input line: "17 Cerica S. Johnson  @00022222"
      Debug output:  m[1]:"17", m[2]:"Cerica", m[3]:"S.", m[4]:"Johnson", m[5]:"00022222",
      Output line: "00022222 Johnson, Cerica S."
      
      Input line: "18 Alejandro Juarez  @00111111"
      Debug output:  m[1]:"18", m[2]:"Alejandro", m[3]:"Juarez", m[4]:"", m[5]:"00111111",
      Output line: "00111111 Juarez, Alejandro"
      
      Input line: "19 Erhan J. Kartaltepe  @00777777"
      Debug output:  m[1]:"19", m[2]:"Erhan", m[3]:"J.", m[4]:"Kartaltepe", m[5]:"00777777",
      Output line: "00777777 Kartaltepe, Erhan J."
      

   ---

   6. (15) Prolog:
      17. Suppose we have a collection of Prolog facts of the form:

          
          courses(cs1713, tr-1400, wagner, sb3-02-16, fulltime).
          courses(cs1723, tr-1230, womack, sb3-01-03c, parttime).
          courses(cs2213, mw-1600, wagner, sb3-02-16, fulltime).
          

          where this means that the course CS 1713 is taught at 2PM, Tues/Thurs, by Neal Wagner, whose office is SB 3.02.16, and Wagner is a full-time employee.

          1. How can we get Prolog to know that tr-1400 represents 2PM, Tues/Thurs? For this we need new facts of the form:

             
             times(tr-1400, '2PM, Tues/Thurs').
             times(tr-1230, '12:30PM, Tues/Thurs').
             times(mw-1600, '4PM, Mon/Wed').
             

          2. Assuming that each field has an alternate readable representation, there are still fundamental flaws in the form of the above facts. What is wrong with having facts of this form? The instructor "wagner" has his office number and full-time/part-time status stored as part of the data for courses. In the above case this data is stored multiple times, creating various problems when inserting a change of office number. Also the office number would not be available for someone not teaching a course, as was discussed in: database design.

          3. What would be a better form for these facts? They should be split up as follows (again as illustrated in the link above):

             
             courses(cs1713, tr-1400, wagner).
             courses(cs1723, tr-1230, womack).
             courses(cs2213, mw-1600, wagner).
             faculty(wagner, sb3-02-16,  fulltime).
             faculty(womack, sb3-01-03c, parttime).