Sample Final Exam

Name:
CS 312
Spring 1999, Final Exam
100 points

Directions: Remember, if I cannot READ your answer, then it is wrong; so write neatly and large enough for me to read. Good luck. Have a safe and happy summer.

  1. [20] Given the following grammar, draw parse trees for:
    
            <e>  ::=  + <e> <e>  |  * <e> <e>  |  <no>
            <no> ::=  2 | 3 | 4 | 5
    
    a.  + * 2 3 + 4 5	
    
    b.  * 2 + + 3 4 5
    

  2. [20] For the grammar given in Problem 1:
    1. Draw an Abstract Syntax tree for 1a.

    2. Give an Abstract Syntax for the concrete grammar.

    3. Give a Denotation Semantics meaning (or M) functions to evaluate the abstract syntax given in 2b.

  3. [20] Consider your instructor's solution to the Fraction class in Java.
    
    public class Fraction {
        // a Fraction is stored as a pair of integers:
        // (num, denom) in lowest common denominator form;
        // ie, 2/4 is stored as (1, 2).
    
    int num;       // numerator
    int denom;     // denominator
    
    public Fraction (int n, int d) throws ArithmeticException {
        num = n;
        denom = d;
        normalize( );
    } // Fraction
    
    public Fraction (Fraction frac) {
        num = frac.numerator( );
        denom = frac.denominator( );
    } // Fraction
    
    public int numerator( ) { return num; }
    
    public int denominator( ) { return denom; }
        
    public Fraction negated( ) { return new Fraction(-num, denom); }
    
    public Fraction add(Fraction frac) {
        return new Fraction (num * frac.denominator() +
    	denom * frac.numerator( ), denom*frac.denominator());
    } // add
    
    public Fraction subtract(Fraction frac) { return add(frac.negated( )); }
    
    public boolean equals(Fraction frac) { return compareTo(frac) == 0; }
    
    public int compareTo(Fraction frac) {
        // Answer -1 if receiver is less than frac,
        //         0 if equal to
        //         1 if greater
        Fraction tmp = subtract(frac);
        if (tmp.numerator() < 0)   return -1;
        else if (tmp.numerator() > 0)  return 1;
    	return 0;
    } // compareTo
    } // Fraction
    

    1. In method negated which constructor for Fraction is called. Explain.

    2. In method add which constructor for Fraction is called. Explain.

    3. Explain the logic of method subtract?

    4. Why doesn't the logic of method subtract normalize the resulting Fraction? Explain.

    5. Explain the logic of method compareTo?

  4. [20] Consider your instructor's solution to the Denotational Semantics assignment in Lisp.
    
    ;;; A State is implemented as a list of ordered pairs,
    ;;; of the form (variable value).  E.g. the initial state
    ;;; for int x; int y would be:
    ;;;   "((x 0) (y 0))
    ;;; we assume that EVERY variable occurs in the state
    
    ;;; Instructions are:
    ;;; (skip)
    ;;; (assign target source)
    ;;; (compound s0 s1 ... sn)
    ;;; (loop test body)
    ;;; (conditional test thenbr elsebr)
    
    (defun m-compound (lst state)
      (if (null lst)
          state
          (m-compound (rest lst) (m-instruction (first lst) state))
    ) )
    
    (defun m-instruction  (instr  state)
      (case (first instr)
         (skip  state)
         (assign  (put (second instr) (m-expression (third instr) state) state)
         (compound  (m-compound (rest instr) state))
         (loop  (if (m-expression (second instr) state)
    	    (m-instruction (third instr) state)
    	    state))
         (conditional  (if (m-expression (second instr) state)
    	    (m-instruction (third instr) state)
                (m-instruction (fourth instr) state))
         (otherwise  nil)
    ) )
    

    1. In case assign why is m-expression called?

    2. Explain the logic behind case assign?

    3. What is the meaning of (skip ((x 1) (y 2) (z 3)))?

    4. In case loop what is (second instr)?

    5. Explain why m-compound is defined as a separate function?

  5. [20] Given the following (pseudo) C++ program, show what is printed by the cout statements, if x, y are passed as indicated:
    int  i = 1;
    int  a[4] = {0, 3, 5, 7};
    
    void P (int x, int y) {
    	x = x + 1;
    	y = y + 1;
    	if (i == x) 
    		x = x + 1;
    	cout << x << y;             // <=====
    }
    
    void main ( ) {
    	P (i, a[i]);
    	cout << i << a[0] << a[1] << a[2] << a[3];        // <===== 
    }
    

    Call by  x   y   i  a[0] a[1] a[2] a[3]
    Value               
    Value-Result               
    Reference               
    Name               


Robert Noonan, noonan@cs.wm.edu
Dec 6, 2001