001 // This file is part of AceWiki.
002 // Copyright 2008-2012, AceWiki developers.
003 //
004 // AceWiki is free software: you can redistribute it and/or modify it under the terms of the GNU
005 // Lesser General Public License as published by the Free Software Foundation, either version 3 of
006 // the License, or (at your option) any later version.
007 //
008 // AceWiki is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
009 // even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
010 // Lesser General Public License for more details.
011 //
012 // You should have received a copy of the GNU Lesser General Public License along with AceWiki. If
013 // not, see http://www.gnu.org/licenses/.
014
015 package ch.uzh.ifi.attempto.chartparser;
016
017 import java.util.ArrayList;
018 import java.util.HashMap;
019 import java.util.HashSet;
020 import java.util.List;
021 import java.util.Map;
022 import java.util.Set;
023
024 import ch.uzh.ifi.attempto.base.PredictiveParser;
025
026 /**
027 * This is a chart parser (concretely an Earley parser) that implements the predictive parser
028 * interface.
029 *
030 * @see Grammar
031 * @author Tobias Kuhn
032 */
033 public class ChartParser implements PredictiveParser {
034
035 private final Grammar grammar;
036 private final String startCategoryName;
037 private final Nonterminal[] context;
038 private DynamicLexicon dynLexicon;
039 private final Chart chart;
040 private final List<String> tokens = new ArrayList<String>();
041 private final List<CPNextTokenOptions> options = new ArrayList<CPNextTokenOptions>();
042 private final List<List<FeatureMap>> backwardReferences = new ArrayList<List<FeatureMap>>();
043 private ParseTree parseTree;
044 private Map<String, Integer> progressTable;
045 private boolean recalculateParseTree = true;
046 private String positionIdentifierPrefix = "#";
047 private boolean debug;
048
049 /**
050 * Creates a new chart parser for the given grammar. The grammar must not be changed afterwards.
051 *
052 * @param grammar The grammar to be used by the chart parser.
053 * @param startCategoryName The name of the start category.
054 * @param context A list of forward references and scope openers that define the context.
055 */
056 public ChartParser(Grammar grammar, String startCategoryName, List<Nonterminal> context) {
057 this.grammar = grammar;
058 this.startCategoryName = startCategoryName;
059 if (context == null) {
060 this.context = new Nonterminal[0];
061 } else {
062 this.context = context.toArray(new Nonterminal[0]);
063 }
064 this.chart = new Chart(grammar);
065 options.add(null);
066 init();
067 runParsingSteps();
068 }
069
070 /**
071 * Creates a new chart parser for the given grammar. The grammar must not be changed afterwards.
072 *
073 * @param grammar The grammar to be used by the chart parser.
074 * @param startCategoryName The name of the start category.
075 */
076 public ChartParser(Grammar grammar, String startCategoryName) {
077 this(grammar, startCategoryName, null);
078 }
079
080 /**
081 * This method can be used to switch on/off debug mode (default is off). In debug mode, messages
082 * about the actions of the chart parser are printed onto the standard error device.
083 *
084 * @param debug true to switch debug mode on, or false to switch it off.
085 */
086 public void debug(boolean debug) {
087 this.debug = debug;
088 }
089
090 /**
091 * Sets the dynamic lexicon.
092 *
093 * @param dynLexicon The dynamic lexicon.
094 */
095 public void setDynamicLexicon(DynamicLexicon dynLexicon) {
096 this.dynLexicon = dynLexicon;
097 updateConcreteOptions(tokens.size());
098 }
099
100 /**
101 * Sets the prefix for the position identifiers that are assigned to the variables of the
102 * position operator "#". The default prefix is "#" so that the position identifiers are "#0",
103 * "#1", "#2" and so on.
104 *
105 * @param prefix The new prefix.
106 */
107 public void setPositionIdentifierPrefix(String prefix) {
108 this.positionIdentifierPrefix = prefix.toString();
109 }
110
111 public void addToken(String token) {
112 chart.addEdge(new Edge(tokens.size(), new Terminal(token)));
113
114 List<LexicalRule> lexRules;
115 if (dynLexicon == null) {
116 lexRules = grammar.lexRulesByWord(token);
117 } else {
118 lexRules = new ArrayList<LexicalRule>();
119 lexRules.addAll(grammar.lexRulesByWord(token));
120 lexRules.addAll(dynLexicon.getLexRules(token));
121 }
122
123 // add edges for applicable lexical rules:
124 for (LexicalRule lexRule : lexRules) {
125 Edge edge = new Edge(tokens.size(), lexRule.deepCopy());
126 chart.addEdge(edge);
127 if (debug) log("SCANNER: " + edge + "\n");
128 }
129
130 runParsingSteps();
131
132 // add the token to the list of tokens:
133 tokens.add(token);
134 if (debug) {
135 log("ADD TOKEN: " + token + "\nTOKEN LIST:");
136 for (String t : tokens) log(" " + t);
137 log("\n");
138 }
139 options.add(null);
140 backwardReferences.add(new ArrayList<FeatureMap>());
141 progressTable = null;
142
143 runParsingSteps();
144 //if (debug) log("CHART:");
145 //if (debug) log(chart);
146 recalculateParseTree = true;
147 }
148
149 public void addTokens(List<String> tokens) {
150 for (String t : tokens) {
151 addToken(t);
152 }
153 }
154
155 public void removeToken() {
156 chart.removeEdgesWithEndPos(tokens.size());
157 backwardReferences.remove(tokens.size()-1);
158 options.remove(tokens.size());
159 tokens.remove(tokens.size()-1);
160 progressTable = null;
161 updateConcreteOptions(tokens.size());
162 recalculateParseTree = true;
163 if (debug) {
164 log("REMOVE LAST TOKEN.\nTOKEN LIST:");
165 for (String t : tokens) log(" " + t);
166 log("\n");
167 }
168 }
169
170 public void removeAllTokens() {
171 if (debug) log("REMOVE ALL TOKENS.\n");
172 tokens.clear();
173 options.clear();
174 options.add(null);
175 backwardReferences.clear();
176 progressTable = null;
177 chart.clear();
178 init();
179 runParsingSteps();
180 recalculateParseTree = true;
181 }
182
183 public void setTokens(List<String> tokens) {
184 removeAllTokens();
185 addTokens(tokens);
186 }
187
188 public List<String> getTokens() {
189 return new ArrayList<String>(tokens);
190 }
191
192 public int getTokenCount() {
193 return tokens.size();
194 }
195
196 /**
197 * This method returns the token number to which the token at the given position refers, if it
198 * is a reference. -1 is returned if the given token is not a reference.
199 *
200 * @param pos The position of the token for which the reference should be returned.
201 * @return The token number to which the token at the given position refers, or -1.
202 */
203 public int getReference(int pos) {
204 int ref = -1;
205 for (FeatureMap f : getBackwardReferences(pos)) {
206 String s = f.getFeature("*pos").getString();
207 if (s != null) {
208 int i = new Integer(s) - 1;
209 if (i > -1) {
210 ref = i;
211 }
212 }
213 }
214 return ref;
215 }
216
217 public int getReference() {
218 return getReference(tokens.size()-1);
219 }
220
221 /**
222 * Return a list of feature maps that show how the backward references at the given position
223 * in the text can be resolved. These feature maps contain special features of the form "*pos"
224 * that denote the textual position of the respective forward references.
225 *
226 * @param pos The position of the backward reference.
227 * @return The list of feature maps.
228 */
229 public List<FeatureMap> getBackwardReferences(int pos) {
230 if (pos == -1 || pos >= tokens.size()) {
231 return new ArrayList<FeatureMap>();
232 }
233 return backwardReferences.get(pos);
234 }
235
236 /**
237 * Returns a list of feature maps that show how the backward references at the end of the
238 * token sequence can be resolved.
239 *
240 * @return The list of feature maps.
241 */
242 public List<FeatureMap> getBackwardReferences() {
243 return getBackwardReferences(tokens.size()-1);
244 }
245
246 public boolean isComplete() {
247 for (Edge e : chart.getEdgesByEndPos(tokens.size())) {
248 if (e.getStartPos() != 0) continue;
249 if (e.isActive()) continue;
250 if (!e.getHead().getName().equals(startCategoryName)) continue;
251 return true;
252 }
253 return false;
254 }
255
256 /**
257 * Returns the parse tree of the parsed text if it is a complete statement according to the
258 * given grammar and category. Null is returned if the text is not a complete statement.
259 *
260 * @param categoryName The category name.
261 * @return The parse tree.
262 */
263 public ParseTree getParseTree(String categoryName) {
264 for (Edge e : chart.getEdgesByEndPos(tokens.size())) {
265 if (e.getStartPos() != 0) continue;
266 if (e.isActive()) continue;
267 if (!e.getHead().getName().equals(categoryName)) continue;
268 return new ParseTree(e);
269 }
270 return null;
271 }
272
273 /**
274 * Returns the parse tree of the parsed text if it is a complete statement according to the
275 * given grammar and start category. Null is returned if the text is not a complete statement.
276 *
277 * @return The parse tree.
278 */
279 public ParseTree getParseTree() {
280 if (recalculateParseTree) {
281 parseTree = getParseTree(startCategoryName);
282 }
283 recalculateParseTree = false;
284 return parseTree;
285 }
286
287 /**
288 * This methods shows the possible tokens that could be used to continue the text at the given
289 * position.
290 *
291 * @param position The position at which the possible next tokens should be found.
292 * @return The options describing the possible next tokens.
293 */
294 public CPNextTokenOptions getNextTokenOptions(int position) {
295 createOptions(position);
296 return options.get(position);
297 }
298
299 public CPNextTokenOptions getNextTokenOptions() {
300 return getNextTokenOptions(tokens.size());
301 }
302
303 /**
304 * This method returns a set of abstract options describing the possible next tokens at the
305 * given position in an abstract way.
306 *
307 * @param position The position at which the possible next tokens should be found.
308 * @return The set of abstract options describing the possible next tokens.
309 */
310 public Set<CPAbstractOption> getAbstractOptions(int position) {
311 createOptions(position);
312 return options.get(position).getAbstractOptions();
313 }
314
315 /**
316 * This method returns a set of abstract options describing the possible next tokens at the end
317 * position in an abstract way.
318 *
319 * @return The set of abstract options describing the possible next tokens.
320 */
321 public Set<CPAbstractOption> getAbstractOptions() {
322 return getAbstractOptions(tokens.size());
323 }
324
325 /**
326 * This method returns a set of concrete options describing the possible next tokens at the
327 * given position in a concrete way.
328 *
329 * @param position The position at which the possible next tokens should be found.
330 * @return The set of concrete options describing the possible next tokens.
331 */
332 public Set<CPConcreteOption> getConcreteOptions(int position) {
333 createOptions(position);
334 return options.get(position).getConcreteOptions();
335 }
336
337 /**
338 * This method returns a set of concrete options describing the possible next tokens at the end
339 * position in a concrete way.
340 *
341 * @return The set of concrete options describing the possible next tokens.
342 */
343 public Set<CPConcreteOption> getConcreteOptions() {
344 return getConcreteOptions(tokens.size());
345 }
346
347 public boolean isPossibleNextToken(String token) {
348 if (getNextTokenOptions().containsToken(token)) return true;
349 for (LexicalRule lr : dynLexicon.getLexRules(token)) {
350 if (!lr.getWord().getName().equals(token)) continue;
351 if (getNextTokenOptions().containsCategory(lr.getCategory())) return true;
352 }
353 return false;
354 }
355
356 /**
357 * Creates the abstract and concrete options at the given position. The options are cached.
358 *
359 * @param position The position for which the options should be calculated.
360 */
361 private void createOptions(int position) {
362 if (options.get(position) == null) {
363 Set<CPAbstractOption> aOptions = createAbstractOptions(position);
364 Set<CPConcreteOption> cOptions = createConcreteOptions(position, aOptions);
365 options.set(position, new CPNextTokenOptions(aOptions, cOptions));
366 }
367 }
368
369 private void updateConcreteOptions(int position) {
370 if (options.get(position) == null) {
371 createOptions(position);
372 } else {
373 Set<CPAbstractOption> aOptions = options.get(position).getAbstractOptions();
374 Set<CPConcreteOption> cOptions = createConcreteOptions(position, aOptions);
375 options.set(position, new CPNextTokenOptions(aOptions, cOptions));
376 }
377 }
378
379 /**
380 * Calculates the set of abstract options for the given position.
381 *
382 * @param position The position for which the abstract options should be calculated.
383 * @return The set of abstract options.
384 */
385 private Set<CPAbstractOption> createAbstractOptions(int position) {
386 Set<CPAbstractOption> aOptions = new HashSet<CPAbstractOption>();
387 for (Edge e : chart.getEdgesByEndPos(position)) {
388 if (!e.isActive()) continue;
389 if (e.getNextActive() instanceof Nonterminal) continue;
390
391 BackrefCategory backref = null;
392 Nonterminal negbackref = null;
393 int refpos = 0;
394 Category[] body = e.getBody();
395 int p = e.getProgress();
396 for (int i = p + 1 ; i < body.length ; i++) {
397 Category c = body[i];
398 if (!(c instanceof Nonterminal)) continue;
399 if (c instanceof BackrefCategory) {
400 backref = (BackrefCategory) c;
401 refpos = i;
402 } else if (i == (p+1) && c.getName().equals("/<")) {
403 negbackref = (Nonterminal) c;
404 refpos = i;
405 }
406 break;
407 }
408
409 if (backref != null) {
410 // For edges with backwards references, the possible bindings have to be performed:
411 for (int i = e.getCombinedAnteList().length - 1 ; i >= 0 ; i--) {
412 if (e.getCombinedAnteList()[i].getName().equals("//")) continue;
413
414 int posrefsCount = backref.getPosFeatureMaps().size();
415 int negrefsCount = backref.getNegFeatureMaps().size();
416 List<Category> exceptions = null;
417 boolean makeRestriction = true;
418
419 if (refpos == (p+1)) {
420 exceptions = new ArrayList<Category>();
421 for (int j = 0 ; j < negrefsCount ; j++) {
422 Edge eC = e.deepCopy();
423 try {
424 FeatureMap backrefFm =
425 ((BackrefCategory) eC.getBody()[refpos]).getNegFeatureMaps().get(j);
426 eC.getCombinedAnteList()[i].getFeatureMap().unify(backrefFm);
427 if (eC.getNextActive() instanceof Terminal) {
428 makeRestriction = false;
429 break;
430 } else {
431 exceptions.add(eC.getNextActive());
432 }
433 } catch (UnificationFailedException ex) {}
434 }
435 }
436 if (!makeRestriction) break;
437
438 for (int j = 0 ; j < posrefsCount ; j++) {
439 Edge eC = e.deepCopy();
440 try {
441 FeatureMap backrefFm =
442 ((BackrefCategory) eC.getBody()[refpos]).getPosFeatureMaps().get(j);
443 eC.getCombinedAnteList()[i].getFeatureMap().unify(backrefFm);
444 if (exceptions != null) {
445 aOptions.add(new CPAbstractOption(
446 grammar,
447 eC.getNextActive(),
448 copyExceptionsList(exceptions)
449 ));
450 } else {
451 aOptions.add(new CPAbstractOption(grammar, eC.getNextActive()));
452 }
453 } catch (UnificationFailedException ex) {}
454 }
455 }
456 } else if (negbackref != null) {
457 List<Category> exceptions = new ArrayList<Category>();
458 // Edges with negative backwards references lead to exceptions:
459 boolean makeRestriction = true;
460 for (int i = 0 ; i < e.getCombinedAnteList().length ; i++) {
461 if (e.getCombinedAnteList()[i].getName().equals("//")) continue;
462 Edge eC = e.deepCopy();
463 try {
464 eC.getCombinedAnteList()[i].getFeatureMap().unify(eC.getBody()[refpos].getFeatureMap());
465 if (eC.getNextActive() instanceof Terminal) {
466 makeRestriction = false;
467 break;
468 } else {
469 exceptions.add(eC.getNextActive());
470 }
471 } catch (UnificationFailedException ex) {}
472 }
473 if (makeRestriction) {
474 aOptions.add(new CPAbstractOption(grammar, e.getNextActive().deepCopy(), exceptions));
475 }
476 } else {
477 aOptions.add(new CPAbstractOption(grammar, e.getNextActive().deepCopy()));
478 }
479 }
480 if (debug) {
481 for (CPAbstractOption o : aOptions) {
482 log("LOOKING FORWARD: " + o + "\n");
483 }
484 }
485
486 return aOptions;
487 }
488
489 /**
490 * Calculates the set of concrete options for the given position on the basis of a set of
491 * abstract options.
492 *
493 * @param position The position for which the concrete options should be calculated.
494 * @param aOptions The set of abstract options.
495 * @return The set of concrete options.
496 */
497 private Set<CPConcreteOption> createConcreteOptions(int position, Set<CPAbstractOption> aOptions) {
498 Set<CPConcreteOption> cOptions = new HashSet<CPConcreteOption>();
499
500 for (CPAbstractOption ao : aOptions) {
501 if (ao.getCategory() instanceof Preterminal) {
502
503 List<LexicalRule> lexRules;
504 if (dynLexicon == null) {
505 lexRules = grammar.lexRulesByCat(ao.getCategory().getName());
506 } else {
507 lexRules = new ArrayList<LexicalRule>();
508 lexRules.addAll(grammar.lexRulesByCat(ao.getCategory().getName()));
509 lexRules.addAll(dynLexicon.getLexRules(ao));
510 }
511
512 for (LexicalRule lexRule : lexRules) {
513 if (ao.isFulfilledBy(lexRule.getCategory())) {
514 cOptions.add(new CPConcreteOption(grammar, lexRule.deepCopy()));
515 }
516 }
517 } else if (ao.getCategory() instanceof Terminal) {
518 cOptions.add(new CPConcreteOption(grammar, (Terminal) ao.getCategory(), null));
519 }
520 }
521
522 return cOptions;
523 }
524
525 /**
526 * Runs the initialization step of the Earley parsing algorithm.
527 */
528 private void init() {
529 for (GrammarRule rule : grammar.rulesByHeadName(startCategoryName)) {
530 Edge edge = new Edge(0, rule.deepCopy(), context);
531 chart.addEdge(edge);
532 if (debug) log("INIT: " + rule + " ---> " + edge + "\n");
533 }
534 }
535
536 /**
537 * Runs the main parsing steps of the Earley algorithm. These parsing steps consists of the
538 * completion/prediction/resolution loop.
539 */
540 private void runParsingSteps() {
541 // Run completion/predition/resolution until neither of them generates a new edge:
542 int chartSize = 0;
543 int step = 0;
544 int idleSteps = 0;
545 if (progressTable == null) {
546 progressTable = new HashMap<String, Integer>();
547 progressTable.put("prediction", 0);
548 progressTable.put("completion", 0);
549 progressTable.put("resolution", 0);
550 }
551 while (true) {
552 step++;
553 chartSize = chart.getSize();
554 if (step == 1) {
555 predict(progressTable);
556 } else if (step == 2) {
557 resolve(progressTable);
558 } else {
559 complete(progressTable);
560 step = 0;
561 }
562 if (chartSize == chart.getSize()) {
563 idleSteps++;
564 } else {
565 idleSteps = 0;
566 }
567 if (idleSteps > 2) {
568 break;
569 }
570 }
571 }
572
573 /**
574 * Runs the prediction step of the Earley parsing algorithm.
575 *
576 * @param progressTable This table captures the progress state in order to prevent from
577 * checking the same edges more than once.
578 */
579 private void predict(Map<String, Integer> progressTable) {
580 List<Edge> l = chart.getEdgesByEndPos(tokens.size());
581 for (int i = new Integer(progressTable.get("prediction")) ; i < l.size() ; i++) {
582 // During this loop, elements might be added to the end of the list l.
583
584 Edge existingEdge = l.get(i);
585 Category category = existingEdge.getNextActive();
586 if (category == null) continue;
587 if (category instanceof Terminal) continue;
588 if (category.isSpecialCategory()) continue;
589 if (debug) log("PREDICTION FOR CATEGORY: " + category + "\n");
590
591 for (GrammarRule rule : grammar.rulesByHeadName(category.getName())) {
592 try {
593 if (!category.isSimilar(rule.getHead())) continue;
594 Edge edgeC = existingEdge.deepCopy();
595 GrammarRule ruleC = rule.deepCopy();
596 edgeC.getNextActive().unify(ruleC.getHead());
597 Edge edge = new Edge(tokens.size(), ruleC, edgeC.getCombinedAnteList());
598 boolean isNewEdge = chart.addEdge(edge);
599 if (debug) log("PREDICT (" + (isNewEdge ? "NEW" : "KNOWN") + "): " + rule + " ---> " + edge + "\n");
600 } catch (UnificationFailedException ex) {
601 continue;
602 }
603 }
604 }
605 progressTable.put("prediction", l.size());
606 }
607
608 /**
609 * Runs the completion step of the Earley parsing algorithm.
610 *
611 * @param progressTable This table captures the progress state in order to prevent from
612 * checking the same edges more than once.
613 */
614 private void complete(Map<String, Integer> progressTable) {
615 List<Edge> l1 = chart.getEdgesByEndPos(tokens.size());
616 for (int i1 = 0 ; i1 < l1.size() ; i1++) {
617 // During this loop, elements might be added to the end of the list l1.
618
619 Edge passiveEdge = l1.get(i1);
620 if (passiveEdge.isActive()) continue;
621 if (debug) log("COMPLETION FOR EDGE: " + passiveEdge + "\n");
622
623 List<Edge> l2 = chart.getEdgesByEndPos(passiveEdge.getStartPos());
624 int start;
625 if (i1 < progressTable.get("completion")) {
626 Integer progress = progressTable.get("completion " + i1);
627 if (progress == null) {
628 start = 0;
629 } else {
630 start = progress;
631 }
632 } else {
633 start = 0;
634 }
635
636 for (int i2 = start ; i2 < l2.size() ; i2++) {
637 // During this loop, elements might be added to the end of the list l2.
638
639 Edge edge = l2.get(i2);
640 if (!edge.isActive()) continue;
641 if (!edge.getNextActive().getName().equals(passiveEdge.getHead().getName())) continue;
642
643 try {
644 if (!passiveEdge.getHead().isSimilar(edge.getNextActive())) continue;
645 Edge passiveEdgeC = passiveEdge.deepCopy();
646 Edge edgeC = edge.deepCopy();
647 passiveEdgeC.getHead().unify(edgeC.getNextActive());
648 if (!passiveEdge.carriesAntecedentInformation()) {
649 // Antecedent lists have to match:
650 Category[] al1 = edgeC.getCombinedAnteList();
651 Category[] al2 = passiveEdgeC.getExternalAnteList();
652 if (al1.length != al2.length) throw new UnificationFailedException();
653 for (int i = 0 ; i < al1.length ; i++) {
654 al1[i].unify(al2[i]);
655 }
656 }
657 edgeC.step(tokens.size(), passiveEdgeC);
658 boolean isNewEdge = chart.addEdge(edgeC);
659 if (debug) log("COMPLETE (" + (isNewEdge ? "NEW" : "KNOWN") + "): " + edge + " ---> " + edgeC + "\n");
660 } catch (UnificationFailedException ex) {
661 continue;
662 }
663 }
664 progressTable.put("completion " + i1, l2.size());
665 }
666 progressTable.put("completion", l1.size());
667 }
668
669 /**
670 * Runs the resolution step, which is an extension of the standard Earley algorithm.
671 *
672 * @param progressTable This table captures the progress state in order to prevent from
673 * checking the same edges more than once.
674 */
675 private void resolve(Map<String, Integer> progressTable) {
676 List<Edge> l1 = chart.getEdgesByEndPos(tokens.size());
677 for (int i1 = progressTable.get("resolution") ; i1 < l1.size() ; i1++) {
678 // During this loop, elements might be added to the end of the list l1.
679
680 Edge edge = l1.get(i1);
681 if (!edge.isActive()) continue;
682
683 String n = edge.getNextActive().getName();
684 List<Edge> newEdges = new ArrayList<Edge>();
685 if (n.equals("#")) {
686 Edge edgeC = edge.deepCopy();
687 try {
688 String posId = positionIdentifierPrefix + tokens.size();
689 edgeC.getNextActive().getFeature("pos").unify(new StringRef(posId));
690 newEdges.add(edgeC);
691 } catch (UnificationFailedException ex) {}
692 } else if (n.equals(">") || n.equals(">>") || n.equals("//")) {
693 Edge edgeC = edge.deepCopy();
694 edgeC.getNextActive().setFeature("*pos", tokens.size() + "");
695 edgeC.addAntecedents(edgeC.getNextActive());
696 newEdges.add(edgeC);
697 } else if (n.equals("<")) {
698 BackrefCategory bwrefCat = (BackrefCategory) edge.getNextActive();
699 Category[] ante = edge.getCombinedAnteList();
700 for (int i = ante.length-1 ; i >= 0 ; i--) {
701 if (ante[i].getName().equals("//")) continue;
702
703 boolean negMatch = false;
704 for (FeatureMap negfm : bwrefCat.getNegFeatureMaps()) {
705 if (ante[i].getFeatureMap().canUnify(negfm)) {
706 negMatch = true;
707 break;
708 }
709 }
710 if (negMatch) continue;
711
712 boolean posMatch = false;
713 List<FeatureMap> posfms = bwrefCat.getPosFeatureMaps();
714 for (int j = 0 ; j < posfms.size() ; j++) {
715 if (ante[i].getFeatureMap().canUnify(posfms.get(j))) {
716 try {
717 Edge edgeC = edge.deepCopy();
718 edgeC.getExternalAnteList()[i].getFeatureMap().unify(
719 ((BackrefCategory) edgeC.getNextActive()).getPosFeatureMaps().get(j)
720 );
721 backwardReferences.get(tokens.size()-1).add(
722 edgeC.getExternalAnteList()[i].getFeatureMap().deepCopy()
723 );
724 newEdges.add(edgeC);
725 posMatch = true;
726 } catch (UnificationFailedException ex) {}
727 }
728 }
729 if (posMatch) break;
730 }
731 } else if (n.equals("/<")) {
732 Edge edgeC = edge.deepCopy();
733 for (Category c : edge.getCombinedAnteList()) {
734 if (c.getName().equals("//")) continue;
735 if (c.getFeatureMap().canUnify(edge.getNextActive().getFeatureMap())) {
736 edgeC = null;
737 break;
738 }
739 }
740 if (edgeC != null) {
741 newEdges.add(edgeC);
742 }
743 } else {
744 continue;
745 }
746
747 if (newEdges.isEmpty()) {
748 if (debug) log("CANNOT RESOLVE: " + edge + "\n");
749 }
750 for (Edge newEdge : newEdges) {
751 newEdge.step();
752 boolean isNewEdge = chart.addEdge(newEdge);
753 if (debug) log("RESOLVE (" + (isNewEdge ? "NEW" : "KNOWN") + "): " + edge + " ---> " + newEdge + "\n");
754 }
755 }
756 progressTable.put("resolution", l1.size());
757 }
758
759 private static List<Category> copyExceptionsList(List<Category> list) {
760 List<Category> listCopy = new ArrayList<Category>();
761 for (Category x : list) {
762 listCopy.add(x.deepCopy());
763 }
764 return listCopy;
765 }
766
767 private void log(String text) {
768 System.err.print(text);
769 }
770
771 }