1 /* 2 * Copyright (c) 2012-2017 The ANTLR Project. All rights reserved. 3 * Use of this file is governed by the BSD 3-clause license that 4 * can be found in the LICENSE.txt file in the project root. 5 */ 6 7 package org.antlr.v4.runtime.atn; 8 9 import org.antlr.v4.runtime.misc.AbstractEqualityComparator; 10 import org.antlr.v4.runtime.misc.FlexibleHashMap; 11 import org.antlr.v4.runtime.misc.MurmurHash; 12 13 import java.util.BitSet; 14 import java.util.Collection; 15 import java.util.HashMap; 16 import java.util.Iterator; 17 import java.util.Map; 18 19 /** 20 * This enumeration defines the prediction modes available in ANTLR 4 along with 21 * utility methods for analyzing configuration sets for conflicts and/or 22 * ambiguities. 23 */ 24 public enum PredictionMode { 25 /** 26 * The SLL(*) prediction mode. This prediction mode ignores the current 27 * parser context when making predictions. This is the fastest prediction 28 * mode, and provides correct results for many grammars. This prediction 29 * mode is more powerful than the prediction mode provided by ANTLR 3, but 30 * may result in syntax errors for grammar and input combinations which are 31 * not SLL. 32 * 33 * <p> 34 * When using this prediction mode, the parser will either return a correct 35 * parse tree (i.e. the same parse tree that would be returned with the 36 * {@link #LL} prediction mode), or it will report a syntax error. If a 37 * syntax error is encountered when using the {@link #SLL} prediction mode, 38 * it may be due to either an actual syntax error in the input or indicate 39 * that the particular combination of grammar and input requires the more 40 * powerful {@link #LL} prediction abilities to complete successfully.</p> 41 * 42 * <p> 43 * This prediction mode does not provide any guarantees for prediction 44 * behavior for syntactically-incorrect inputs.</p> 45 */ 46 SLL, 47 /** 48 * The LL(*) prediction mode. This prediction mode allows the current parser 49 * context to be used for resolving SLL conflicts that occur during 50 * prediction. This is the fastest prediction mode that guarantees correct 51 * parse results for all combinations of grammars with syntactically correct 52 * inputs. 53 * 54 * <p> 55 * When using this prediction mode, the parser will make correct decisions 56 * for all syntactically-correct grammar and input combinations. However, in 57 * cases where the grammar is truly ambiguous this prediction mode might not 58 * report a precise answer for <em>exactly which</em> alternatives are 59 * ambiguous.</p> 60 * 61 * <p> 62 * This prediction mode does not provide any guarantees for prediction 63 * behavior for syntactically-incorrect inputs.</p> 64 */ 65 LL, 66 /** 67 * The LL(*) prediction mode with exact ambiguity detection. In addition to 68 * the correctness guarantees provided by the {@link #LL} prediction mode, 69 * this prediction mode instructs the prediction algorithm to determine the 70 * complete and exact set of ambiguous alternatives for every ambiguous 71 * decision encountered while parsing. 72 * 73 * <p> 74 * This prediction mode may be used for diagnosing ambiguities during 75 * grammar development. Due to the performance overhead of calculating sets 76 * of ambiguous alternatives, this prediction mode should be avoided when 77 * the exact results are not necessary.</p> 78 * 79 * <p> 80 * This prediction mode does not provide any guarantees for prediction 81 * behavior for syntactically-incorrect inputs.</p> 82 */ 83 LL_EXACT_AMBIG_DETECTION; 84 85 /** A Map that uses just the state and the stack context as the key. */ 86 static class AltAndContextMap extends FlexibleHashMap<ATNConfig,BitSet> { AltAndContextMap()87 public AltAndContextMap() { 88 super(AltAndContextConfigEqualityComparator.INSTANCE); 89 } 90 } 91 92 private static final class AltAndContextConfigEqualityComparator extends AbstractEqualityComparator<ATNConfig> { 93 public static final AltAndContextConfigEqualityComparator INSTANCE = new AltAndContextConfigEqualityComparator(); 94 AltAndContextConfigEqualityComparator()95 private AltAndContextConfigEqualityComparator() { 96 } 97 98 /** 99 * The hash code is only a function of the {@link ATNState#stateNumber} 100 * and {@link ATNConfig#context}. 101 */ 102 @Override hashCode(ATNConfig o)103 public int hashCode(ATNConfig o) { 104 int hashCode = MurmurHash.initialize(7); 105 hashCode = MurmurHash.update(hashCode, o.state.stateNumber); 106 hashCode = MurmurHash.update(hashCode, o.context); 107 hashCode = MurmurHash.finish(hashCode, 2); 108 return hashCode; 109 } 110 111 @Override equals(ATNConfig a, ATNConfig b)112 public boolean equals(ATNConfig a, ATNConfig b) { 113 if ( a==b ) return true; 114 if ( a==null || b==null ) return false; 115 return a.state.stateNumber==b.state.stateNumber 116 && a.context.equals(b.context); 117 } 118 } 119 120 /** 121 * Computes the SLL prediction termination condition. 122 * 123 * <p> 124 * This method computes the SLL prediction termination condition for both of 125 * the following cases.</p> 126 * 127 * <ul> 128 * <li>The usual SLL+LL fallback upon SLL conflict</li> 129 * <li>Pure SLL without LL fallback</li> 130 * </ul> 131 * 132 * <p><strong>COMBINED SLL+LL PARSING</strong></p> 133 * 134 * <p>When LL-fallback is enabled upon SLL conflict, correct predictions are 135 * ensured regardless of how the termination condition is computed by this 136 * method. Due to the substantially higher cost of LL prediction, the 137 * prediction should only fall back to LL when the additional lookahead 138 * cannot lead to a unique SLL prediction.</p> 139 * 140 * <p>Assuming combined SLL+LL parsing, an SLL configuration set with only 141 * conflicting subsets should fall back to full LL, even if the 142 * configuration sets don't resolve to the same alternative (e.g. 143 * {@code {1,2}} and {@code {3,4}}. If there is at least one non-conflicting 144 * configuration, SLL could continue with the hopes that more lookahead will 145 * resolve via one of those non-conflicting configurations.</p> 146 * 147 * <p>Here's the prediction termination rule them: SLL (for SLL+LL parsing) 148 * stops when it sees only conflicting configuration subsets. In contrast, 149 * full LL keeps going when there is uncertainty.</p> 150 * 151 * <p><strong>HEURISTIC</strong></p> 152 * 153 * <p>As a heuristic, we stop prediction when we see any conflicting subset 154 * unless we see a state that only has one alternative associated with it. 155 * The single-alt-state thing lets prediction continue upon rules like 156 * (otherwise, it would admit defeat too soon):</p> 157 * 158 * <p>{@code [12|1|[], 6|2|[], 12|2|[]]. s : (ID | ID ID?) ';' ;}</p> 159 * 160 * <p>When the ATN simulation reaches the state before {@code ';'}, it has a 161 * DFA state that looks like: {@code [12|1|[], 6|2|[], 12|2|[]]}. Naturally 162 * {@code 12|1|[]} and {@code 12|2|[]} conflict, but we cannot stop 163 * processing this node because alternative to has another way to continue, 164 * via {@code [6|2|[]]}.</p> 165 * 166 * <p>It also let's us continue for this rule:</p> 167 * 168 * <p>{@code [1|1|[], 1|2|[], 8|3|[]] a : A | A | A B ;}</p> 169 * 170 * <p>After matching input A, we reach the stop state for rule A, state 1. 171 * State 8 is the state right before B. Clearly alternatives 1 and 2 172 * conflict and no amount of further lookahead will separate the two. 173 * However, alternative 3 will be able to continue and so we do not stop 174 * working on this state. In the previous example, we're concerned with 175 * states associated with the conflicting alternatives. Here alt 3 is not 176 * associated with the conflicting configs, but since we can continue 177 * looking for input reasonably, don't declare the state done.</p> 178 * 179 * <p><strong>PURE SLL PARSING</strong></p> 180 * 181 * <p>To handle pure SLL parsing, all we have to do is make sure that we 182 * combine stack contexts for configurations that differ only by semantic 183 * predicate. From there, we can do the usual SLL termination heuristic.</p> 184 * 185 * <p><strong>PREDICATES IN SLL+LL PARSING</strong></p> 186 * 187 * <p>SLL decisions don't evaluate predicates until after they reach DFA stop 188 * states because they need to create the DFA cache that works in all 189 * semantic situations. In contrast, full LL evaluates predicates collected 190 * during start state computation so it can ignore predicates thereafter. 191 * This means that SLL termination detection can totally ignore semantic 192 * predicates.</p> 193 * 194 * <p>Implementation-wise, {@link ATNConfigSet} combines stack contexts but not 195 * semantic predicate contexts so we might see two configurations like the 196 * following.</p> 197 * 198 * <p>{@code (s, 1, x, {}), (s, 1, x', {p})}</p> 199 * 200 * <p>Before testing these configurations against others, we have to merge 201 * {@code x} and {@code x'} (without modifying the existing configurations). 202 * For example, we test {@code (x+x')==x''} when looking for conflicts in 203 * the following configurations.</p> 204 * 205 * <p>{@code (s, 1, x, {}), (s, 1, x', {p}), (s, 2, x'', {})}</p> 206 * 207 * <p>If the configuration set has predicates (as indicated by 208 * {@link ATNConfigSet#hasSemanticContext}), this algorithm makes a copy of 209 * the configurations to strip out all of the predicates so that a standard 210 * {@link ATNConfigSet} will merge everything ignoring predicates.</p> 211 */ hasSLLConflictTerminatingPrediction(PredictionMode mode, ATNConfigSet configs)212 public static boolean hasSLLConflictTerminatingPrediction(PredictionMode mode, ATNConfigSet configs) { 213 /* Configs in rule stop states indicate reaching the end of the decision 214 * rule (local context) or end of start rule (full context). If all 215 * configs meet this condition, then none of the configurations is able 216 * to match additional input so we terminate prediction. 217 */ 218 if (allConfigsInRuleStopStates(configs)) { 219 return true; 220 } 221 222 // pure SLL mode parsing 223 if ( mode == PredictionMode.SLL ) { 224 // Don't bother with combining configs from different semantic 225 // contexts if we can fail over to full LL; costs more time 226 // since we'll often fail over anyway. 227 if ( configs.hasSemanticContext ) { 228 // dup configs, tossing out semantic predicates 229 ATNConfigSet dup = new ATNConfigSet(); 230 for (ATNConfig c : configs) { 231 c = new ATNConfig(c,SemanticContext.NONE); 232 dup.add(c); 233 } 234 configs = dup; 235 } 236 // now we have combined contexts for configs with dissimilar preds 237 } 238 239 // pure SLL or combined SLL+LL mode parsing 240 241 Collection<BitSet> altsets = getConflictingAltSubsets(configs); 242 boolean heuristic = 243 hasConflictingAltSet(altsets) && !hasStateAssociatedWithOneAlt(configs); 244 return heuristic; 245 } 246 247 /** 248 * Checks if any configuration in {@code configs} is in a 249 * {@link RuleStopState}. Configurations meeting this condition have reached 250 * the end of the decision rule (local context) or end of start rule (full 251 * context). 252 * 253 * @param configs the configuration set to test 254 * @return {@code true} if any configuration in {@code configs} is in a 255 * {@link RuleStopState}, otherwise {@code false} 256 */ hasConfigInRuleStopState(ATNConfigSet configs)257 public static boolean hasConfigInRuleStopState(ATNConfigSet configs) { 258 for (ATNConfig c : configs) { 259 if (c.state instanceof RuleStopState) { 260 return true; 261 } 262 } 263 264 return false; 265 } 266 267 /** 268 * Checks if all configurations in {@code configs} are in a 269 * {@link RuleStopState}. Configurations meeting this condition have reached 270 * the end of the decision rule (local context) or end of start rule (full 271 * context). 272 * 273 * @param configs the configuration set to test 274 * @return {@code true} if all configurations in {@code configs} are in a 275 * {@link RuleStopState}, otherwise {@code false} 276 */ allConfigsInRuleStopStates(ATNConfigSet configs)277 public static boolean allConfigsInRuleStopStates(ATNConfigSet configs) { 278 for (ATNConfig config : configs) { 279 if (!(config.state instanceof RuleStopState)) { 280 return false; 281 } 282 } 283 284 return true; 285 } 286 287 /** 288 * Full LL prediction termination. 289 * 290 * <p>Can we stop looking ahead during ATN simulation or is there some 291 * uncertainty as to which alternative we will ultimately pick, after 292 * consuming more input? Even if there are partial conflicts, we might know 293 * that everything is going to resolve to the same minimum alternative. That 294 * means we can stop since no more lookahead will change that fact. On the 295 * other hand, there might be multiple conflicts that resolve to different 296 * minimums. That means we need more look ahead to decide which of those 297 * alternatives we should predict.</p> 298 * 299 * <p>The basic idea is to split the set of configurations {@code C}, into 300 * conflicting subsets {@code (s, _, ctx, _)} and singleton subsets with 301 * non-conflicting configurations. Two configurations conflict if they have 302 * identical {@link ATNConfig#state} and {@link ATNConfig#context} values 303 * but different {@link ATNConfig#alt} value, e.g. {@code (s, i, ctx, _)} 304 * and {@code (s, j, ctx, _)} for {@code i!=j}.</p> 305 * 306 * <p>Reduce these configuration subsets to the set of possible alternatives. 307 * You can compute the alternative subsets in one pass as follows:</p> 308 * 309 * <p>{@code A_s,ctx = {i | (s, i, ctx, _)}} for each configuration in 310 * {@code C} holding {@code s} and {@code ctx} fixed.</p> 311 * 312 * <p>Or in pseudo-code, for each configuration {@code c} in {@code C}:</p> 313 * 314 * <pre> 315 * map[c] U= c.{@link ATNConfig#alt alt} # map hash/equals uses s and x, not 316 * alt and not pred 317 * </pre> 318 * 319 * <p>The values in {@code map} are the set of {@code A_s,ctx} sets.</p> 320 * 321 * <p>If {@code |A_s,ctx|=1} then there is no conflict associated with 322 * {@code s} and {@code ctx}.</p> 323 * 324 * <p>Reduce the subsets to singletons by choosing a minimum of each subset. If 325 * the union of these alternative subsets is a singleton, then no amount of 326 * more lookahead will help us. We will always pick that alternative. If, 327 * however, there is more than one alternative, then we are uncertain which 328 * alternative to predict and must continue looking for resolution. We may 329 * or may not discover an ambiguity in the future, even if there are no 330 * conflicting subsets this round.</p> 331 * 332 * <p>The biggest sin is to terminate early because it means we've made a 333 * decision but were uncertain as to the eventual outcome. We haven't used 334 * enough lookahead. On the other hand, announcing a conflict too late is no 335 * big deal; you will still have the conflict. It's just inefficient. It 336 * might even look until the end of file.</p> 337 * 338 * <p>No special consideration for semantic predicates is required because 339 * predicates are evaluated on-the-fly for full LL prediction, ensuring that 340 * no configuration contains a semantic context during the termination 341 * check.</p> 342 * 343 * <p><strong>CONFLICTING CONFIGS</strong></p> 344 * 345 * <p>Two configurations {@code (s, i, x)} and {@code (s, j, x')}, conflict 346 * when {@code i!=j} but {@code x=x'}. Because we merge all 347 * {@code (s, i, _)} configurations together, that means that there are at 348 * most {@code n} configurations associated with state {@code s} for 349 * {@code n} possible alternatives in the decision. The merged stacks 350 * complicate the comparison of configuration contexts {@code x} and 351 * {@code x'}. Sam checks to see if one is a subset of the other by calling 352 * merge and checking to see if the merged result is either {@code x} or 353 * {@code x'}. If the {@code x} associated with lowest alternative {@code i} 354 * is the superset, then {@code i} is the only possible prediction since the 355 * others resolve to {@code min(i)} as well. However, if {@code x} is 356 * associated with {@code j>i} then at least one stack configuration for 357 * {@code j} is not in conflict with alternative {@code i}. The algorithm 358 * should keep going, looking for more lookahead due to the uncertainty.</p> 359 * 360 * <p>For simplicity, I'm doing a equality check between {@code x} and 361 * {@code x'} that lets the algorithm continue to consume lookahead longer 362 * than necessary. The reason I like the equality is of course the 363 * simplicity but also because that is the test you need to detect the 364 * alternatives that are actually in conflict.</p> 365 * 366 * <p><strong>CONTINUE/STOP RULE</strong></p> 367 * 368 * <p>Continue if union of resolved alternative sets from non-conflicting and 369 * conflicting alternative subsets has more than one alternative. We are 370 * uncertain about which alternative to predict.</p> 371 * 372 * <p>The complete set of alternatives, {@code [i for (_,i,_)]}, tells us which 373 * alternatives are still in the running for the amount of input we've 374 * consumed at this point. The conflicting sets let us to strip away 375 * configurations that won't lead to more states because we resolve 376 * conflicts to the configuration with a minimum alternate for the 377 * conflicting set.</p> 378 * 379 * <p><strong>CASES</strong></p> 380 * 381 * <ul> 382 * 383 * <li>no conflicts and more than 1 alternative in set => continue</li> 384 * 385 * <li> {@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s, 3, z)}, 386 * {@code (s', 1, y)}, {@code (s', 2, y)} yields non-conflicting set 387 * {@code {3}} U conflicting sets {@code min({1,2})} U {@code min({1,2})} = 388 * {@code {1,3}} => continue 389 * </li> 390 * 391 * <li>{@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 1, y)}, 392 * {@code (s', 2, y)}, {@code (s'', 1, z)} yields non-conflicting set 393 * {@code {1}} U conflicting sets {@code min({1,2})} U {@code min({1,2})} = 394 * {@code {1}} => stop and predict 1</li> 395 * 396 * <li>{@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 1, y)}, 397 * {@code (s', 2, y)} yields conflicting, reduced sets {@code {1}} U 398 * {@code {1}} = {@code {1}} => stop and predict 1, can announce 399 * ambiguity {@code {1,2}}</li> 400 * 401 * <li>{@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 2, y)}, 402 * {@code (s', 3, y)} yields conflicting, reduced sets {@code {1}} U 403 * {@code {2}} = {@code {1,2}} => continue</li> 404 * 405 * <li>{@code (s, 1, x)}, {@code (s, 2, x)}, {@code (s', 3, y)}, 406 * {@code (s', 4, y)} yields conflicting, reduced sets {@code {1}} U 407 * {@code {3}} = {@code {1,3}} => continue</li> 408 * 409 * </ul> 410 * 411 * <p><strong>EXACT AMBIGUITY DETECTION</strong></p> 412 * 413 * <p>If all states report the same conflicting set of alternatives, then we 414 * know we have the exact ambiguity set.</p> 415 * 416 * <p><code>|A_<em>i</em>|>1</code> and 417 * <code>A_<em>i</em> = A_<em>j</em></code> for all <em>i</em>, <em>j</em>.</p> 418 * 419 * <p>In other words, we continue examining lookahead until all {@code A_i} 420 * have more than one alternative and all {@code A_i} are the same. If 421 * {@code A={{1,2}, {1,3}}}, then regular LL prediction would terminate 422 * because the resolved set is {@code {1}}. To determine what the real 423 * ambiguity is, we have to know whether the ambiguity is between one and 424 * two or one and three so we keep going. We can only stop prediction when 425 * we need exact ambiguity detection when the sets look like 426 * {@code A={{1,2}}} or {@code {{1,2},{1,2}}}, etc...</p> 427 */ resolvesToJustOneViableAlt(Collection<BitSet> altsets)428 public static int resolvesToJustOneViableAlt(Collection<BitSet> altsets) { 429 return getSingleViableAlt(altsets); 430 } 431 432 /** 433 * Determines if every alternative subset in {@code altsets} contains more 434 * than one alternative. 435 * 436 * @param altsets a collection of alternative subsets 437 * @return {@code true} if every {@link BitSet} in {@code altsets} has 438 * {@link BitSet#cardinality cardinality} > 1, otherwise {@code false} 439 */ allSubsetsConflict(Collection<BitSet> altsets)440 public static boolean allSubsetsConflict(Collection<BitSet> altsets) { 441 return !hasNonConflictingAltSet(altsets); 442 } 443 444 /** 445 * Determines if any single alternative subset in {@code altsets} contains 446 * exactly one alternative. 447 * 448 * @param altsets a collection of alternative subsets 449 * @return {@code true} if {@code altsets} contains a {@link BitSet} with 450 * {@link BitSet#cardinality cardinality} 1, otherwise {@code false} 451 */ hasNonConflictingAltSet(Collection<BitSet> altsets)452 public static boolean hasNonConflictingAltSet(Collection<BitSet> altsets) { 453 for (BitSet alts : altsets) { 454 if ( alts.cardinality()==1 ) { 455 return true; 456 } 457 } 458 return false; 459 } 460 461 /** 462 * Determines if any single alternative subset in {@code altsets} contains 463 * more than one alternative. 464 * 465 * @param altsets a collection of alternative subsets 466 * @return {@code true} if {@code altsets} contains a {@link BitSet} with 467 * {@link BitSet#cardinality cardinality} > 1, otherwise {@code false} 468 */ hasConflictingAltSet(Collection<BitSet> altsets)469 public static boolean hasConflictingAltSet(Collection<BitSet> altsets) { 470 for (BitSet alts : altsets) { 471 if ( alts.cardinality()>1 ) { 472 return true; 473 } 474 } 475 return false; 476 } 477 478 /** 479 * Determines if every alternative subset in {@code altsets} is equivalent. 480 * 481 * @param altsets a collection of alternative subsets 482 * @return {@code true} if every member of {@code altsets} is equal to the 483 * others, otherwise {@code false} 484 */ allSubsetsEqual(Collection<BitSet> altsets)485 public static boolean allSubsetsEqual(Collection<BitSet> altsets) { 486 Iterator<BitSet> it = altsets.iterator(); 487 BitSet first = it.next(); 488 while ( it.hasNext() ) { 489 BitSet next = it.next(); 490 if ( !next.equals(first) ) return false; 491 } 492 return true; 493 } 494 495 /** 496 * Returns the unique alternative predicted by all alternative subsets in 497 * {@code altsets}. If no such alternative exists, this method returns 498 * {@link ATN#INVALID_ALT_NUMBER}. 499 * 500 * @param altsets a collection of alternative subsets 501 */ getUniqueAlt(Collection<BitSet> altsets)502 public static int getUniqueAlt(Collection<BitSet> altsets) { 503 BitSet all = getAlts(altsets); 504 if ( all.cardinality()==1 ) return all.nextSetBit(0); 505 return ATN.INVALID_ALT_NUMBER; 506 } 507 508 /** 509 * Gets the complete set of represented alternatives for a collection of 510 * alternative subsets. This method returns the union of each {@link BitSet} 511 * in {@code altsets}. 512 * 513 * @param altsets a collection of alternative subsets 514 * @return the set of represented alternatives in {@code altsets} 515 */ getAlts(Collection<BitSet> altsets)516 public static BitSet getAlts(Collection<BitSet> altsets) { 517 BitSet all = new BitSet(); 518 for (BitSet alts : altsets) { 519 all.or(alts); 520 } 521 return all; 522 } 523 524 /** 525 * Get union of all alts from configs. 526 * 527 * @since 4.5.1 528 */ getAlts(ATNConfigSet configs)529 public static BitSet getAlts(ATNConfigSet configs) { 530 BitSet alts = new BitSet(); 531 for (ATNConfig config : configs) { 532 alts.set(config.alt); 533 } 534 return alts; 535 } 536 537 /** 538 * This function gets the conflicting alt subsets from a configuration set. 539 * For each configuration {@code c} in {@code configs}: 540 * 541 * <pre> 542 * map[c] U= c.{@link ATNConfig#alt alt} # map hash/equals uses s and x, not 543 * alt and not pred 544 * </pre> 545 */ getConflictingAltSubsets(ATNConfigSet configs)546 public static Collection<BitSet> getConflictingAltSubsets(ATNConfigSet configs) { 547 AltAndContextMap configToAlts = new AltAndContextMap(); 548 for (ATNConfig c : configs) { 549 BitSet alts = configToAlts.get(c); 550 if ( alts==null ) { 551 alts = new BitSet(); 552 configToAlts.put(c, alts); 553 } 554 alts.set(c.alt); 555 } 556 return configToAlts.values(); 557 } 558 559 /** 560 * Get a map from state to alt subset from a configuration set. For each 561 * configuration {@code c} in {@code configs}: 562 * 563 * <pre> 564 * map[c.{@link ATNConfig#state state}] U= c.{@link ATNConfig#alt alt} 565 * </pre> 566 */ getStateToAltMap(ATNConfigSet configs)567 public static Map<ATNState, BitSet> getStateToAltMap(ATNConfigSet configs) { 568 Map<ATNState, BitSet> m = new HashMap<ATNState, BitSet>(); 569 for (ATNConfig c : configs) { 570 BitSet alts = m.get(c.state); 571 if ( alts==null ) { 572 alts = new BitSet(); 573 m.put(c.state, alts); 574 } 575 alts.set(c.alt); 576 } 577 return m; 578 } 579 hasStateAssociatedWithOneAlt(ATNConfigSet configs)580 public static boolean hasStateAssociatedWithOneAlt(ATNConfigSet configs) { 581 Map<ATNState, BitSet> x = getStateToAltMap(configs); 582 for (BitSet alts : x.values()) { 583 if ( alts.cardinality()==1 ) return true; 584 } 585 return false; 586 } 587 getSingleViableAlt(Collection<BitSet> altsets)588 public static int getSingleViableAlt(Collection<BitSet> altsets) { 589 BitSet viableAlts = new BitSet(); 590 for (BitSet alts : altsets) { 591 int minAlt = alts.nextSetBit(0); 592 viableAlts.set(minAlt); 593 if ( viableAlts.cardinality()>1 ) { // more than 1 viable alt 594 return ATN.INVALID_ALT_NUMBER; 595 } 596 } 597 return viableAlts.nextSetBit(0); 598 } 599 600 } 601