Exam #3 - Comp 212

Rice University - Fall 2001

Instructions

  1. The examination is open book/notes.  You are allowed to consult any written materials available under the sun, except code from your current Comp212 classmates.  If your code is based on materials that we did not provide you, just give us the appropriate references.
  2. You are not allowed to discuss the exam in any way with anybody beside the instructors (Nguyen and Wong, but not the labbies) of this course.
  3. Do not post your questions on the newsgroup.  E-mail us, dxnguyen@rice.edu and swong@rice.edu, your questions instead. We  will reply to you directly, and if deemed necessary, we will forward our reply to the newsgroup as well.  We will check our e-mail as often as we can to catch and respond to your questions
  4. Write your code in the most object-oriented way possible, that is with the fewest number of control statements and no checking of the states and class types of the objects involved in any way.
  5. We expect correct Java syntax.
  6. There are 5 questions for a total of  100 points.  Each question should take on the average 30 minutes.  However, you have 5 hours to do the exam.
  7. Submit a hard copy of your exam with all answers in type-written form, except perhaps diagrams (if any) which can be hand-drawn.  Be sure to print your name and sign the honor pledge.
  8. Turn in the exam to Nguyen only.  Send Nguyen an e-mail to notify your submission.  He will reply to confirm your submission.
  9. The deadline for submission is  Dec. 19, 2000 at 5 PM.
Pledge of Honor

