* The grammar for the String inputs that this class was designed to * handle is: *
* The nodes of the parse tree are labelled "AdditiveExpression", * "MultiplicativeExpression", and "PrimaryExpression" following the rules of * the above grammar. The method GetNodeType accesses these labels. *
* Nodes labelled AdditiveExpression will have an additional field labelled * "+", "-", or "" depending on whether this expression is formed by an additive * operator. Similarly, nodes labelled MultiplicativeExpression will have an * additional field labelled "*", "/", or "" depending on whether this * expression is formed by a multiplicative operator. Finally, Nodes labelled * PrimaryExpression will have an additional field labelled "(" if the * expression is a parenthetic expression; otherwise the additional field will * contain the corresponding portion of the input expression. This additional * field can be accessed by the method GetToken. *
* In the event that an AdditiveExpression or a MultiplicativeExpression has * a Token field that is not "", then there will be two subtrees associated * with the node corresponding to the two operands of the operator in the Token * field. The first subtree can be accessed with the method GetLeftSubtree and * the second subtree can be accessed with the method GetRightSubtree. *
* In the event that an AdditiveExpression or a MultiplicativeExpression has * a Token field that is "", then the left subtree contains the parse tree * for the expression. Similarly, if a PrimaryExpression has a Token field * that is "(", then the left subtree contains the parse tree for the expression * inside those parenthesis. *
* source * @version 1.0 18 January 1998 * @author Robert E. Webber * @see ParseTree#GetNodeType * @see ParseTree#GetToken * @see ParseTree#GetLeftSubtree * @see ParseTree#GetRightSubtree */ public class ParseTree { private String TheNodeType; private String TheToken; private ParseTree TheLeftSubtree; private ParseTree TheRightSubtree; /** * primitive constructor for a ParseTree. not intended for general use. * @param TheNodeType is a string representing the grammatical type of this node * @param TheToken is a string providing extra information relating to TheNodeType * @param TheLeftSubtree is the left subtree of the parse tree rooted at the current node. * @param TheRightSubtree is the right subtree of the parse tree rooted at the current node. */ public ParseTree(String TheNodeType, String TheToken, ParseTree TheLeftSubtree, ParseTree TheRightSubtree) { this.TheNodeType = TheNodeType; this.TheToken = TheToken; this.TheLeftSubtree = TheLeftSubtree; this.TheRightSubtree = TheRightSubtree; } /** * BuildAdditiveSubtree is the usual constructor for a ParseTree. * This method builds a parse tree that corresponds to its String * parameter. This parameter is broken into symbols using * MyStringTokenizer. Spaces are used to delimit symbols. * * @param TheText is the String to be converted * @see MyStringTokenizer */ static public ParseTree BuildAdditiveSubtree(String TheText) { MyStringTokenizer TheStringTokenizer = new MyStringTokenizer(TheText); return BuildAdditiveSubtree(TheStringTokenizer); } /** * This is an internal routine used to process the portion of the * grammar corresponding to the rules: *
* NOTE: This is the only method of the series * BuildAdditiveSubtree, BuildMultiplicativeSubtree, and * BuildPrimarySubtree that actually consumes tokens from * TheStringTokenizer. As such, not only does it consume the token * that corresponds to the primary expression, but it also consumes * the token immediately after it, thus setting things up so that * the other methods can access the appropriate information via * GetCurrentToken in MyStringTokenizer. * * @param TheStringTokenizer is a string tokenizer holding the input to be processed. * @see MyStringTokenizer */ static private ParseTree BuildPrimarySubtree(MyStringTokenizer TheStringTokenizer) { ParseTree TheLeftSubtree = null; ParseTree TheRightSubtree = null; String TheToken = ""; if (TheStringTokenizer.hasMoreTokens()) { TheToken = TheStringTokenizer.nextToken(); if (TheToken.equals("(")) { TheLeftSubtree = BuildAdditiveSubtree(TheStringTokenizer); // if (TheStringTokenizer.hasMoreTokens()) { // TheStringTokenizer.nextToken(); // } } if (TheStringTokenizer.hasMoreTokens()) { TheStringTokenizer.nextToken(); } return new ParseTree("PrimaryExpression", TheToken, TheLeftSubtree, TheRightSubtree); } else { return null; } } /** * This method is used to access the syntactic type of this parse * tree. * @return one of "AdditiveExpression", "MultiplicativeExpression", or "PrimaryExpression" */ public String GetNodeType() { return TheNodeType; } /** * This method is used to get portions of the input string that are * important to defining the semantics of the parse tree. * @return a String */ public String GetToken() { return TheToken; } /** * This method is used to get the subtree corresponding to the first * nonterminal in the grammar rule for the current node's type. * @return a ParseTree */ public ParseTree GetLeftSubtree() { return TheLeftSubtree; } /** * This method is used to get the subtree corresponding to the second * nonterminal in the grammar rule for the current node's type. * @return a ParseTree */ public ParseTree GetRightSubtree() { return TheRightSubtree; } /** * Internal information relating to the display area used to show * the parse tree. TheGraphicsComponent is the display area to * be used. TheHeightOfACharacter is the height of a character * in the current font of TheGraphicsComponent. TheWidthOfThreeSpaces * is the width of three spaces in the current font of * TheGraphicsComponent. The value of these variables is set by * the method Display and then used by the method DisplaySubtree. * @see ParseTree#Display * @see ParseTree#DisplaySubtree */ private Graphics TheGraphicsComponent; private int TheHeightOfACharacter; private int TheWidthOfThreeSpaces; /** * An internal routine that walks the parse tree and displays it * indented like an outline. It makes use of the internal variables * TheGraphicsComponent, TheHeightOfACharacter, and * TheWidthOfThreeSpaces. This method is invoked by Display, which * also sets up these internal variables. * @param TheCurrentWidthOffset is how far we are currently indented. * It is a multiple of TheWidthOfThreeSpaces. * @param TheCurrentHeightOffset is the vertical height where the * current line can be printed. * @param TheParseTree is the tree to be displayed * @return the vertical height that the next output can be printed at. * This value is a multiple of TheWidthOfThreeSpaces. * @see ParseTree#Display */ private int DisplaySubtree(int TheCurrentWidthOffset, int TheCurrentHeightOffset, ParseTree TheParseTree) { if (TheParseTree == null) { return TheCurrentHeightOffset; } TheGraphicsComponent.drawString(TheParseTree.GetToken() + " <" + TheParseTree.GetNodeType() + ">", TheCurrentWidthOffset, TheCurrentHeightOffset); TheCurrentWidthOffset += TheWidthOfThreeSpaces; TheCurrentHeightOffset += TheHeightOfACharacter; TheCurrentHeightOffset = DisplaySubtree(TheCurrentWidthOffset, TheCurrentHeightOffset, TheParseTree.GetLeftSubtree()); return DisplaySubtree(TheCurrentWidthOffset, TheCurrentHeightOffset, TheParseTree.GetRightSubtree()); } /** * This method is used to display the current parse tree in outline * format * @param TheGraphicsComponent is the region of the screen where the * parse tree is to be displayed. */ public void Display(Graphics TheGraphicsComponent) { this.TheGraphicsComponent = TheGraphicsComponent; TheHeightOfACharacter = TheGraphicsComponent.getFontMetrics().getHeight(); TheWidthOfThreeSpaces = TheGraphicsComponent.getFontMetrics().stringWidth(" "); DisplaySubtree(0, TheHeightOfACharacter, this); } }