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