001 package org.maltparser.parser.algorithm.nivre; 002 003 import java.util.ArrayList; 004 import java.util.HashMap; 005 import java.util.HashSet; 006 import java.util.Stack; 007 008 import org.maltparser.core.exception.MaltChainedException; 009 import org.maltparser.core.symbol.SymbolTable; 010 import org.maltparser.core.symbol.TableHandler; 011 import org.maltparser.core.syntaxgraph.DependencyStructure; 012 import org.maltparser.core.syntaxgraph.LabelSet; 013 import org.maltparser.core.syntaxgraph.edge.Edge; 014 import org.maltparser.core.syntaxgraph.node.DependencyNode; 015 import org.maltparser.parser.SingleMalt; 016 import org.maltparser.parser.algorithm.ParsingAlgorithm; 017 import org.maltparser.parser.algorithm.ParsingException; 018 import org.maltparser.parser.algorithm.helper.TransitionTable; 019 import org.maltparser.parser.algorithm.helper.TransitionTableHandler; 020 import org.maltparser.parser.history.GuideUserHistory; 021 import org.maltparser.parser.history.History; 022 import org.maltparser.parser.history.action.GuideUserAction; 023 import org.maltparser.parser.history.container.ActionContainer; 024 025 /** 026 * 027 * @author Joakim Nivre 028 * @author Johan Hall 029 * @since 1.0 030 */ 031 public abstract class Nivre implements ParsingAlgorithm { 032 // Transitions 033 protected static final int SHIFT = 1; 034 035 // Root Handling 036 public static final int STRICT = 1; //root tokens unattached, Reduce not permissible 037 public static final int RELAXED = 2; //root tokens unattached, Reduce permissible 038 public static final int NORMAL = 3; //root tokens attached to Root with RightArc 039 040 protected GuideUserHistory history; 041 protected ArrayList<ActionContainer> actionContainers; 042 protected ActionContainer transActionContainer; 043 protected ActionContainer pushActionContainer; 044 protected TransitionTable pushTable; 045 protected HashSet<ActionContainer> arcLabelActionContainers; 046 protected final SingleMalt configuration; 047 protected GuideUserAction currentAction; 048 protected HashMap<String, TableHandler> tableHandlers; 049 protected TransitionTableHandler transitionTableHandler; 050 protected int rootHandling; 051 protected boolean postProcessing; 052 protected final Stack<DependencyNode> stack; 053 protected final Stack<DependencyNode> input; 054 protected boolean complexTransition = false; 055 056 057 public Nivre(SingleMalt configuration) throws MaltChainedException { 058 this.configuration = configuration; 059 initRootHandling(); 060 initPostProcessing(); 061 stack = new Stack<DependencyNode>(); 062 input = new Stack<DependencyNode>(); 063 initHistory(); 064 } 065 066 067 public DependencyStructure parse(DependencyStructure parseDependencyGraph) throws MaltChainedException { 068 clear(parseDependencyGraph); 069 while (!input.isEmpty()) { 070 currentAction = history.getEmptyGuideUserAction(); 071 if (rootHandling != NORMAL && stack.peek().isRoot()) { 072 updateActionContainers(SHIFT, null); 073 } else { 074 configuration.predict(currentAction); 075 } 076 transition(parseDependencyGraph); 077 } 078 079 if (postProcessing == true) { 080 input.clear(); 081 while (!stack.isEmpty() && !stack.peek().isRoot()) { 082 if (!stack.peek().hasHead()) { 083 input.push(stack.pop()); 084 } else { 085 stack.pop(); 086 } 087 } 088 while (!input.isEmpty()) { 089 currentAction = history.getEmptyGuideUserAction(); 090 if (rootHandling != NORMAL && stack.peek().isRoot()) { 091 updateActionContainers(SHIFT, null); 092 } else { 093 configuration.predict(currentAction); 094 } 095 transition(parseDependencyGraph); 096 } 097 } 098 parseDependencyGraph.linkAllTreesToRoot(); 099 return parseDependencyGraph; 100 } 101 102 public DependencyStructure oracleParse(DependencyStructure goldDependencyGraph, DependencyStructure parseDependencyGraph) throws MaltChainedException { 103 clear(parseDependencyGraph); 104 while (!input.isEmpty()) { 105 currentAction = history.getEmptyGuideUserAction(); 106 if (rootHandling != NORMAL && stack.peek().isRoot()) { 107 updateActionContainers(SHIFT, null); 108 } else { 109 oraclePredict(goldDependencyGraph, parseDependencyGraph); 110 configuration.setInstance(currentAction); 111 } 112 transition(parseDependencyGraph); 113 } 114 parseDependencyGraph.linkAllTreesToRoot(); 115 return parseDependencyGraph; 116 } 117 118 protected boolean isActionContainersLabeled() { 119 for (ActionContainer container : arcLabelActionContainers) { 120 if (container.getActionCode() < 0) { 121 return false; 122 } 123 } 124 return true; 125 } 126 127 protected void addEdgeLabels(Edge e) throws MaltChainedException { 128 if (e != null) { 129 for (ActionContainer container : arcLabelActionContainers) { 130 e.addLabel((SymbolTable)container.getTable(), container.getActionCode()); 131 } 132 } 133 } 134 135 protected LabelSet getArcLabels(DependencyStructure parseDependencyGraph) throws MaltChainedException { 136 final LabelSet arcLabels = parseDependencyGraph.checkOutNewLabelSet(); 137 for (ActionContainer container : arcLabelActionContainers) { 138 arcLabels.put((SymbolTable)container.getTable(), container.getActionCode()); 139 } 140 return arcLabels; 141 } 142 143 public DependencyNode getStackNode(int index) throws MaltChainedException { 144 if (index < 0) { 145 throw new ParsingException("Stack index must be non-negative in feature specification. "); 146 } 147 if (stack.size()-index > 0) { 148 return stack.get(stack.size()-1-index); 149 } 150 return null; 151 } 152 153 public DependencyNode getInputNode(int index) throws MaltChainedException { 154 if (index < 0) { 155 throw new ParsingException("Input index must be non-negative in feature specification. "); 156 } 157 if (input.size()-index > 0) { 158 return input.get(input.size()-1-index); 159 } 160 return null; 161 } 162 163 public DependencyNode getLeftTarget() { 164 return stack.peek(); 165 } 166 167 public DependencyNode getRightTarget() { 168 return input.peek(); 169 } 170 171 public DependencyNode getNode(String dataStructure, int index) throws MaltChainedException { 172 if (dataStructure.equalsIgnoreCase("Stack")) { 173 if (index < 0) { 174 throw new ParsingException("Stack index must be non-negative in feature specification. "); 175 } 176 if (stack.size()-index > 0) { 177 return stack.get(stack.size()-1-index); 178 } 179 } else if (dataStructure.equalsIgnoreCase("Input")) { 180 if (index < 0) { 181 throw new ParsingException("Input index must be non-negative in feature specification. "); 182 } 183 if (input.size()-index > 0) { 184 return input.get(input.size()-1-index); 185 } 186 } else { 187 throw new ParsingException("Undefined data structure in feature specification. "); 188 } 189 return null; 190 } 191 192 public int getRootHandling() { 193 return rootHandling; 194 } 195 196 protected void clear(DependencyStructure dg) throws MaltChainedException { 197 stack.clear(); 198 input.clear(); 199 history.clear(); 200 stack.push(dg.getDependencyRoot()); 201 for (int i = dg.getHighestTokenIndex(); i > 0; i--) { 202 final DependencyNode node = dg.getDependencyNode(i); 203 if (node != null) { 204 input.push(node); 205 } 206 } 207 } 208 209 protected void initRootHandling() throws MaltChainedException { 210 final String rh = getConfiguration().getOptionValue("nivre", "root_handling").toString(); 211 if (rh.equalsIgnoreCase("strict")) { 212 rootHandling = Nivre.STRICT; 213 } else if (rh.equalsIgnoreCase("relaxed")) { 214 rootHandling = Nivre.RELAXED; 215 } else if (rh.equalsIgnoreCase("normal")) { 216 rootHandling = Nivre.NORMAL; 217 } else { 218 throw new ParsingException("The root handling '"+rh+"' is unknown"); 219 } 220 } 221 222 protected void addTransition(ActionContainer transitionContainer, GuideUserAction action, int value) throws MaltChainedException { 223 transitionContainer.setAction(value); 224 for (ActionContainer container : arcLabelActionContainers) { 225 container.setAction(-1); 226 } 227 currentAction.addAction(actionContainers); 228 } 229 230 protected void initPostProcessing() throws MaltChainedException { 231 postProcessing = ((Boolean)getConfiguration().getOptionValue("nivre", "post_processing")).booleanValue(); 232 } 233 234 public SingleMalt getConfiguration() { 235 return configuration; 236 } 237 238 239 protected void initHistory() throws MaltChainedException { 240 String decisionSettings = configuration.getOptionValue("guide", "decision_settings").toString().trim(); 241 transitionTableHandler = new TransitionTableHandler(); 242 tableHandlers = new HashMap<String, TableHandler>(); 243 244 final String[] decisionElements = decisionSettings.split(",|#|;|\\+"); 245 246 int nTrans = 0; 247 int nArc = 0; 248 for (int i = 0; i < decisionElements.length; i++) { 249 int index = decisionElements[i].indexOf('.'); 250 if (index == -1) { 251 throw new ParsingException("Decision settings '"+decisionSettings+"' contain an item '"+decisionElements[i]+"' that does not follow the format {TableHandler}.{Table}. "); 252 } 253 if (decisionElements[i].substring(0,index).equals("T")) { 254 if (!tableHandlers.containsKey("T")) { 255 tableHandlers.put("T", transitionTableHandler); 256 } 257 if (decisionElements[i].substring(index+1).equals("TRANS")) { 258 if (nTrans == 0) { 259 TransitionTable ttable = (TransitionTable)transitionTableHandler.addSymbolTable("TRANS"); 260 addAvailableTransitionToTable(ttable); 261 } else { 262 throw new ParsingException("Illegal decision settings '"+decisionSettings+"'"); 263 } 264 nTrans++; 265 } else if (decisionElements[i].substring(index+1).equals("PUSH")) { 266 if (nArc == 0) { 267 complexTransition = true; 268 pushTable = (TransitionTable)transitionTableHandler.addSymbolTable("PUSH"); 269 pushTable.addTransition(1, "YES", true, null); 270 pushTable.addTransition(2, "NO", true, null); 271 } else { 272 throw new ParsingException("Illegal decision settings '"+decisionSettings+"'"); 273 } 274 nArc++; 275 } 276 } else if (decisionElements[i].substring(0,index).equals("A")) { 277 if (!tableHandlers.containsKey("A")) { 278 tableHandlers.put("A", configuration.getSymbolTables()); 279 } 280 } else { 281 throw new ParsingException("The decision settings '"+decisionSettings+"' contains an unknown table handler '"+decisionElements[i].substring(0,index)+"'. " + 282 "Only T (Transition table handler) and A (ArcLabel table handler) is allowed for '"+getName()+"' parsing algorithm. "); 283 } 284 } 285 286 history = new History(decisionSettings, getConfiguration().getOptionValue("guide", "classitem_separator").toString(), tableHandlers); 287 actionContainers = history.getActionContainers(); 288 if (actionContainers.size() < 1) { 289 throw new ParsingException("Problem when initialize the history (sequence of actions). There are no action containers. "); 290 } 291 292 for (int i = 0; i < actionContainers.size(); i++) { 293 if (actionContainers.get(i).getTableContainerName().equals("T.TRANS")) { 294 transActionContainer = actionContainers.get(i); 295 } else if (actionContainers.get(i).getTableContainerName().equals("T.PUSH")) { 296 pushActionContainer = actionContainers.get(i); 297 } else if (actionContainers.get(i).getTableContainerName().startsWith("A.")) { 298 if (arcLabelActionContainers == null) { 299 arcLabelActionContainers = new HashSet<ActionContainer>(); 300 } 301 arcLabelActionContainers.add(actionContainers.get(i)); 302 } 303 } 304 currentAction = history.getEmptyGuideUserAction(); 305 initWithDefaultTransitions(); 306 } 307 308 public GuideUserHistory getHistory() { 309 return history; 310 } 311 312 protected abstract int getTransition(); 313 protected abstract void updateActionContainers(int transition, LabelSet arcLabels) throws MaltChainedException; 314 protected abstract void transition(DependencyStructure dg) throws MaltChainedException; 315 protected abstract void addAvailableTransitionToTable(TransitionTable ttable) throws MaltChainedException; 316 protected abstract void initWithDefaultTransitions() throws MaltChainedException; 317 protected abstract boolean checkParserAction(DependencyStructure dg) throws MaltChainedException; 318 protected abstract void oraclePredict(DependencyStructure gold, DependencyStructure parseDependencyGraph) throws MaltChainedException; 319 public abstract String getName(); 320 321 } 322