const PredictionModeSLL … const PredictionModeLL … const PredictionModeLLExactAmbigDetection … // PredictionModehasSLLConflictTerminatingPrediction computes the SLL prediction termination condition. // // This method computes the SLL prediction termination condition for both of // the following cases: // // - The usual SLL+LL fallback upon SLL conflict // - Pure SLL without LL fallback // // # Combined SLL+LL Parsing // // When LL-fallback is enabled upon SLL conflict, correct predictions are // ensured regardless of how the termination condition is computed by this // method. Due to the substantially higher cost of LL prediction, the // prediction should only fall back to LL when the additional lookahead // cannot lead to a unique SLL prediction. // // Assuming combined SLL+LL parsing, an SLL configuration set with only // conflicting subsets should fall back to full LL, even if the // configuration sets don't resolve to the same alternative, e.g. // // {1,2} and {3,4} // // If there is at least one non-conflicting // configuration, SLL could continue with the hopes that more lookahead will // resolve via one of those non-conflicting configurations. // // Here's the prediction termination rule them: SLL (for SLL+LL parsing) // stops when it sees only conflicting configuration subsets. In contrast, // full LL keeps going when there is uncertainty. // // # Heuristic // // As a heuristic, we stop prediction when we see any conflicting subset // unless we see a state that only has one alternative associated with it. // The single-alt-state thing lets prediction continue upon rules like // (otherwise, it would admit defeat too soon): // // [12|1|[], 6|2|[], 12|2|[]]. s : (ID | ID ID?) ; // // When the [ATN] simulation reaches the state before ';', it has a // [DFA] state that looks like: // // [12|1|[], 6|2|[], 12|2|[]] // // Naturally // // 12|1|[] and 12|2|[] // // conflict, but we cannot stop processing this node because alternative to has another way to continue, // via // // [6|2|[]] // // It also let's us continue for this rule: // // [1|1|[], 1|2|[], 8|3|[]] a : A | A | A B ; // // After Matching input A, we reach the stop state for rule A, state 1. // State 8 is the state immediately before B. Clearly alternatives 1 and 2 // conflict and no amount of further lookahead will separate the two. // However, alternative 3 will be able to continue, and so we do not stop // working on this state. In the previous example, we're concerned with // states associated with the conflicting alternatives. Here alt 3 is not // associated with the conflicting configs, but since we can continue // looking for input reasonably, don't declare the state done. // // # Pure SLL Parsing // // To handle pure SLL parsing, all we have to do is make sure that we // combine stack contexts for configurations that differ only by semantic // predicate. From there, we can do the usual SLL termination heuristic. // // # Predicates in SLL+LL Parsing // // SLL decisions don't evaluate predicates until after they reach [DFA] stop // states because they need to create the [DFA] cache that works in all // semantic situations. In contrast, full LL evaluates predicates collected // during start state computation, so it can ignore predicates thereafter. // This means that SLL termination detection can totally ignore semantic // predicates. // // Implementation-wise, [ATNConfigSet] combines stack contexts but not // semantic predicate contexts, so we might see two configurations like the // following: // // (s, 1, x, {}), (s, 1, x', {p}) // // Before testing these configurations against others, we have to merge // x and x' (without modifying the existing configurations). // For example, we test (x+x')==x” when looking for conflicts in // the following configurations: // // (s, 1, x, {}), (s, 1, x', {p}), (s, 2, x”, {}) // // If the configuration set has predicates (as indicated by // [ATNConfigSet.hasSemanticContext]), this algorithm makes a copy of // the configurations to strip out all the predicates so that a standard // [ATNConfigSet] will merge everything ignoring predicates. func PredictionModehasSLLConflictTerminatingPrediction(mode int, configs *ATNConfigSet) bool { … } // PredictionModehasConfigInRuleStopState checks if any configuration in the given configs is in a // [RuleStopState]. Configurations meeting this condition have reached // the end of the decision rule (local context) or end of start rule (full // context). // // The func returns true if any configuration in the supplied configs is in a [RuleStopState] func PredictionModehasConfigInRuleStopState(configs *ATNConfigSet) bool { … } // PredictionModeallConfigsInRuleStopStates checks if all configurations in configs are in a // [RuleStopState]. Configurations meeting this condition have reached // the end of the decision rule (local context) or end of start rule (full // context). // // the func returns true if all configurations in configs are in a // [RuleStopState] func PredictionModeallConfigsInRuleStopStates(configs *ATNConfigSet) bool { … } // PredictionModeresolvesToJustOneViableAlt checks full LL prediction termination. // // Can we stop looking ahead during [ATN] simulation or is there some // uncertainty as to which alternative we will ultimately pick, after // consuming more input? Even if there are partial conflicts, we might know // that everything is going to resolve to the same minimum alternative. That // means we can stop since no more lookahead will change that fact. On the // other hand, there might be multiple conflicts that resolve to different // minimums. That means we need more look ahead to decide which of those // alternatives we should predict. // // The basic idea is to split the set of configurations 'C', into // conflicting subsets (s, _, ctx, _) and singleton subsets with // non-conflicting configurations. Two configurations conflict if they have // identical [ATNConfig].state and [ATNConfig].context values // but a different [ATNConfig].alt value, e.g. // // (s, i, ctx, _) // // and // // (s, j, ctx, _) ; for i != j // // Reduce these configuration subsets to the set of possible alternatives. // You can compute the alternative subsets in one pass as follows: // // A_s,ctx = {i | (s, i, ctx, _)} // // for each configuration in C holding s and ctx fixed. // // Or in pseudo-code: // // for each configuration c in C: // map[c] U = c.ATNConfig.alt alt // map hash/equals uses s and x, not alt and not pred // // The values in map are the set of // // A_s,ctx // // sets. // // If // // |A_s,ctx| = 1 // // then there is no conflict associated with s and ctx. // // Reduce the subsets to singletons by choosing a minimum of each subset. If // the union of these alternative subsets is a singleton, then no amount of // further lookahead will help us. We will always pick that alternative. If, // however, there is more than one alternative, then we are uncertain which // alternative to predict and must continue looking for resolution. We may // or may not discover an ambiguity in the future, even if there are no // conflicting subsets this round. // // The biggest sin is to terminate early because it means we've made a // decision but were uncertain as to the eventual outcome. We haven't used // enough lookahead. On the other hand, announcing a conflict too late is no // big deal; you will still have the conflict. It's just inefficient. It // might even look until the end of file. // // No special consideration for semantic predicates is required because // predicates are evaluated on-the-fly for full LL prediction, ensuring that // no configuration contains a semantic context during the termination // check. // // # Conflicting Configs // // Two configurations: // // (s, i, x) and (s, j, x') // // conflict when i != j but x = x'. Because we merge all // (s, i, _) configurations together, that means that there are at // most n configurations associated with state s for // n possible alternatives in the decision. The merged stacks // complicate the comparison of configuration contexts x and x'. // // Sam checks to see if one is a subset of the other by calling // merge and checking to see if the merged result is either x or x'. // If the x associated with lowest alternative i // is the superset, then i is the only possible prediction since the // others resolve to min(i) as well. However, if x is // associated with j > i then at least one stack configuration for // j is not in conflict with alternative i. The algorithm // should keep going, looking for more lookahead due to the uncertainty. // // For simplicity, I'm doing an equality check between x and // x', which lets the algorithm continue to consume lookahead longer // than necessary. The reason I like the equality is of course the // simplicity but also because that is the test you need to detect the // alternatives that are actually in conflict. // // # Continue/Stop Rule // // Continue if the union of resolved alternative sets from non-conflicting and // conflicting alternative subsets has more than one alternative. We are // uncertain about which alternative to predict. // // The complete set of alternatives, // // [i for (_, i, _)] // // tells us which alternatives are still in the running for the amount of input we've // consumed at this point. The conflicting sets let us to strip away // configurations that won't lead to more states because we resolve // conflicts to the configuration with a minimum alternate for the // conflicting set. // // Cases // // - no conflicts and more than 1 alternative in set => continue // - (s, 1, x), (s, 2, x), (s, 3, z), (s', 1, y), (s', 2, y) yields non-conflicting set // {3} ∪ conflicting sets min({1,2}) ∪ min({1,2}) = {1,3} => continue // - (s, 1, x), (s, 2, x), (s', 1, y), (s', 2, y), (s”, 1, z) yields non-conflicting set // {1} ∪ conflicting sets min({1,2}) ∪ min({1,2}) = {1} => stop and predict 1 // - (s, 1, x), (s, 2, x), (s', 1, y), (s', 2, y) yields conflicting, reduced sets // {1} ∪ {1} = {1} => stop and predict 1, can announce ambiguity {1,2} // - (s, 1, x), (s, 2, x), (s', 2, y), (s', 3, y) yields conflicting, reduced sets // {1} ∪ {2} = {1,2} => continue // - (s, 1, x), (s, 2, x), (s', 2, y), (s', 3, y) yields conflicting, reduced sets // {1} ∪ {2} = {1,2} => continue // - (s, 1, x), (s, 2, x), (s', 3, y), (s', 4, y) yields conflicting, reduced sets // {1} ∪ {3} = {1,3} => continue // // # Exact Ambiguity Detection // // If all states report the same conflicting set of alternatives, then we // know we have the exact ambiguity set: // // |A_i| > 1 // // and // // A_i = A_j ; for all i, j // // In other words, we continue examining lookahead until all A_i // have more than one alternative and all A_i are the same. If // // A={{1,2}, {1,3}} // // then regular LL prediction would terminate because the resolved set is {1}. // To determine what the real ambiguity is, we have to know whether the ambiguity is between one and // two or one and three so we keep going. We can only stop prediction when // we need exact ambiguity detection when the sets look like: // // A={{1,2}} // // or // // {{1,2},{1,2}}, etc... func PredictionModeresolvesToJustOneViableAlt(altsets []*BitSet) int { … } // PredictionModeallSubsetsConflict determines if every alternative subset in altsets contains more // than one alternative. // // The func returns true if every [BitSet] in altsets has // [BitSet].cardinality cardinality > 1 func PredictionModeallSubsetsConflict(altsets []*BitSet) bool { … } // PredictionModehasNonConflictingAltSet determines if any single alternative subset in altsets contains // exactly one alternative. // // The func returns true if altsets contains at least one [BitSet] with // [BitSet].cardinality cardinality 1 func PredictionModehasNonConflictingAltSet(altsets []*BitSet) bool { … } // PredictionModehasConflictingAltSet determines if any single alternative subset in altsets contains // more than one alternative. // // The func returns true if altsets contains a [BitSet] with // [BitSet].cardinality cardinality > 1, otherwise false func PredictionModehasConflictingAltSet(altsets []*BitSet) bool { … } // PredictionModeallSubsetsEqual determines if every alternative subset in altsets is equivalent. // // The func returns true if every member of altsets is equal to the others. func PredictionModeallSubsetsEqual(altsets []*BitSet) bool { … } // PredictionModegetUniqueAlt returns the unique alternative predicted by all alternative subsets in // altsets. If no such alternative exists, this method returns // [ATNInvalidAltNumber]. // // @param altsets a collection of alternative subsets func PredictionModegetUniqueAlt(altsets []*BitSet) int { … } // PredictionModeGetAlts returns the complete set of represented alternatives for a collection of // alternative subsets. This method returns the union of each [BitSet] // in altsets, being the set of represented alternatives in altsets. func PredictionModeGetAlts(altsets []*BitSet) *BitSet { … } // PredictionModegetConflictingAltSubsets gets the conflicting alt subsets from a configuration set. // // for each configuration c in configs: // map[c] U= c.ATNConfig.alt // map hash/equals uses s and x, not alt and not pred func PredictionModegetConflictingAltSubsets(configs *ATNConfigSet) []*BitSet { … } // PredictionModeGetStateToAltMap gets a map from state to alt subset from a configuration set. // // for each configuration c in configs: // map[c.ATNConfig.state] U= c.ATNConfig.alt} func PredictionModeGetStateToAltMap(configs *ATNConfigSet) *AltDict { … } func PredictionModehasStateAssociatedWithOneAlt(configs *ATNConfigSet) bool { … } // PredictionModegetSingleViableAlt gets the single alternative predicted by all alternative subsets in altsets // if there is one. // // TODO: JI - Review this code - it does not seem to do the same thing as the Java code - maybe because [BitSet] is not like the Java utils BitSet func PredictionModegetSingleViableAlt(altsets []*BitSet) int { … }
Codebase Browser
kubernetes