/* * parseTree.java * * Created on 1 december 2005, 9:35 * */ package DOPParser; /** * * @author gideon */ import java.util.*; public class parseTree { private ArrayList associatedNodes; public int deepestLevel = 0; protected double parseProbability; /** * Creates a new instance of parseTree */ public parseTree() { this.associatedNodes = new ArrayList(); //add TOP rule Node topNode = new Node("TOP", null); topNode.setType(Main.NONTERMINAL); topNode.setDepth(0); this.associatedNodes.add(topNode); } //this constructor is for reading in rules from an external grammar and converting them to CNF public parseTree(String myLHS) { this.associatedNodes = new ArrayList(); //add TOP rule Node topNode = new Node(myLHS, null); topNode.setType(Main.NONTERMINAL); topNode.setDepth(0); this.associatedNodes.add(topNode); } /** * add a rule of the form X->YZ to nonTerminal */ public void addNode(Node myNode){ this.associatedNodes.add(myNode); //return this.associatedNodes.size() - 1; } public void removeNode(int nrNode){ this.associatedNodes.remove(nrNode); } public Node getNode(int nrNode){ //todo: error if nrNode > totalRules //int totalRules = this.associatedNodes.size(); //System.out.println("nonTerminal= " + this.getName() + "; totalRules= " + totalRules + "; nrNode=" + nrNode); //assert(nrNode>0 && nrNode < totalRules); ??? werkt niet return this.associatedNodes.get(nrNode); } public ArrayList getNodes(){ return this.associatedNodes; } public double getProbability(){ return this.parseProbability; } public void setProbability(double myProbability) { this.parseProbability = myProbability; } /** This function transforms the grammer to the CNF. * *enumerate nodes vd parseTree *maak nwe parseTree en schrijf ondertussen nieuwe nodes daarnaartoe met nwe indices *check of node in CNF staat *indien unary doe dan zoals boven *zoniet, scheidt eerste child van andere children *als eerste child terminal dan maak je nwe nonTerminal, met als child de terminal *als rest single nonTerminal *als rest single Terminal, maak dan je nwe nonTerminal, met als child de terminal *als rest meer dan een symbool, maar dan nwe nonTerminal, en maak deze child en de rest worden *children vd nieuwe */ public void transformToCNF(){ //System.out.println("in transformToCNF"); //you need to store the new nodes aside, before you can add them to parseTree ArrayList tempNodeStore = new ArrayList(); for (Iterator it = this.associatedNodes.iterator(); it.hasNext(); ) { Node myNode = it.next(); int nrOfChildNodes = myNode.getChildNodes().size(); //don't bother with unary productions here, only after you have converted this node to CNF format //you check if this node is single child of the parent if (nrOfChildNodes >= 2) { /* //controle StringBuffer testNode = new StringBuffer(); testNode.append(myNode.getName()).append("-->"); for (Node myChildNode : myNode.getChildNodes()) { testNode.append(myChildNode.getName()).append(" + "); } System.out.println("controle: node=" + testNode.toString()); */ //first, replace all terminal nodes by nonterminal nodes, and append terminals on them int nrChildNode = 0; for (Node myChildNode : myNode.getChildNodes()) { if (myChildNode.getType()==Main.TERMINAL){ //create new node String newNodeName = "X_" + Node.newNodeIndex++; //XXX ??? to think about Node newNode = new Node(newNodeName, myNode); newNode.setType(Main.NONTERMINAL); //add terminal node as a child to this one newNode.addChildNode(myChildNode); //this.addNode(newNode); tempNodeStore.add(newNode); //replace parent in terminal node myChildNode.replaceParentNode(newNode); //replace terminal node by new node in parent node myNode.replaceChildNode(nrChildNode, newNode ); //myNode.addChildNode(newChildNode); } nrChildNode++; } //now, all nodes are nonterminals, now recursively remove one nonterminal and descend one level //untill there are exactly 2 children left Node tempNode = myNode; while (nrOfChildNodes > 2) { //create new node String newNodeName = "X_" + Node.newNodeIndex++; //String newNodeName = tempNode.getName() + "_X"; //XXX ??? think about this: //tempNode = parent Node newNode = new Node(newNodeName, tempNode); newNode.setType(Main.NONTERMINAL); //iterate over children, put all but first child in new node (and parent), remember first child int i = 0; Node firstChild = tempNode.getChildNodes().get(0); for (Node myChildNode : tempNode.getChildNodes()) { if (i>0) { newNode.addChildNode(myChildNode); //replace parent in terminal node myChildNode.replaceParentNode(newNode); } i++; } //this.addNode(newNode); tempNodeStore.add(newNode); //remove all children from original, then put first child and new node in it tempNode.removeAllChildNodes(); tempNode.addChildNode(firstChild); tempNode.addChildNode(newNode); //descend to child and recompute nrOfChildNodes nrOfChildNodes = newNode.getChildNodes().size(); tempNode = newNode; } } //if (nrOfChildNodes>=2) //remove unary rules: look at parent and check if this one is single child //if it is, move all its children to the parent and delete this one //check whether the current rule is not a unary rule, if so, remove it, //and update children of parent node (TOP is allowed to be unary) if (!myNode.getName().equals("TOP") && (myNode.getParentNode()!=null)) { if (myNode.getType()==Main.NONTERMINAL && myNode.getParentNode().getChildNodes().size()==1 && !(myNode.getParentNode().getName().equals("TOP"))) { //remove this child from parent node and put all children of this node inside myNode.getParentNode().removeAllChildNodes(); for (Node myChildNode : myNode.getChildNodes()) { myNode.getParentNode().addChildNode(myChildNode); //replace pointer to parent nodes in children myChildNode.replaceParentNode(myNode.getParentNode()); } //remove this node from parseTree //System.out.println("node removed "); it.remove(); } } } //iterator mynode //only now you may add new nodes to parsetree this.associatedNodes.addAll(tempNodeStore); } public void transformBackToCFG(){ //identify all CNF nodes by their name, and remove/collapse them //first move all the children of the CNF node to the parent node //work bottom-up, start with deepest level and climb up the tree for (int currentDepth = this.deepestLevel; currentDepth >=0; currentDepth--) { for (Iterator it = this.associatedNodes.iterator(); it.hasNext(); ) { Node myNode = it.next(); if (myNode.getDepth() == currentDepth) { if (myNode.getName().contains("X_")) { //System.out.println("remove node " + myNode.getName()); for (Node myChildNode : myNode.getChildNodes()) { //System.out.println("parent= " + myNode.getParentNode().getName()); //myNode.getParentNode().addChildNode(myChildNode); //replace pointer to parent nodes in children myChildNode.replaceParentNode(myNode.getParentNode()); } //remove reference to this node in parent and get its index int myIndex =0; for (Iterator it2 = myNode.getParentNode().getChildNodes().iterator(); it2.hasNext(); ) { //Node myParentsChildrenNode = it2.next(); //XXX FOUT als er meerdere children met zelfde naam zijn!!! kijk naar equals method //LHS, getLeftSpan, rightSpan en ChildNodes moeten gelijk zijn!!! //if (myParentsChildrenNode.getName().equals(myNode.getName()) && myParentsChildrenNode.getChildNodes().equals(myNode.getChildNodes()) && myParentsChildrenNode.getLeftSpan() ==myNode.getLeftSpan() && myParentsChildrenNode.getRightSpan()==myNode.getRightSpan()) { if (it2.next().equals(myNode)) { myIndex = myNode.getParentNode().getChildNodes().indexOf(myNode); //TEMP solution if (myIndex == -1) System.out.println("BUG!!! index=-1 for ParentNode=" + myNode.getParentNode().getName() + "; child Node=" + myNode.getName() + "; index=" + myIndex); it2.remove(); } } //add all its children to the parent node and insert in the same position where the CNF was //TEMP solution //if (myIndex != -1) myNode.getParentNode().getChildNodes().addAll(myIndex, myNode.getChildNodes()); //remove the CNF node from parseTree it.remove(); } } } } } public void calculateLabelFrequencies(HashMap labelFrequencies1){ for (Node myNode : this.associatedNodes) { if (myNode.getType()==Main.NONTERMINAL) { if (labelFrequencies1.get(myNode.getName())==null) { labelFrequencies1.put(myNode.getName(), 1); } else labelFrequencies1.put(myNode.getName(), labelFrequencies1.get(myNode.getName()).intValue()+1); } } } public void calculateNodeDepthAndLabelNodes(){ int myDeepestLevel = 0; int iLabel = 0; for (Node myNode : this.associatedNodes) { iLabel++; //recursively find parent node, until you encounter TOP Node tempNode = myNode; int depth = 0; while (!(tempNode.getName().equals("TOP"))) { depth++; tempNode = tempNode.getParentNode(); } myNode.setDepth(depth); myNode.setLabel(iLabel); if (depth>myDeepestLevel) myDeepestLevel = depth; } this.deepestLevel = myDeepestLevel; //if (DO_TREEBANK_COMPARISON) you must set the spans of the fringe nodes, and interpret them as terminals if (Main.DIRECT_EVALUATION_NO_PARSING) { int wordPosition = 0; for (Node myNode : this.associatedNodes) { if (myNode.getChildNodes().size()==0) { wordPosition++; myNode.setType(Main.TERMINAL); //since nodes are assigned from left to right, index indicates word position =span for terminal nodes myNode.setLeftSpan(wordPosition-1); myNode.setRightSpan(wordPosition); } } } } public void calculateSubTrees(){ //start with deepest level and climb up the tree for (int currentDepth = this.deepestLevel; currentDepth >=0; currentDepth--) { //xxxcheck for loop for (Node myNode : this.associatedNodes) { if (myNode.getDepth() == currentDepth) { //node either has a single terminal as child: then nrSubtrees=0 //or it has two nonterminals as children: nrSubtrees= (Aj+1)(Bk+1) //or it is itself terminal if (myNode.getType()==Main.NONTERMINAL){ if (myNode.getChildNodes().size()==1) myNode.setnrSubtrees(0); else myNode.setnrSubtrees((myNode.getChildNodes().get(0).getnrSubtrees()+1) * (myNode.getChildNodes().get(1).getnrSubtrees()+1)); } } } } } public void calculateNodeSpans(){ //start with deepest level and climb up the tree for (int currentDepth = this.deepestLevel; currentDepth >=0; currentDepth--) { for (Node myNode : this.associatedNodes) { if (myNode.getDepth() == currentDepth) { //if node is terminal then span corresponds to word position //if node is nonterminal, then left span is same as for leftmost child, and right span same as for rightmost child if (myNode.getType()==Main.NONTERMINAL){ if (myNode.getChildNodes().size()==0) System.out.println("index out of bounds: " + myNode.getName()); //if (myNode.getChildNodes().size()>0) { myNode.setLeftSpan(myNode.getChildNodes().get(0).getLeftSpan()); myNode.setRightSpan(myNode.getChildNodes().get(myNode.getChildNodes().size()-1).getRightSpan()); //} //System.out.println("Node=" + myNode.getName() + "; Depth=" + myNode.getDepth() + "; leftChild=" + myNode.getChildNodes().get(0).getName() + "; rightChild=" + myNode.getChildNodes().get(myNode.getChildNodes().size()-1).getName()); } //the span of TERMINALS is already entered with the initiation of the Terminal nodes } } } } public void calculateSubTrees_generalized(){ //start with deepest level and climb up the tree for (int currentDepth = this.deepestLevel; currentDepth >=0; currentDepth--) { //xxxcheck for loop for (Node myNode : this.associatedNodes) { if (myNode.getDepth() == currentDepth) { //node either has a single terminal as child: then nrSubtrees=0 //or it has two nonterminals as children: nrSubtrees= (Aj+1)(Bk+1) //or it is itself terminal if (myNode.getType()==Main.NONTERMINAL && myNode.getChildNodes().size()>0){ int nrSubtrees = 1; for (int iChild = 0; iChild < myNode.getChildNodes().size(); iChild++){ nrSubtrees = nrSubtrees*(myNode.getChildNodes().get(iChild).getnrSubtrees()+1) ; } myNode.setnrSubtrees(nrSubtrees); //XXX hebben preterminals 1 of 0 subtrees? //if (myNode.getChildNodes().size()==1 && myNode.getChildNodes().get(0).getType()==Main.TERMINAL) myNode.setnrSubtrees(0); } } } } } public void removeEmptyNonTerminalNodes(){ Node myNode; for (ListIterator it = this.associatedNodes.listIterator(); it.hasNext();) { myNode = (Node) it.next(); //for (Node myNode : this.associatedNodes) { if (myNode.getType() == 2 && myNode.getChildNodes().size()==0) { //2=NONTERMINAL //remove reference in parentnode myNode.getParentNode().getChildNodes().remove(myNode); it.remove(); } } } public boolean doBranchCounting() { boolean hasQuinteryBranches = false; for (Node myNode : this.associatedNodes) { if (myNode.getChildNodes().size()==2) Grammar.nrBinaryBranches++; if (myNode.getChildNodes().size()==3) Grammar.nrTertiaryBranches++; if (myNode.getChildNodes().size()==4) Grammar.nrQuarteryBranches++; if (myNode.getChildNodes().size()==5) { Grammar.nrQuinteryBranches++; hasQuinteryBranches=true; } if (myNode.getChildNodes().size()==6) { Grammar.nrSexteryBranches++; hasQuinteryBranches=true; } } if (hasQuinteryBranches) { Grammar.quinteryBranchSentences.add(this.printToLatex(false, false, "")); return true; //take those sentences out of WSJ_labeled and unlabeled } return false; } public String printToLatex(boolean blnPrintNrSubtrees, boolean blnPrintNodeSpans, String strText){ //go counter-clockwise, start with TOP, find left child //if no child, then go to sister, if no more sister, then go up one level, go to next child //do this until you encounter again the TOP node from the right side, and after you have treated all its children //first set processedChildren of all nodes to 0 for (Node myNode : this.associatedNodes) { myNode.processedChildren = 0; } StringBuffer parseLatexFmt = new StringBuffer(); //rechts van nonterminal: spatie ] //overal moeten spaties voor behalve voor nonterminal moet . //multiwords en Latex commands zoals \ldots moeten in {} Node currentNode = this.associatedNodes.get(0); boolean allChildrenOfTOPProcessed = false; while (allChildrenOfTOPProcessed ==false) { //only write [. first time you enter node if (currentNode.processedChildren==0){ if (currentNode.getType()==Main.NONTERMINAL) parseLatexFmt.append(" [.{").append(currentNode.getName()); else { parseLatexFmt.append(" {"); String terminalName = currentNode.getName(); //remove _ from name, because Latex doesn't like it if (!Main.BRACKET_FORMAT_WSJ_STYLE) { terminalName = currentNode.getName().substring(0, currentNode.getName().length()); } parseLatexFmt.append(terminalName); } //{} for multiwords if (blnPrintNrSubtrees && currentNode.getType()==Main.NONTERMINAL) parseLatexFmt.append(" (" + currentNode.getnrSubtrees() + ")"); if (blnPrintNodeSpans && currentNode.getType()==Main.NONTERMINAL) parseLatexFmt.append(" (" + currentNode.getLeftSpan() + "-" + currentNode.getRightSpan() + ")"); parseLatexFmt.append("}"); } //(s,[(per,[(ik_,[])]),(vp,[(v,[(wil_,[])]),(up,[(mp,[(mp,[(p,[(van_,[])]),(np,[(voorschoten_,[])])]),(mp,[(p,[(naar_,[])]),(np,[(np,[(den,[(den_,[])]),(haag,[(haag_,[])])]),(np,[(np,[(centraal_,[])]),(n,[(station_,[])])])])]),(zp,[(hallo_,[]),(jij_,[]),(rp,[(daar_,[]),(auto_,[])])])])])])]). //if there is an unprocessed child, make it current node and return to start of while-loop if (currentNode.getChildNodes().size()>currentNode.processedChildren) { currentNode = currentNode.getChildNodes().get(currentNode.processedChildren); } //if there are no more unprocessed children, write closing bracket, and mark node as processed with parent else { if (currentNode.getType()==Main.NONTERMINAL) parseLatexFmt.append(" ]"); //System.out.println("nrChildren=" + currentNode.getChildNodes().size() + "; processed=" +currentNode.processedChildren); //System.out.println("current node=" + currentNode.getName()); currentNode.getParentNode().processedChildren++; //go to parent node currentNode = currentNode.getParentNode(); } //check allChildrenOfTOPProcessed if (currentNode.getName().equals("TOP") && currentNode.getChildNodes().size() == currentNode.processedChildren) allChildrenOfTOPProcessed = true; } parseLatexFmt.append(" ]"); /* (s,[(per,[(ik_,[])]),(vp,[(v,[(wil_,[])]),(mp,[(mp,[(p,[(van_,[])]),(np, [(voorschoten_,[])])]),(mp,[(p,[(naar_,[])]),(np,[(np,[(den,[(den_,[])]), (haag,[(haag_,[])])]),(np,[(np,[(centraal_,[])]),(n,[(station_,[])])])])]),(zp,[(hallo_,[])])])])]). */ if (!strText.equals("")) System.out.println("The " + strText + " parse tree is: " + parseLatexFmt.toString()); return parseLatexFmt.toString(); } public String printOVISFormat(boolean blnWithUnderScore){ //go counter-clockwise, start with TOP, find left child //if no child, then go to sister, if no more sister, then go up one level, go to next child //do this until you encounter again the TOP node from the right side, and after you have treated all its children //first set processedChildren of all nodes to 0 for (Node myNode : this.associatedNodes) { myNode.processedChildren = 0; } StringBuffer parseOVISFmt = new StringBuffer(); //(A,[comma-list]) //(mp,[(morgenavond_,[])]). Node currentNode = this.associatedNodes.get(0); boolean allChildrenOfTOPProcessed = false; while (allChildrenOfTOPProcessed ==false) { //only write [. first time you enter node if (currentNode.processedChildren==0){ if (currentNode.getType()==Main.NONTERMINAL) parseOVISFmt.append("(").append(currentNode.getName()).append(",["); else { //terminal parseOVISFmt.append("(").append(currentNode.getName()).append(blnWithUnderScore?"_":"").append(",[])"); } } //OVIS: (s,[(per,[(ik_,[])]),(vp,[(v,[(wil_,[])]),(up,[(mp,[(mp,[(p,[(van_,[])]),(np,[(voorschoten_,[])])]),(mp,[(p,[(naar_,[])]),(np,[(np,[(den,[(den_,[])]),(haag,[(haag_,[])])]),(np,[(np,[(centraal_,[])]),(n,[(station_,[])])])])]),(zp,[(hallo_,[]),(jij_,[]),(rp,[(daar_,[]),(auto_,[])])])])])])]). //if there is an unprocessed child, make it current node and return to start of while-loop if (currentNode.getChildNodes().size()>currentNode.processedChildren) { if (currentNode.processedChildren > 0) parseOVISFmt.append(","); currentNode = currentNode.getChildNodes().get(currentNode.processedChildren); } //if there are no more unprocessed children, write closing bracket, and mark node as processed with parent else { if (currentNode.getType()==Main.NONTERMINAL) parseOVISFmt.append("])"); //System.out.println("nrChildren=" + currentNode.getChildNodes().size() + "; processed=" +currentNode.processedChildren); //System.out.println("current node=" + currentNode.getName()); currentNode.getParentNode().processedChildren++; //go to parent node currentNode = currentNode.getParentNode(); } //check allChildrenOfTOPProcessed if (currentNode.getName().equals("TOP") && currentNode.getChildNodes().size() == currentNode.processedChildren) allChildrenOfTOPProcessed = true; } parseOVISFmt.append(")"); /* (s,[(per,[(ik_,[])]),(vp,[(v,[(wil_,[])]),(mp,[(mp,[(p,[(van_,[])]),(np, [(voorschoten_,[])])]),(mp,[(p,[(naar_,[])]),(np,[(np,[(den,[(den_,[])]), (haag,[(haag_,[])])]),(np,[(np,[(centraal_,[])]),(n,[(station_,[])])])])]),(zp,[(hallo_,[])])])])]). */ System.out.println("The parse tree in OVIS format is: " + parseOVISFmt.toString()); return parseOVISFmt.toString(); } public String printWSJFormat(){ //go counter-clockwise, start with TOP, find left child //if no child, then go to sister, if no more sister, then go up one level, go to next child //do this until you encounter again the TOP node from the right side, and after you have treated all its children //first set processedChildren of all nodes to 0 for (Node myNode : this.associatedNodes) { myNode.processedChildren = 0; } StringBuffer parseWSJFmt = new StringBuffer(); //(A,[comma-list]) //(mp,[(morgenavond_,[])]). //wordt: (mp (POSTAG morgenavond) ) //dus: , --> spatie ; [] niet schrijven, [] wordt herhaling Node currentNode = this.associatedNodes.get(0); boolean allChildrenOfTOPProcessed = false; while (allChildrenOfTOPProcessed ==false) { //only write [. first time you enter node if (currentNode.processedChildren==0){ if (currentNode.getType()==Main.NONTERMINAL) parseWSJFmt.append("(").append(currentNode.getName()).append(" "); //for extract a treebank with all nodes equal X except for TOP and terminals //if (currentNode.getType()==Main.NONTERMINAL) { // if (currentNode.getName().equals("TOP")) parseWSJFmt.append("(TOP "); // else parseWSJFmt.append("(X "); //} else { //terminal //TEMP: parseWSJFmt.append("(").append(currentNode.getName()).append(" )"); parseWSJFmt.append("(").append(currentNode.getName()).append(" )"); } } //if there is an unprocessed child, make it current node and return to start of while-loop if (currentNode.getChildNodes().size()>currentNode.processedChildren) { if (currentNode.processedChildren > 0) parseWSJFmt.append(" "); currentNode = currentNode.getChildNodes().get(currentNode.processedChildren); } //if there are no more unprocessed children, write closing bracket, and mark node as processed with parent else { if (currentNode.getType()==Main.NONTERMINAL) parseWSJFmt.append(")"); //System.out.println("nrChildren=" + currentNode.getChildNodes().size() + "; processed=" +currentNode.processedChildren); //System.out.println("current node=" + currentNode.getName()); currentNode.getParentNode().processedChildren++; //go to parent node currentNode = currentNode.getParentNode(); } //check allChildrenOfTOPProcessed if (currentNode.getName().equals("TOP") && currentNode.getChildNodes().size() == currentNode.processedChildren) allChildrenOfTOPProcessed = true; } parseWSJFmt.append(")"); //System.out.println("The parse tree in WSJ format is: " + parseWSJFmt.toString()); return parseWSJFmt.toString(); } public String printSimple(boolean blnPrintNrSubtrees, boolean blnPrintNodeSpans, String strText){ StringBuffer parseSimpleFmt = new StringBuffer(); parseSimpleFmt.append(strText + ": "); for (Node myNode : this.associatedNodes) { if (myNode.getType()==Main.NONTERMINAL && (myNode.getRightSpan()-myNode.getLeftSpan()>1)) parseSimpleFmt.append(" (" + myNode.getLeftSpan() + "-" + myNode.getRightSpan() + ") "); } System.out.println(parseSimpleFmt.toString()); return parseSimpleFmt.toString(); } public String printSpans() { StringBuffer parseSpans = new StringBuffer(); for (Node myNode : this.associatedNodes) { if (myNode.getRightSpan()-myNode.getLeftSpan()>1) parseSpans.append(myNode.getLeftSpan() + "-" + myNode.getRightSpan() + " "); //myNode.getType()==Main.NONTERMINAL && ( } System.out.println("Spans: " + parseSpans); return parseSpans.toString(); } }