Pledge of Honor |
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.
}
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.
}