Module Design: Command Object

Version: 1.0.1, April. 23, 1998.

Maintained by: Darrah Chavey.

Changes from Previous Versions: Items marked updated or new under: TokenType description, Parse algorithm for handling errors, and errors generated by the Parse() method.

private class Token {

Private Data:

TokenType: an enumerated value chosen from the following list: P, Q, R, S, NEXT, PREV, DATA, IF, NEW, DELETE, NULL, INT_NODE, STR_NODE, LEFT_PAREN, RIGHT_PAREN, ASSIGN, SEMI_COLON, EQUAL, NOT_EQUAL, GREATER, LESS, GREATER_EQUAL, LESS_EQUAL, AND, OR, NOT, ARROW, NUMBER_LITERAL, STRING_LITERAL, BOOLEAN_LITERAL, NODE_VALUE.
Most of these values are direct translations of equivalent characters or character sequences in an input command (see "Parse" for more detail). The last two values exist only for intermediate calculations.
UPDATED: "NODE_VALUE" is used for keeping track of the actual node currently being manipulated. The "Parse()" method never generates such a token; instead it is generated by the evaluate procedure to keep track, for example, of which node is represented by the expression "p->next", and that one is used to determine the node represented by "p->next->prev", etc. In all cases, the token value notes that this token is a node, but a pointer to the actual node is stored in "theNode".
There is no current use for accepting a boolean literal ("true" or "false") in an input command, and the specifications do not allow it. Nevertheless, it would be easy to extend the command object to allow this. This might be of some value if we accepted a "break" statement in a loop, since there would then be reason to allow a loop such as "while (true) ...".

String Literal: a string of length three which stores the literal value for the three "Literal" types of tokens. True and false are stored as the strings "tru" and "fal" respectively.
Node theNode: For tokens of type NODE_VALUE, this stores (a pointer to) the actual node being referred to by the token.
char NodeField: This will be one of the following values: 'L', for a left (or next) pointer field, 'R' for a right (or prev) pointer field, 'D' for the data field, or '?' for undetermined.

*/

Methods:

None.

};

 

public class Command {

private Token Tokens[50]: An array of 50 "token" objects.

private short NumberOfTokens: How much of the array of tokens is actually in use.

private Command ThenStatement, ElseStatement: Two subordinate commands objects, which are usually null, but which will hold the two subordinate statements for an "if-else "statement, or one such statement for an "if" statement.

public boolean Parse( String toParse );
Overview:
The method "Parse" takes an input string containing a C++ statement and encodes it in a series of tokens in the data array "Tokens". This string may be an assignment statement, a "new" or "delete" statement, an if or if-else (with the subordinant statements contained inside the if-else), or a boolean condition, but it is not a loop. "Chained" assignments such as p = q = NULL are not accepted.
Parameters:
The string "toParse" contains the C++ statement that is to be analyzed.
Pre-Conditions:
1) The calling object has correctly decomposed the lines of text entered in loop input into individual statements. Thus the string passed in is either a full statement or a full boolean expression. (A statement entered into the loop window on multiple lines must be combined before being sent in.)
2) The calling object has done the equivalent of converting a "for" loop into the constituent pieces that make it equivalent to a while loop. No other provision is made here for processing the compound statement controlling a "for" loop.
3) The input statement is limited to one of the types of C++ statements outlined in the requirements document, §4.12.
4) A boolean expression must be surrounded by parenthesis. Thus the boolean that controls a loop, which is entered without parentheses, must have those parentheses added before the string is passed in here.
Post-Conditions:
1) If the input statement was a correctly phrased assignment statement, "new" or "delete" statement, or a boolean condition, then all of the statement will have been converted into a continuous sequence of tokens representing the statement passed in, and the data elements ThenStatement and ElseStatement will be nil.
2) If the input statement was a correctly phrased "if" statement, then all of the subordinate "then" clause will be encoded in the command object "ThenStatement", the rest of the statement (including the word "if" and the boolena expression) will be encoded in "Tokens", and "ElseStatement" will be nil.
3) If the input statement was a correctly phrased "if-else" statement, then all of the subordinate "then" clause will be encoded in the command object "ThenStatement", all of the subordinate "else" clause will be encoded in the command object "ElseStatement", the word "else" will have been discarded, and the rest of the statement (including the word "if" and the boolena expression) will be encoded in "Tokens".
4) The number of tokens stored in the "Tokens" array will be recorded in NumberOfTokens, hence Tokens[NumberOfTokens] will be the first unused element of that array.
5) If one of the error conditions listed below is detected, an error message will be sent to the "Error" object, the Tokens array will be cleared, and the value of NumberOfTokens will be set to 0.
Algorithm:
The Parse method analyzes the string one character at a time (from the start) and decomposes it into "tokens", which are stored in the internal Token array. When an alphabetic character is seen in the string, the next characters are scanned to see what word they represent (if any). Substrings such as "data" are converted into corresponding single enumerated values. "left" and "right" are converted into the NEXT and PREV enumerated values, after checking that they are legal link values based on the type of node in use. When the characters -, !, <, >, =, |, or & are seen, the character following is inspected to see if it forms a 2 character operator (->, !=, <=, >=, ==, ||, or &&) a one character operator (!, <, >, or =). When a " character is seen, the string is scanned for a string literal, whose length is verified and, when acceptable, stored in the literal field. If a digit character is seen, the string is scanned for a number literal, which is then placed in the literal field (padded out with nul characters if necessary).
NEW: In these last two situations, reading a number or string literal, the established nodetype in the MasterNode object is checked to verify that this type of literal is acceptable.
If the string represents an if or if-else statement, the corresponding statements are separated, the subordinate command objects are initialized, and the subordinate commands are given their statements to parse.
Interactions with Other Objects:
1) It needs to ask someone for the type of node currently in use (singly linked, doubly-linked, or tree) in order to determine which link names are legal. This is probably the Master Node object, but at present there is no method available from any object to give this information.
Error Conditions:
This method will check for and report the following types of errors:
1) Illegal link type­if they used next, prev, left, or right when those link names were inappropriate;
2) Unknown identifier­for any alphabetic substring detected not corresponding to a known word;
3) Mismatched parentheses;
4) Assignment statement inside a boolean expression (when checking for mismatched parentheses, if it sees an assignment operator when the LParen count is higher than the RParen count). (This check requires pre-condition #4.)
5) Incomplete statement or missing semi-colon, if the expression did not begin with a Left Paren (in which case it must be a boolean expression) and did not end with a semi-colon.
NEW:
6) If there are illegal characters, or characters that form no acceptable token, in the input stream, and error message is given.
7) If a string literal is read when the NodeType is set to numeric data, or vice versa, an appropriate error message is given.
Return Value:
If no error condition is detected, "true" is returned. If an error condition is detected (and handled), "false" will be returned.

 

