Consider the following grammar that was part of one of the recitations.

S ---> b M b           ("S" is the start symbol)
M ---> ( L
M ---> a
L ---> M a )
    

1. Which are the terminal symbols?
   Which are the non-terminal symbols?
   Which are the meta-symbols?

2. Give the parse tree for the following sentence. (You may construct this parse tree by trial and error, or by any other means; you do not need to use the method in the recitation involving this grammar.)
   b ( ( a a ) a ) b

    

    

    

3. Which of our two parsing methods did we use in the recitation that involved this grammar?

4. Give a simple way to show that a grammar is ambiguous. [In fact, the grammar above is not ambiguous.]

5. Give one brief example of an ambiguous construct from one of the grammars that we studied. [Just state the example; don't show that it is ambiguous.]

The language describes by the grammar below gives fully parenthesized postfix expressions:

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

// Parser.java: parser for parenthesized postfix language
public class Parser {
   private char next; // = ' ';

   // P: recognize a program
   public void P() {
      E();
   }

   // E: recognize a statement
   private void E() {
      scan();
      if (Character.isDigit(next)) {
         // next is a single digit here
      }
      else if (next == '(') {
         E();
         E();
         scan();
         scan(); // for the ')'
         if (next != ')') error(1);
      }
      else error(3);
   }

   // scan: put the next non whitespace char into next
   private void scan() {
      do {
        try {
            next = (char)System.in.read();
        } catch (Exception e){
           error(2);
        }
      } while ( next == ' ' || next == '\n');
   }

   // error: error encountered during the parse
   private void error(int n) {
      System.out.println("ERROR " + n + ", Token: " + next );
      System.exit(1);
   }

   public static void main(String[] args) {
      Parser parser = new Parser();
      parser.P();
   }
}

% java Parser
6
6
% java Parser
( (2 3 +) (3 4 *) -)
-7
% java Parser
((2 4 ^) ( (8 2 /) (5 3 -) *) +)
24

6. What does fully parenthesized mean?

   What does postfix mean?

7. Evaluate the expression

   
   ((2 4 ^) ( (8 2 /) (5 3 -) *) +)
   

   carefully by hand and show that 24 is the correct answer.

8. Does this parser use an early or a late scanning stategy? What does this mean in terms of recognizing an expression? (No credit for just guessing "early" or "late".)

9. Supply the additional code needed to do the evaluation. If you wish, you may use the evaluating function below. (If you don't know any java, 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 int eval(int r1, int r2, char op) {
         switch (op) {
            case '+': return r1 + r2;
            case '-': return r1 - r2;
            case '*': return r1 * r2;
            case '/': return r1 / r2;
            case '^': int res = r1;
                         while (r2 != 1) {
                            res = res*r1; r2--;
                         }
                      return res;
            default: 
               error(4);
               return 0;
         }
      } 
   

10. In each case say what the Lisp interpreter would produce when it evaluates the given input (there are no errors):
    1. 17
    2. (+ (* 2 3) (* 8 4))
    3. (car '((a b c) d (e)))
    4. (cdr '((a b c) d (e)))
    5. (car (cdr '(a b c)))
    6. (cons '(a) '(b c))
    7. (append '(a) '(b c))
    8. (list '(a) '(b c))
    9. (cond ((= 4 (* 2 2)) 47)
              (t 54))
    10. ()

11. Explain why each of the following inputs is in error when evaluated by Lisp. Explain in each case exactly what the error is (not what the error message, if any, is).
    1. (car (cdr '(a b c))
    2. (car (car '(a b c)))
    3. (append (a b c) (d e f))

12. Write a Lisp function switch that will take a two-element list as input and returns a list with these elements in the opposite order. (This function does not use recursion, and you do not need to use cond either. You are not allowed to use the built-in Lisp function reverse. You can solve this problem just using functions from problem 10 above.) For example,

    > (switch '(a b))
    (B A)
    > (switch '((a) (b c)))
    ((B C) (A))
             

13. Write a recursive Lisp function remove that removes all occurrences of an element from a list. For example,

    > (remove 'a '(a b c a b))
    (B C B)
    > (remove 'a '(a a a))
    NIL
    > (remove 'a '(a))
    NIL
    > (remove 'a '(b c d))
    (B C D)
    > (remove '(a b) '(a (a b) c (a b) d (a b))
    (A C D)
             

Consider the following two Postscript programs:

/Times-Roman findfont 20 scalefont setfont /inch { 72 mul} def /square { newpath 0 0 moveto 1 inch 0 rlineto 0 1 inch rlineto -1 inch 0 rlineto closepath fill 0.1 inch 1.1 inch moveto (A Box) show } def square 4 inch 2 inch translate 60 rotate square 4 inch 2 inch translate 60 rotate square showpage

/inch { 72 mul} def /square { % stack: side => --- /side exch def newpath 0 0 moveto side 0 rlineto 0 side rlineto side neg 0 rlineto closepath fill } def 1 inch square 4 inch 2 inch translate 60 rotate 1.5 inch square 4 inch 2 inch translate 60 rotate 2 inch square showpage

14. Use a sketch to show exactly what the program on the left will print. [Hint: remember that Postscript uses degrees for angles and that a positive angle is counter-clockwise.]

15. The program on the right is a slight variation. It uses a parameter. Again sketch what the program on the right will print. Then explain exactly how the parameter is handled.

16. Replace the 7 lines before showpage on the left with

    
    0 1 20 {
       pop
       square
       1.5 inch 0.5 inch translate
       45 rotate
       0.5 sqrt dup scale % scale factor: 0.707
    } for
    

    Say approximately what will be printed with this replacement.

17. 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 is prints the UTSA 5 inches up from the bottom, and exactly centered horizontally on the page. [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.]

The use of Interfaces in Java:

18. What is an Interface in Java?

19. What is the Comparable interface, and what does a program need to do to implement it?

20. Explain in general terms how one can take a class that implements the Comparable interface, and use generic code to insert instances of the class into an array in increasing order (that is, sorting them with a generic sort).

     

     

     

     

(We didn't do enough with Prolog for it to make much sense to ask very much....)

Consider the Prolog facts and rules on the separate sheet, an example similar to one from class about CS courses. [Recall that any name starting with a capital letter is a variable.]

21. Which are the rules and which are the facts?

22. What does the character combination :- mean?

23. What happens when the following is entered (after loading in the example facts and rules), followed by typing ";" over and over?

    ?- spr03(X, Y, wagner, Z).
    

24. What happens when the following is entered, followed by typing ";" over and over?

    ?- faculty_teaches_in_room(_, Y, Z, '3.03.04BB').