type ClosureBusy … // NewClosureBusy creates a new ClosureBusy instance used to avoid infinite recursion for right-recursive rules func NewClosureBusy(desc string) *ClosureBusy { … } func (c *ClosureBusy) Put(config *ATNConfig) (*ATNConfig, bool) { … } type ParserATNSimulator … //goland:noinspection GoUnusedExportedFunction func NewParserATNSimulator(parser Parser, atn *ATN, decisionToDFA []*DFA, sharedContextCache *PredictionContextCache) *ParserATNSimulator { … } func (p *ParserATNSimulator) GetPredictionMode() int { … } func (p *ParserATNSimulator) SetPredictionMode(v int) { … } func (p *ParserATNSimulator) reset() { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) AdaptivePredict(parser *BaseParser, input TokenStream, decision int, outerContext ParserRuleContext) int { … } // execATN performs ATN simulation to compute a predicted alternative based // upon the remaining input, but also updates the DFA cache to avoid // having to traverse the ATN again for the same input sequence. // // There are some key conditions we're looking for after computing a new // set of ATN configs (proposed DFA state): // // - If the set is empty, there is no viable alternative for current symbol // - Does the state uniquely predict an alternative? // - Does the state have a conflict that would prevent us from // putting it on the work list? // // We also have some key operations to do: // // - Add an edge from previous DFA state to potentially NewDFA state, D, // - Upon current symbol but only if adding to work list, which means in all // cases except no viable alternative (and possibly non-greedy decisions?) // - Collecting predicates and adding semantic context to DFA accept states // - adding rule context to context-sensitive DFA accept states // - Consuming an input symbol // - Reporting a conflict // - Reporting an ambiguity // - Reporting a context sensitivity // - Reporting insufficient predicates // // Cover these cases: // // - dead end // - single alt // - single alt + predicates // - conflict // - conflict + predicates // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) execATN(dfa *DFA, s0 *DFAState, input TokenStream, startIndex int, outerContext ParserRuleContext) (int, RecognitionException) { … } func (p *ParserATNSimulator) getExistingTargetState(previousD *DFAState, t int) *DFAState { … } // Compute a target state for an edge in the DFA, and attempt to add the // computed state and corresponding edge to the DFA. // // @param dfa The DFA // @param previousD The current DFA state // @param t The next input symbol // // @return The computed target DFA state for the given input symbol // {@code t}. If {@code t} does not lead to a valid DFA state, p method // returns {@link //ERROR}. // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) computeTargetState(dfa *DFA, previousD *DFAState, t int) *DFAState { … } func (p *ParserATNSimulator) predicateDFAState(dfaState *DFAState, decisionState DecisionState) { … } // comes back with reach.uniqueAlt set to a valid alt // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) execATNWithFullContext(dfa *DFA, D *DFAState, s0 *ATNConfigSet, input TokenStream, startIndex int, outerContext ParserRuleContext) (int, RecognitionException) { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) computeReachSet(closure *ATNConfigSet, t int, fullCtx bool) *ATNConfigSet { … } // removeAllConfigsNotInRuleStopState returns a configuration set containing only the configurations from // configs which are in a [RuleStopState]. If all // configurations in configs are already in a rule stop state, this // method simply returns configs. // // When lookToEndOfRule is true, this method uses // [ATN].[NextTokens] for each configuration in configs which is // not already in a rule stop state to see if a rule stop state is reachable // from the configuration via epsilon-only transitions. // // When lookToEndOfRule is true, this method checks for rule stop states // reachable by epsilon-only transitions from each configuration in // configs. // // The func returns configs if all configurations in configs are in a // rule stop state, otherwise it returns a new configuration set containing only // the configurations from configs which are in a rule stop state func (p *ParserATNSimulator) removeAllConfigsNotInRuleStopState(configs *ATNConfigSet, lookToEndOfRule bool) *ATNConfigSet { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) computeStartState(a ATNState, ctx RuleContext, fullCtx bool) *ATNConfigSet { … } // applyPrecedenceFilter transforms the start state computed by // [computeStartState] to the special start state used by a // precedence [DFA] for a particular precedence value. The transformation // process applies the following changes to the start state's configuration // set. // // 1. Evaluate the precedence predicates for each configuration using // [SemanticContext].evalPrecedence. // 2. Remove all configurations which predict an alternative greater than // 1, for which another configuration that predicts alternative 1 is in the // same ATN state with the same prediction context. // // Transformation 2 is valid for the following reasons: // // - The closure block cannot contain any epsilon transitions which bypass // the body of the closure, so all states reachable via alternative 1 are // part of the precedence alternatives of the transformed left-recursive // rule. // - The "primary" portion of a left recursive rule cannot contain an // epsilon transition, so the only way an alternative other than 1 can exist // in a state that is also reachable via alternative 1 is by nesting calls // to the left-recursive rule, with the outer calls not being at the // preferred precedence level. // // The prediction context must be considered by this filter to address // situations like the following: // // grammar TA // prog: statement* EOF // statement: letterA | statement letterA 'b' // letterA: 'a' // // In the above grammar, the [ATN] state immediately before the token // reference 'a' in letterA is reachable from the left edge // of both the primary and closure blocks of the left-recursive rule // statement. The prediction context associated with each of these // configurations distinguishes between them, and prevents the alternative // which stepped out to prog, and then back in to statement // from being eliminated by the filter. // // The func returns the transformed configuration set representing the start state // for a precedence [DFA] at a particular precedence level (determined by // calling [Parser].getPrecedence). func (p *ParserATNSimulator) applyPrecedenceFilter(configs *ATNConfigSet) *ATNConfigSet { … } func (p *ParserATNSimulator) getReachableTarget(trans Transition, ttype int) ATNState { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) getPredsForAmbigAlts(ambigAlts *BitSet, configs *ATNConfigSet, nalts int) []SemanticContext { … } func (p *ParserATNSimulator) getPredicatePredictions(ambigAlts *BitSet, altToPred []SemanticContext) []*PredPrediction { … } // getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule is used to improve the localization of error messages by // choosing an alternative rather than panic a NoViableAltException in particular prediction scenarios where the // Error state was reached during [ATN] simulation. // // The default implementation of this method uses the following // algorithm to identify an [ATN] configuration which successfully parsed the // decision entry rule. Choosing such an alternative ensures that the // [ParserRuleContext] returned by the calling rule will be complete // and valid, and the syntax error will be Reported later at a more // localized location. // // - If a syntactically valid path or paths reach the end of the decision rule, and // they are semantically valid if predicated, return the min associated alt. // - Else, if a semantically invalid but syntactically valid path exist // or paths exist, return the minimum associated alt. // - Otherwise, return [ATNInvalidAltNumber]. // // In some scenarios, the algorithm described above could predict an // alternative which will result in a [FailedPredicateException] in // the parser. Specifically, this could occur if the only configuration // capable of successfully parsing to the end of the decision rule is // blocked by a semantic predicate. By choosing this alternative within // [AdaptivePredict] instead of panic a [NoViableAltException], the resulting // [FailedPredicateException] in the parser will identify the specific // predicate which is preventing the parser from successfully parsing the // decision rule, which helps developers identify and correct logic errors // in semantic predicates. // // pass in the configs holding ATN configurations which were valid immediately before // the ERROR state was reached, outerContext as the initial parser context from the paper // or the parser stack at the instant before prediction commences. // // Teh func returns the value to return from [AdaptivePredict], or // [ATNInvalidAltNumber] if a suitable alternative was not // identified and [AdaptivePredict] should report an error instead. func (p *ParserATNSimulator) getSynValidOrSemInvalidAltThatFinishedDecisionEntryRule(configs *ATNConfigSet, outerContext ParserRuleContext) int { … } func (p *ParserATNSimulator) GetAltThatFinishedDecisionEntryRule(configs *ATNConfigSet) int { … } type ATNConfigSetPair … func (p *ParserATNSimulator) splitAccordingToSemanticValidity(configs *ATNConfigSet, outerContext ParserRuleContext) []*ATNConfigSet { … } // evalSemanticContext looks through a list of predicate/alt pairs, returning alts for the // pairs that win. A [SemanticContextNone] predicate indicates an alt containing an // un-predicated runtimeConfig which behaves as "always true." If !complete // then we stop at the first predicate that evaluates to true. This // includes pairs with nil predicates. // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) evalSemanticContext(predPredictions []*PredPrediction, outerContext ParserRuleContext, complete bool) *BitSet { … } func (p *ParserATNSimulator) closure(config *ATNConfig, configs *ATNConfigSet, closureBusy *ClosureBusy, collectPredicates, fullCtx, treatEOFAsEpsilon bool) { … } func (p *ParserATNSimulator) closureCheckingStopState(config *ATNConfig, configs *ATNConfigSet, closureBusy *ClosureBusy, collectPredicates, fullCtx bool, depth int, treatEOFAsEpsilon bool) { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) closureCheckingStopStateRecursive(config *ATNConfig, configs *ATNConfigSet, closureBusy *ClosureBusy, collectPredicates, fullCtx bool, depth int, treatEOFAsEpsilon bool) { … } // Do the actual work of walking epsilon edges // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) closureWork(config *ATNConfig, configs *ATNConfigSet, closureBusy *ClosureBusy, collectPredicates, fullCtx bool, depth int, treatEOFAsEpsilon bool) { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) canDropLoopEntryEdgeInLeftRecursiveRule(config *ATNConfig) bool { … } func (p *ParserATNSimulator) getRuleName(index int) string { … } func (p *ParserATNSimulator) getEpsilonTarget(config *ATNConfig, t Transition, collectPredicates, inContext, fullCtx, treatEOFAsEpsilon bool) *ATNConfig { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) actionTransition(config *ATNConfig, t *ActionTransition) *ATNConfig { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) precedenceTransition(config *ATNConfig, pt *PrecedencePredicateTransition, collectPredicates, inContext, fullCtx bool) *ATNConfig { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) predTransition(config *ATNConfig, pt *PredicateTransition, collectPredicates, inContext, fullCtx bool) *ATNConfig { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) ruleTransition(config *ATNConfig, t *RuleTransition) *ATNConfig { … } func (p *ParserATNSimulator) getConflictingAlts(configs *ATNConfigSet) *BitSet { … } // getConflictingAltsOrUniqueAlt Sam pointed out a problem with the previous definition, v3, of // ambiguous states. If we have another state associated with conflicting // alternatives, we should keep going. For example, the following grammar // // 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|[]]. // // The key is that we have a single state that has config's only associated // with a single alternative, 2, and crucially the state transitions // among the configurations are all non-epsilon transitions. That means // we don't consider any conflicts that include alternative 2. So, we // ignore the conflict between alts 1 and 2. We ignore a set of // conflicting alts when there is an intersection with an alternative // associated with a single alt state in the state config-list map. // // It's also the case that we might have two conflicting configurations but // also a 3rd non-conflicting configuration for a different alternative: // // [1|1|[], 1|2|[], 8|3|[]]. // // This can come about from grammar: // // a : A | A | A B // // After Matching input A, we reach the stop state for rule A, state 1. // State 8 is the state right 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, 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, I don't declare the state done. We // ignore a set of conflicting alts when we have an alternative // that we still need to pursue. func (p *ParserATNSimulator) getConflictingAltsOrUniqueAlt(configs *ATNConfigSet) *BitSet { … } func (p *ParserATNSimulator) GetTokenName(t int) string { … } func (p *ParserATNSimulator) getLookaheadName(input TokenStream) string { … } // Used for debugging in [AdaptivePredict] around [execATN], but I cut // it out for clarity now that alg. works well. We can leave this // "dead" code for a bit. func (p *ParserATNSimulator) dumpDeadEndConfigs(_ *NoViableAltException) { … } func (p *ParserATNSimulator) noViableAlt(input TokenStream, outerContext ParserRuleContext, configs *ATNConfigSet, startIndex int) *NoViableAltException { … } func (p *ParserATNSimulator) getUniqueAlt(configs *ATNConfigSet) int { … } // Add an edge to the DFA, if possible. This method calls // {@link //addDFAState} to ensure the {@code to} state is present in the // DFA. If {@code from} is {@code nil}, or if {@code t} is outside the // range of edges that can be represented in the DFA tables, p method // returns without adding the edge to the DFA. // // <p>If {@code to} is {@code nil}, p method returns {@code nil}. // Otherwise, p method returns the {@link DFAState} returned by calling // {@link //addDFAState} for the {@code to} state.</p> // // @param dfa The DFA // @param from The source state for the edge // @param t The input symbol // @param to The target state for the edge // // @return If {@code to} is {@code nil}, p method returns {@code nil} // otherwise p method returns the result of calling {@link //addDFAState} // on {@code to} // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) addDFAEdge(dfa *DFA, from *DFAState, t int, to *DFAState) *DFAState { … } // addDFAState adds state D to the [DFA] if it is not already present, and returns // the actual instance stored in the [DFA]. If a state equivalent to D // is already in the [DFA], the existing state is returned. Otherwise, this // method returns D after adding it to the [DFA]. // // If D is [ATNSimulatorError], this method returns [ATNSimulatorError] and // does not change the DFA. // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) addDFAState(dfa *DFA, d *DFAState) *DFAState { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) ReportAttemptingFullContext(dfa *DFA, conflictingAlts *BitSet, configs *ATNConfigSet, startIndex, stopIndex int) { … } //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) ReportContextSensitivity(dfa *DFA, prediction int, configs *ATNConfigSet, startIndex, stopIndex int) { … } // ReportAmbiguity reports and ambiguity in the parse, which shows that the parser will explore a different route. // // If context-sensitive parsing, we know it's an ambiguity not a conflict or error, but we can report it to the developer // so that they can see that this is happening and can take action if they want to. // //goland:noinspection GoBoolExpressions func (p *ParserATNSimulator) ReportAmbiguity(dfa *DFA, _ *DFAState, startIndex, stopIndex int, exact bool, ambigAlts *BitSet, configs *ATNConfigSet) { … }