Consider the following grammar:

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

You are to add code to the listing above (not shown here) so that the program will return the correct double value as it parses input. Here is an interactive session showing legal input and what should be returned by your program.

% 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))))))
The above input was included in error.  It is legal in Lisp,
but not according to the above grammar or the above parser.
It should have been:
(+ 3 (/ 1 (+ 7 (/ 1 (* 4 4)))))
3.1415929203539825

1. What is the name of this kind of parser? Recursive descent 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..) Yes they are legal Lisp inputs. They are S-expressions. (The semantics is different, though, because for this program, all inputs produce a double result.)

3. Give the parse tree for the following expression:

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

   
                                       E(66)
                                       |
   +---+-------------------------------+------------------------------+----+
   |   |                               |                              |    |
   |   |                               E(22)                          |    |
   |   |                               |                              |    |
   |   |   +---+-----------+-----------+-----------+-------------+    |    |
   |   |   |   |           |                       |             |    |    |
   |   |   |   |           E(20)                   E(2)          |    |    |
   |   |   |   |           |                       |             |    |    |
   |   |   |   |   +---+---+----+----+    +----+----+----+----+  |    |    |
   |   |   |   |   |   |   |    |    |    |    |    |    |    |  |    |    |
   |   |   |   |   |   |   E(5) E(4) |    |    |    E(4) E(2) |  |    E(3) |
   |   |   |   |   |   |   |    |    |    |    |    |    |    |  |    |    |
   |   P   |   P   |   P  dig  dig   |    |    P   dig  dig   |  |   dig   |
   |   |   |   |   |   |   |    |    |    |    |    |    |    |  |    |    |
   (   *   (   +   (   *   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.Shown in parens above.

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.) Complete answer below, with additions in red.

   
   // Evaluate: evaluates simple S-expressions as doubles
   //   using the grammar below
   // grammar:  S   --->  dig | '('  P  S  S  ')'
   //           P   --->  '+' | '-' | '*' | '/' 
   //           dig --->  '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
   //
   public class Evaluate {
      private char tok; // = ' ';
   
      // eval: evaluate an S-expression
      public void eval() {
         double result = S();
         System.out.println("Result: " + result);
      }
   
      // S: recognize a lisp s-expression
      private double S() {
         char opcode;
         double operand1, operand2;
         tok = gettoken();
         if (Character.isDigit(tok))
            return  (double)(tok - '0');
         else if (tok == '(') {
            tok = gettoken();
            if (tok == '+' || tok == '-' || 
                tok == '*' || tok == '/' || tok == '^') {
               opcode = tok;
               operand1 = S();
               operand2 = S();
               tok = gettoken();
               if (tok == ')')
                  return eval2(opcode, operand1, operand2);
               else { err(0); return 0; }
            }
            else { err(1); return 0; }
         }
         else { err(2); return 0; }
      }
   
      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; }
         }
      }
      // 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();
      }
   }
   

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. 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 will it(they) be output? They need to be output after the call to E, that is, in position D.
   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 C and POSITION D.

8. In each case say what the Lisp interpreter would produce when it evaluates the given input (there are no errors):

   > (car '((a b) c d (e)))
   (A B)
   > (cdr '(a (b c d)))
   ((B C D))
   > (cdr (car '((a b) c)))
   (B)
   > (cons '(a b) '(c))
   ((A B) C)
   > (list '(a b) '(c))
   ((A B) (C))
   > (append '(a b) '(c))
   (A B C)
   >  (cond ((= 4 (* 2 3)) 47)
                (t 54))
   54
   >  ()
   NIL
   

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.) Answer below:

   
   (defun power (b e)
      (cond ((= e 0) 1)
            (t (* b (power b (- e 1))))))
   

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

    ((a b) c (d))
    

    Here is an answer:

    
                      +---+---+    +---+---+               +---+---+
    ((a b) c (d)):--->| o | o-|--->| o | o-|-------------->| o | o-|---> nil
                      +---+---+    +---+---+               +---+---+
                        |            |                       |
                        |            v                       |
                        |            c                       v
                        |                                  +---+---+
                        v                                  | o | o-|---> nil
                      +---+---+    +---+---+               +---+---+
                      | o | o-|--->| o | o-|---> nil         |
                      +---+---+    +---+---+                 v
                        |            |                       d
                        v            v
                        a            b
    

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.] Here is an answer:

    
    %!PS-Adobe-2.0
    %% problem 11 on final exam
    /inch {72 mul} def
    /Times-Roman findfont 100 scalefont setfont
    8.5 inch 50 sub (UTSA) stringwidth pop sub
    8 inch moveto
    (UTSA) show
    showpage
    

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.) The results of each Postscript program are given as PDF files at the end of the table.

    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
    prob12a.pdf	prob12b.pdf	prob12c.pdf	prob12d.pdf

13. Consider the following Postscript program: Results of the program (in PDF), along with 3 other slightly different versions, have links to them at the end. Interestingly enough, in all versions there are slight differences between the regular fonts and the outline fonts. I don't know why this is the case.

    /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

    lines.pdf   lines2.pdf   lines3.pdf   lines4.pdf

    1. What does the function line do? The function line draws a single line from the origin diagonally at a 45 degree angle to the point (1000, 1000).
    2. What does the function lines do? Lines draws 300 lines, starting with the one above, and then placing each subsequent line 5 point to the right of the previous one. PART A (not asked for) translates lines 900 points to the left, so if just fills the page with lines.
    3. What does the portion marked PART B: do? PART B overwrites the lines with large letters "SUBVERT" in white.
    4. What does the portion marked PART C: do? This then redraws the lines, clipped to the inside of the letters, drawn slight wider, and moved 1 point to the left. This makes the letters readable, but they seem to blur.

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")? An end token is used for these, as well as for classes and function definitions.
    2. What token does a function definition start with? It starts with a def token.
    3. Give several types of tokens that Ruby programmers often leave off at the end of lines, although they can be present. They leave off semicolons at the end, as well as token like do and then if they come at the end of a line.
    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++)? Its name is 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
       

    6. What do local variables of a function start with? With a lower-case letter.
    7. What do class instance variable of a class start with? With an "at" sign: @.
    8. What do global variables start with? With an "dollar" sign: $.
    9. What do constants start with? With an upper-case letter.

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. Answer:

    
    #!/usr/local/bin/ruby
    
    while line = gets  # fetch next line of input file
       re = /^(.+)by\s+([-a-zA-Z]+),\s+(.+)Released:\s+(.*)$/  # main RE
       m = re.match(line) # match line with RE
       newline = m[3].strip + " " + m[2].strip + ", \"" +
          m[1].strip + "\" (" + m[4].strip + ")\n"
       print newline
    end