I. Recursive Descent Parsing  (see lab #14)

Consider the following grammar for prefix arithmetic expressions.

Arithmetic Expression Grammar Rules

Description

E :: Leaf | BinOp An expression E  is either a Leaf or a BinOp.
Leaf :: VarLeaf | IntLeaf A Leaf is either a VarLeaf or an IntLeaf
VarLeaf :: id A VarLeaf is an id, where id is a token representing a variable.
IntLeaf :: int An IntLeaf is an int, where int is a token representing an integer.
BinOp :: AddOp | MulOp A BinOp is either an AddOp or a MulOp
AddOp :: ( + E E ) An AddOp is a left parenthesis token,  followed by a plus token, followed by an expression E, followed by another expression E, followed by a right parenthesis token.
MulOp :: ( * E E ) An MulOp is a left parenthesis token,  followed by a star token, followed by an expression E, followed by another expression E, followed by a right parenthesis token.

 

An example for such an expression is: (* 34 (+ xyz 7)), where

The tokens of the above grammar can be implemented using the visitor pattern.  

public abstract class AToken {
    protected String _lexeme; // String representing the token.
    protected AToken(String lexeme);
    public String getLexeme() { return_lexeme;}
    public Object abstract execute(ATokVisitor v, Object inp);
}

/**
* Represents the id token.
*/
public class IdToken extends AToken{
    public IdToken(String s) {
        super(s);
    }
    public Object execute(ITokVisitor v, Object inp) {
        return v.idCase(this, inp);
    }
}

// Other concrete token classes, etc.

public abstract class ATokVisitor {
    /**
    * This is the case when the host is a concrete IdToken.
    * Throws an IllegalArgumentException as default behavior.
    * @param host a concrete IdToken.
    * @param inp the input needed for this ATokVisitor to perform its task.
    */
    public Object idCase(IdToken host, Object inp) {
        throw new IllegalArgumentException("Wrong token!");
    }
    // etc..., a method for each concrete token case.
}

1. Use the example of the IdToken class given in the above, write a concrete subclass of AToken to represent each of the remaining tokens in the above grammar.  15 points

2. Based on the answer to question 1, write all the methods for the abstract class ATokVisitor given in the above.  Throw an IllegalArgumentException in all the methods.  This is the default behavior of all tokens.   10 points

3. A tokenizer is an object that knows how to scan an input stream and extract the appropriate tokens for a given grammar, one token at a time.  Write the code for a tokenizer class specified in the following.  25 points

/**
* Extracts and returns an appropriate AToken from some given source.
*/
interface ITokenizer (
    public AToken getNextToken();
}

/**
* Uses the StreamTokenizer provided by in java.io to scan an input
* stream and extract an appropriate AToken.
*/
public class StreamTokenizerWrapper implements ITokenizer {
    private StreamTokenizer _st;

    /**
    * Initializes _st to read from a input Reader file with the given
    * input file name.
    * @param inputFileName the name of the input text file.
    public StreamTokenizerWrapper(String inputFileName) {
    // Students to write code.
    }

    /**
    * Uses _st to scan the input, extracts, and returns an appropriate
    * concrete AToken.
    * Throws an exception if an illegal input is encountered.
    */
    public AToken getNextToken() {
    // Students to write code.
    }
}

4. Write a recursive descent parser as specified in the following.  This parser

 

/**
* Abstract factory to produce abstract syntax tree IAST.
*/
interface
IASTFactory {
    public IAST makeAST(); 
}

/**
* Recursive descent parser to scan input text and produce an IAST.
* Note the one-to-one correspondence between the non-terminal symbols
* of the grammar and the methods of the parser.
* Also, there is a one-to-one correspondence between the non-terminal
* symbols of the grammar and the classes in the object model for 
* abstract syntax trees.
* Throws an Exception when an illegal input is encountered.
*/
public class RdpASTFactory implements IASTFactory {
    private AToken _currentTok; //the current token object.
    private ITokenizer _tokenizer:
    public RdpASTFactory(ITokenizer tokenizer) { _tokenizer = tokenizer;}

    /**
    * Parses input and returns an IAST.
    */
    public IAST makeAST() { 
    // Students to write code; use anonymous inner class for ATokVisitor
    }

    /**
    * Parses input and returns an ILeaf.
    */
    protected IAST makeLeaf() { 
    // Students to write code; use anonymous inner class for ATokVisitor
    }

    /**
    * Parses input and returns a ABinOp.
    */
    protected IAST makeBinOp() { 
    // Students to write code; use anonymous inner class for ATokVisitor
    }

    /**
    * Parses input and returns an IntLeaf.
    */
    protected IAST makeIntLeaf() { 
    // Students to write code; use anonymous inner class for ATokVisitor
    }

    /**
    * Parses input and returns a VarLeaf.
    */
    protected IAST makeVarLeaf() { 
    // Students to write code; use anonymous inner class for ATokVisitor
    }

    /**
    * Parses input and returns an Add.
    */
    protected IAST makeAddOp() { 
    // Students to write code; use anonymous inner class for ATokVisitor
    }

    /**
    * Parses input and returns a Multiply.
    */
    protected IAST makeMulOp() { 
    // Students to write code; use anonymous inner class for ATokVisitor
    }

    // Students are free to add any other non-public methods.
}

II. Sorting Framework

Consider the following technique for sorting called "Sink Sort" .

Initially:  4 5 1 3 2 ("top" is on the left at index 0, "bottom" is on the right at index 4)

Split all the array into one element arrays:  4  5  1  3  2

2 is already sorted:         4  5  1  3  2

Sink 3 until at right of 2:  4  5  1  2 3

Sink 1-already there :   4  5  1 2 3

Sink 5 until at right of 3: 4  1 5 2 3

                   4 1 2 5 3

                   4  1 2 3 5

Sink 4 until at right of 3: 1 4 2 3 5

                   1 2 4 3 5

                   1 2 3 4 5

Basically the idea is that the next number is "sunk" by swapping places with its adjacent number on the right until it is smaller than the number to its right.  According to Merritt's split-sort-sort-join model of sorting, Sink sort is an easy split/hard join algorithm.  The code for split is simply:

protected int split(Object[] A, int lo, int hi){
    return (lo + 1);
}

5. Write the code for the join method of Sink sort as described in the above.  25 points

/**
* Given A[lo..s-1] and A[s..hi] sorted, 
* merges the two sub-arrays so that A[lo..hi] is sorted.
* Here s == lo + 1 (see split).
* The merge should be done in such a way that the numbers in A[lo..s-1]
* sink by swapping places with their adjacent right neighbors until each
* is smaller than the number to its right.  
*/

protected void join(Object[] A, int lo, int s, int hi){
    // Students to write code.
}

Notes: