In either case, send me (dxnguyen@rice.edu) an e-mail to notify your submission. I will reply to confirm your submission.
| Pledge of Honor |
Consider the following grammar rules to generate "sentences" consisting of terminal symbols a, b, c.
|
Grammar Rules |
Description |
S :: X Y |
S is the start symbol. S is X followed by Y. |
X :: c | A |
X is either c or a followed by X, where a and c are terminal symbols. |
|
|
Y :: B | X |
Y is b followed by Y or X, where b is a terminal symbol. |
|
|
Here are a few examples of "sentences" generated by the above grammar rules.
The above grammar can be modeled by the following object structure (click here to download the source code: grammar.jar).
The main purpose of the following group of questions is to scan input text files consisting of characters such as 'a', 'b' and 'c' and build the corresponding S object. The technique described in the following falls into the category of parsing called recursive descent parsing. The parser here differs slightly from the one done in lab #11 of week 12, in that instead of maintaining a current token, it gets the next token from the tokenizer at the appropriate time, passes the token around and let the token drive the control flow. As a result, one can say that the parser described here is more object-oriented than the one done in lab #11 of week 12.
Analogous to the grammar for Scheme arithmetic expressions done in lab #11, the tokens of the above grammar can be implemented using the visitor pattern.
public abstract class AToken {
private String _lexeme; // String representing the token.
protected AToken(String lex) {_lexeme = lex;}
public String toString() { return _lexeme;}
public Object abstract execute(ATokVisitor v, Object inp);
}
public class TokenA extends AToken{ // represents
the a token.
// students to write code.
}
public abstract class ATokVisitor {
/**
* This is the case when the host is a concrete TokenA.
* @param host a concrete token.
* @param inp the input needed for this ATokVisitor to perform
its task.
* @exception IllegalArgumentException thrown as default behavior.
*/
public Object caseA(TokenA host, Object inp) {
throw new
IllegalArgumentException("Wrong token: " + host);
}
// etc..., student to write a method for each concrete token case.
}
1. (10 points) Write a concrete subclass of AToken to represent each of the remaining tokens in the above grammar.
2. (10 points) 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.
3. (20 points) 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.
/**
* 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 for the above grammar.
*/
public class TokenizerABC 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 TokenizerABC(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. (35 points) Write a recursive descent parser as specified in the following. This parser
/**
* Abstract factory to produce an S object.
*/
interface ISFactory {
public S makeS();
}
/**
* Recursive descent parser to scan input text and produce an S object.
* Throws an Exception when an illegal input is encountered.
*/
public class RDPSFactory implements ISFactory {
private ITokenizer _tokenizer;
public RDPSFactory(ITokenizer tokenizer) { _tokenizer =
tokenizer;}
private AToken nextToken() { return
_tokenizer.getNextToken(); }
/**
* Parses input and returns an S.
*/
public S makeS() {
// Students to write code;
// Hint: what do you need to make first before you can make
S?
}
/**
* Given the current token tok, parses input and returns an
AX.
* @param tok the current token in the token stream.
*/
private AX makeX(AToken tok) {
// Students to write code;
// If needed, use anonymous inner class for ATokVisitor
}
/**
* Parses input and returns an AY, given a current token tok.
* @param tok the current token in the token stream.
*/
private AY makeY(AToken tok) {
// Students to write code;
// If needed, use anonymous inner class for ATokVisitor
}
/**
* Parses input and returns an A, given a current token tok.
* @param tok the current token in the token stream.
*/
private A makeA(TokenA tok) {
// Students to write code;
// If needed, use anonymous inner class for ATokVisitor
}
/**
* Parses input and returns a B, given a current token tok.
* @param tok the current token in the token stream.
*/
private B makeB(TokenB tok) {
// Students to write code;
// If needed, use anonymous inner class for ATokVisitor
}
/**
* Returns a C, given a current token tok.
* @param tok the current token in the token stream.
*/
private C makeC(TokenC tok) {
// Students to write code;
// If needed, use anonymous inner class for ATokVisitor
}
// Students are free to add any other non-public methods.
}
Here is an example of a client of the parser.
/**
* Test can be run via: java RdpClient inputFileName
*/
public class RdpClient {
/**
* Does the test.
* @param inFile name of input file
*/
public void test(String inFile) {
TokenizerABC tokenizer = new TokenizerABC(inFile);
ISFactory fac = new RDPSFactory(tokenizer);
System.out.println("Sentence= '" + fac.makeS() +"'");
}
/**
* Gets called by the JVM.
* @param arg[0] the input file name.
*/
public static void main(String arg[]) {
new RdpClient().test(arg[0]);
}
}
5. (10 points) Make appropriate changes to our object model of the grammar to support the visitor pattern; specifically, write the Java code for the interface and abstract and concrete method definitions necessary to support visitors. Feel free to add code to the classes that are provided to you in grammar.jar.
6. (15 points) The diagram below illustrates special operations on binary trees called left rotation and right rotation. These operations are inverses of each other. These operations are commonly used on binary search trees (BST) because they maintain the BST property of the trees. Write a visitor called RightRotation to perform a right rotation on a BiTree host. The visitor should not create any new tree; instead it should mutate the host as illustrated in the figure.
