Consider the following grammar:

     E   --->  dig | '('  P  E  E  ')'
     P   --->  '+' | '-' | '*' | '/' 
     dig --->  '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'

Here is a Java parser for this grammar:

public class Evaluate {
   private char tok;

   // eval: evaluate (after making additions below)
   public void eval() {
      E();
      System.out.println("Successful Parse!");
   }

   private void E() {
      tok = gettoken();
      if (Character.isDigit(tok))
         ; // do nothing for now
      else if (tok == '(') {
         tok = gettoken();
         if (tok == '+' || tok == '-' || 
             tok == '*' || tok == '/' || tok == '^') {
            E();
            E();
            tok = gettoken();
            if (tok == ')')
               ; // do nothing for now
            else { err(0);}
         }
         else { err(1);}
      }
      else { err(2);}
   }

   // err: error message
   private void err(int i) {
      System.out.println("Error number: " + i);
      System.exit(1);
   }

   // gettoken: fetch next token (here just a char)
   private char gettoken() {
      char next = ' ';
      do {
         try {
            next = (char)System.in.read();
         } catch (Exception e){
            err(2);
         }
      } while ( next == ' ' || next == '\n');
      return next;
   }

   public static void main(String[] args) {
      Evaluate e = new Evaluate();
      e.eval();
   }
}

% java Evaluate
6
6.0
% java Evaluate
(+ (* 3 3) (* 4 4))
25.0
% java Evaluate
(* (+ (* 5 4) (/ 4 2) ) 3)
66.0
% java Evaluate
(+ 3 (/ 1 (+ 7 (/ 1 (+ (* 4 4))))))
3.1415929203539825

1. What is the name of this kind of parser?

2. Would all the inputs above be legal as input to a real Lisp interpreter?
   (If "yes", you must say what the name for these inputs is in Lisp;
   if "no", you must say why they are not legal.)

3. Give the parse tree for the following expression:

   
   (* (+ (* 5 4) (/ 4 2) ) 3)
   

4. Using your parse tree in the previous question, show how values can propagated upward from the leaves to produce the number 66.0 at the root.

5. Carefully add code to the listing above so that the program will return the correct double value as it parses an input S-expression. If you wish, you may use the evaluating function below. (You should provide the extra code as carefully and completely as you can. If you don't know java well, you can still do this problem by just pretending that you are coding in C, since for this application the two languages are nearly identical.)

   
      private double eval2(char op, double arg1, double arg2) {
         switch (op) {
         case '+': return arg1 + arg2;
         case '-': return arg1 - arg2;
         case '*': return arg1 * arg2;
         case '/': return arg1 / arg2;
         case '^': return Math.pow(arg1, arg2);
         default: { err(3); return 0; }
         }
      }
   

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 A
      if (Character.isLowerCase(next)) {
           // POSITION B
         scan();
      }
      if (next == '=') scan();
           // POSITION C
      E();
      if (next == ';') scan();
           // POSITION D
   }

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

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)))
   4. (cons '(a b) '(c))
   5. (list '(a b) '(c))
   6. (append '(a b) '(c))
   7. (cond ((= 4 (* 2 3)) 47)
             (t 54))
   8. ()

9. Write a recursive Lisp function power that will compute an integer raised to a non-negative integer power. In conventional notation (using ^ for power), if the arguments to power are b and e, then
   b ^ e = 1, if e = 0, and
   b ^ e = b * (b ^ (e - 1)), otherwise, that is, if e > 0.

   For example, in Lisp notation, (power 2 5) is 32. (Of course, Lisp has a built-in "raise-to-a-power" function called expt, but you are not to use that.)

10. Draw a diagram showing the internal representation in Lisp of the S-expression:

    
    ((a b) c (d))
    

11. Consider the following Postscript code, which prints UTSA starting at (0, 0).

    
    /Times-Roman findfont 100 scalefont setfont
    0 0 moveto
    (UTSA) show
    showpage
    

    Rewrite this code so that it prints the UTSA 8 inches up from the bottom, and exactly right-justified 50 points from the right edge. Thus the right side of the "A" should be 50 points from the right edge of the paper. [Hints: The page is 8.5 inches wide. There are 72 points to an inch. The Postscript code (UTSA) stringwidth pop will give the horizontal extent of the string.]

12. For each of the 4 Postscript programs below, give a sketch (with dimensions) showing what will be printed and where. (In Postscript, angles are in degrees and a positive rotation is counter-clockwise.)

    Part a.	Part b.	Part c.	Part d.
    /box { newpath 0 0 moveto 0 72 rlineto 72 0 rlineto 0 -72 rlineto closepath } def 45 rotate 200 200 translate box stroke showpage	/box { newpath 0 0 moveto 0 72 rlineto 72 0 rlineto 0 -72 rlineto closepath } def 200 200 translate 45 rotate box stroke showpage	/box { newpath 0 0 moveto 0 72 rlineto 72 0 rlineto 0 -72 rlineto closepath } def 200 200 translate 45 rotate 0.25 0.25 scale box stroke showpage	/box { newpath 0 0 moveto 0 72 rlineto 72 0 rlineto 0 -72 rlineto closepath } def 0.25 0.25 scale 200 200 translate 45 rotate box stroke showpage

13. Consider the following Postscript program:

    /line { newpath 0 0 moveto 1000 1000 lineto stroke } def /lines { 1 1 300{ 5 0 translate line } for } def % PART A: 1 setlinewidth gsave -900 0 translate lines grestore % PART B: /Helvetica-Bold findfont 100 scalefont setfont 1 setgray % white 50 500 moveto (SUBVERT) show 0 setgray % black % PART C: newpath 50 500 moveto (SUBVERT) false charpath clip 1.25 setlinewidth -901 0 translate lines showpage

    1. What does the function line do?
    2. What does the function lines do?
    3. What does the portion marked PART B: do?
    4. What does the portion marked PART C: do?

14. 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. Give several types of tokens that Ruby programmers often leave off at the end of lines, although they can be present.
    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. What do local variables of a function start with?
    7. What do class instance variable of a class start with?
    8. What do global variables start with?
    9. What do constants start with?

15. 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 about authors, titles of books, and date released (from a library webpage) in the following form:

    
    Emma by Austen, Jane Released: Aug 1994
    Mansfield Park by Austen, Jane Released: Jun 1994
    Doctor Marigold by Dickens, Charles Released: Aug 1998
    George Silverman's Explanation by Dickens, Charles Released: Feb 1997
    Sir Nigel by Doyle, Arthur Conan Released: Aug 2005
    Tales of Terror and Mystery by Doyle, Arthur Conan Released: Aug 2005
    

    We want to rewrite these in the following form. This assumes that the book title is always ended by "by", that the author's last name is always followed by "," and that the first name(s) is(are) always followed by "Released:".

    
    Jane Austen, "Emma" (Aug 1994)
    Jane Austen, "Mansfield Park" (Jun 1994)
    Charles Dickens, "Doctor Marigold" (Aug 1998)
    Charles Dickens, "George Silverman's Explanation" (Feb 1997)
    Arthur Conan Doyle, "Sir Nigel" (Aug 2005)
    Arthur Conan Doyle, "Tales of Terror and Mystery" (Aug 2005)
    

    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.