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 Lisp0 { private char next; private void P() { S(); scan(); if (next != '$') error(1); else System.out.println("Success"); } private void S() { scan(); if (Character.isDigit(next)) { // nothing! } else if (next == '(') { scan(); // next == Op S(); S(); scan(); /* next == ')' */ if (next != ')') error(2); } else error(3); } private void scan() { do { try { next = (char)System.in.read(); } catch (IOException e) { System.out.println("Excp"); } } while (Character.isWhitespace(next)); } private void error(int n) { System.out.println("*** ERROR: " + n); } public static void main(String[] args) { Lisp0 lisp = new Lisp0(); 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?

2. Give the parse tree for the sentence (* (+ 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)?

    

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.)

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.
   1. What is(are) the MIPS statement(s)?

   2. At what POSITION(S) will it(they) be output?

   3. What information (returned or obtained) will be needed to output this(these) statement(s)?

    

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?

   2. How will these statements be output by the compiler?

   3. Between which pair of "POSITIONS" will the "add" and "mul" MIPS statements end up getting output?

3. 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)))
      2. (cdr '(a b (c d)))
      3. (cdr (car '((a b) c d)))
      4. (cons '(a) '(b c))
      5. (list '(a) '(b c))
      6. (append '(a) '(b c))
      7. (cond ((= 6 (* 2 3)) 47)
                (> 6 (+ 2 1)) 55)
                (t 72))
      8. ()

       

   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.

       

       

       

   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.

4. 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.

        

   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.

        

   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.]

        

        

   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".]

5. 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")?

       2. What token does a function definition start with?

       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.)

       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++)?

       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)?

       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?]

       7. What do global variables start with?

       8. What do constants start with?

   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.

6. 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?

           

       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?

           

       3. What would be a better form for these facts?