public boolean Evaluate( void );
Overview:
The Tokens stored in the Tokens array are processed like an interpreter. If they form an acceptable statement, they are executed. If they form an acceptable boolean expression, the expression is evaluated and the value returned. If they do not form an acceptable statement or expression, an exception is thrown.
Parameters:
None.
Pre-Conditions:
1) A C++ statement or boolean expression has been parsed and placed in the Tokens array.
2) NumberOfTokens >= 3. (The smallest legal statement is "delete p;")
Post-Conditions:
1) If the Tokens array represented a correct C++ statement, according to the constraints of requirements document §4.12, then that statement will have been executed, and the appropriate changes will have occured to the Node, Link, Line, Master Node, Master Link, and Master Line objects. (No redraw will be called, hence these changes may not yet propogate to the screen display.)
2) If the Tokens array represented a correct C++ boolean expression, according to the constraints of requirements document §4.12, then the value of that expression will be returned, and no changes will occur to any other objects or to the screen display.
3) If the Tokens array do not represent a correct C++ statement or boolean expression, then no changes will occur to any other objects or to the screen display, and a "SyntaxErrorException" will be thrown.
Algorithm:
We read the tokens from the Tokens array one at a time (starting from 0), pushing them on a stack, or taking an action, depending on the token we have just read. In the description below, the phrase "Verify" means to check if something is true, to throw an exception if it is false, and to continue processing if it is true. The phrase "Pop X" means to pop the last token off the stack, verify (in the sense just described) that it has TokenType X, and store it in a local variable "CurrentToken", discarding any previous value there. The phrase "Pop into Operator" means to pop the last token off the stack, but to place it into a second local variable "Operator", leaving the value of "CurrentToken" unchanged. The phrase "Read the next token" means to read the current token from the Token array into "NewToken", and advance the counter keeping track of the active location in the Token array.
The main algorithm is a loop that runs through each token in the Token array and takes the following action, depending on the TokenType of that token:
switch ( TokenType ) {
On P, Q, R, S: Push a NODE_VALUE token where theNode is set to p, q, r, or s respectively. Set NodeField to 'R'.
On ARROW: Pop a NODE_VALUE token. Verify that NodeField is 'R' or 'L'. Ask theNode for its Next or Prev node (as appropriate). Verify this is a legal node (depends on how Node object ends up handling these calls for invalid pointers). Put that Node into theNode, set NodeField to '?', and push this token.
On NEXT, PREV, DATA: Pop a NODE_VALUE token. Verify that NodeField is '?'. Set NodeField to 'R' for NEXT, 'L' for PREV, or 'D' for DATA. Push the token.
On IF, NEW, DELETE, NULL, LEFT_PAREN, ASSIGN, EQUAL, NOT_EQUAL, GREATER, LESS, GREATER_EQUAL, LESS_EQUAL, AND, OR, NOT, NUMBER_LITERAL, STRING_LITERAL: Push the token.
// If we added "BOOLEAN_LITERAL" to acceptable inputs, it would go here also.
On INT_NODE, STR_NODE: Push the token. Read the next token. Verify it is a SEMI_COLON. Verify we're at the end of the TokenArray. Pop the (INT_NODE, STR_NODE) token. Pop NEW. Pop ASSIGN. Pop NODE_VALUE. Verify the stack is empty. Call MasterNodeObject.NewNode( CurrentToken.theNode ). Use the return value from this call for either CurrentToken.theNode.SetNext() or SetPrev() as appropriate.
On RIGHT_PAREN:
LOOP: Pop either a NODE_VALUE token or one of the LITERAL tokens (including "NULL"). Pop into "Operator". The next step depends on the type of this operator:
switch (Operator.TokenType) {
LEFT_PAREN: Push the CurrentToken. Done processing (break).
NOT: Verify the CurrentToken is BOOLEAN_LITERAL, invert its literal value, and push it.
AND, OR: Verify CurrentToken is BOOLEAN_LITERAL. Pop BOOLEAN_LITERAL. Calculate new literal value and Push it.
GREATER, LESS, GREATER_EQUAL, LESS_EQUAL, EQUAL, NOT_EQUAL:
Pop into another local variable either a NODE_VALUE token or one of the LITERAL tokens. Verify that the type of this token is compatible with the one in CurrentToken. Calculate the value of this boolean expression, calling such methods as Node.GetNext(), Node.GetPrev(), and Node.GetData() to get the actual values of the left and right sides of the operand. Push the resulting boolean literal.
ASSIGN: Throw IllegalAssignmentException. (Should be caught by the Parser?)
Otherwise: Throw SyntaxErrorException.
}
Except for those two cases that were indicated as "Done processing", we should continue looping on this case, as implied above. When done, check the stack size. If only one item on it, we are evaluating a boolean expression, so return the appropriate value. If the stack size is 1, Pop an IF token, then call ThenStatement.Execute() or ElseStatement.Execute() as appropriate.
On SEMI_COLON: Verify we're at the last token in Tokens. Pop into "Operator". The next step depends on the type of this operator:
switch (Operator.TokenType) {
DELETE: Call MasterNode.DeleteNode(). Somehow find a way to set all pointers that used to point to this node to "Uninitialized" values.
ASSIGN: Pop into another local variable a NODE_VALUE token. Verify that the type of this token is compatible with the one in CurrentToken. If CurrentToken is a NODE_VALUE, use Node.GetNext(), Node.GetPrev(), or Node.GetData() to get the actual value to assign, otherwise, use the Literal. Use Node.SetNext(), Node.SetPrev(), or Node.SetData() to update the data for the newly popped NODE_VALUE. Call the appropriate DeleteLink() and MakeLink() routines to erase any previous lnk n ocrae e new ones.

}
Interactions with Other Objects:
1) "On ARROW", we call Node.GetNext() and Node.GetPrev().
2) "On INT_NODE, STR_NODE" calls MasterNodeObject.NewNode().
3) "On INT_NODE, STR_NODE" calls Node.SetNext() and Node.SetPrev().
4) "On RIGHT_PAREN" calls Node.GetNext(), GetPrev(), GetData(), SetNext(), SetPrev() and SetData().
5) "On SEMI_COLON" calls MasterNode.DeleteNode().
6) "On SEMI_COLON" calls MasterLink.DeleteLink() and MasterLink.MakeLink().
Error Conditions:
This method will check for and report the following types of errors:
1) A syntax error represented within the tokens (including a token string that is too short) will result in a "SyntaxErrorException" being thrown.
2) An attempt to create a new node when there is no room for one will result in a message being sent to the Error object.
3) An attempt to dereference a nil or uninitialized pointer will result in "NilPointerException" or "InvalidPointerException" being thrown.
Return Value:
If the token array represented a statement or represented a boolean expression that evaluated to true, "true" is returned. If the token array represented a boolean expression that evaluated to false, "false" is returned. (If the array represented an illegal statement/expression, an exception will have been thrown and nothing is returned.)

Search engine sitemap created by AutoSitemap.com