Lines Matching defs:to
43 * The basic complexity of the adaptive strategy makes it harder to understand.
44 * We begin with ATN simulation to build paths in a DFA. Subsequent prediction
46 * the current symbol, the algorithm fails over to the ATN simulation to
50 * All of that is done without using the outer context because we want to create
57 * stacks in the configurations. When lack of context leads to a conflict, we
63 * to the DFA. Configuration context stacks will be the full invocation stacks
66 * don't get a conflict, it implies that the decision is sensitive to the outer
72 * This is slow because we can't save the results and have to "interpret" the
77 * We could cache results from full context to predicted alternative easily and
80 * context, because closure can fall off the end of a rule. I tried to cache
83 * memory. The goal is not to create the world's fastest parser anyway. I'd like
84 * to keep this algorithm simple. By launching multiple threads, we can improve
88 * which makes it really hard to build a cache for full context. Let's say that
89 * we have input A B C that leads to an SLL conflict with full context X. That
90 * implies that using X we might only use A B but we could also use A B C D to
94 * full context prediction, which would lead us to requiring more input than the
95 * original A B C. To make a prediction cache work, we have to track the exact
96 * input used during the previous prediction. That amounts to a cache that maps
97 * X to a specific DFA for that context.
100 * likely LL(1) + pred eval. Easier to do the whole SLL unless error and retry
137 * evaluation until it reaches and accept state. This allows us to cache the SLL
146 * true predicates. The simple way to think about it is to strip away all
155 * on-the-fly. This is crucial to reducing the configuration set size during
171 * field when it adds a new DFA object to that array.
175 * decision when looking up a DFA state to see if it already exists. We must
176 * make sure that all requests to add DFA states that are equivalent result in
178 * to update the DFA at once. {@see ParserATNSimulator::addDFAState()} also
185 * It follows the {@see DFAState::$edges} field to new targets. The DFA simulator
186 * will either find {@see DFAState::$edges} to be `null`, to be non-`null` and
187 * `dfa.edges[t]` null, or `dfa.edges[t]` to be non-null. The
188 * {@see ParserATNSimulator::addDFAEdge()} method could be racing to set the field
190 * simulation. It could also race trying to get `dfa.edges[t]`, but either
193 * tarting with SLL then failing to combined SLL/LL (Two-Stage Parsing)
196 * point in doing full LL, which is slower. We only have to try LL if we get a
197 * syntax error. For maximum speed, Sam starts the parser set to pure SLL
205 * error, we need to retry with the combined SLL/LL strategy.
270 * This maps graphs a and b to merged result c. (a,b)→c. We can avoid
279 * LAME globals to avoid parameters!!!!! I need these down deep in predTransition.
348 // Now we are certain to have a specific decision's DFA, but do we still need an initial state?
385 * to convert the computed start state to a precedence start
386 * state. We then use DFA.setPrecedenceStartState to set the
395 $dfa->s0->configs = $s0_closure; // not used for prediction but useful to know start configs anyway
424 * Performs ATN simulation to compute a predicted alternative based
425 * upon the remaining input, but also updates the DFA cache to avoid
426 * having to traverse the ATN again for the same input sequence.
435 * We also have some key operations to do:
436 * - add an edge from previous DFA state to potentially new DFA state, D,
437 * upon current symbol but only if adding to work list, which means in all
439 * - collecting predicates and adding semantic context to DFA accept states
440 * - adding rule context to context-sensitive DFA accept states
494 * means that input up to t actually finished entry rule
547 // Restore the index so reporting the fallback to full
596 // Report ambiguity after predicate evaluation to make sure
637 * Compute a target state for an edge in the DFA, and attempt to add
638 * the computed state and corresponding edge to the DFA.
645 * symbol `t`. If `t` does not lead to a valid DFA
659 // Create new target state; we'll add to DFA after it's complete
714 // All adds to dfa are done after we've created full D state
722 // We need to test all predicates, even in DFA states that uniquely predict alternative.
739 // resolve to min alt.
742 throw new \RuntimeException('Unexpected null alternatives to collect predicates');
750 * Comes back with reach.uniqueAlt set to a valid alt.
777 * means that input up to t actually finished entry rule
827 // In exact ambiguity mode, we never try to terminate early.
860 * In non-exact ambiguity detection mode, we might actually be able to
861 * detect an exact ambiguity, but I'm not going to spend the cycles
862 * needed to check. We only emit ambiguity warnings in exact ambiguity
867 * conflict. It's possible to have nonconflicting alt subsets as in:
878 * would resolve this without conflict to alternative 1. Any other viable
909 * For full-context reach operations, separate handling is required to
934 $this->log[] = \sprintf('Added %s to skippedStopStates', (string) $c);
949 $this->log[] = \sprintf('Added %s to intermediate', (string) $cfg);
964 * relevant to the reach set, but this condition is not true when one
971 // It can only have one alternative; just add to result
983 // operation on the intermediate set to compute its initial value.
998 * context). Update reach to contain only these configurations. This
1003 * this case, removeAllConfigsNotInRuleStopState needs to check for
1009 * already guaranteed to meet this condition whether or not it's
1019 * only add them back to reach if no configuration during the current
1049 * state to see if a rule stop state is reachable from the configuration via
1052 * @param ATNConfigSet $configs The configuration set to update
1095 // Always at least the implicit call to start rule
1116 * conflict leads to full LL evaluation and nonlinear prediction which
1126 * We convert that to the following:
1138 * it back to the enter or exit decision. In this case, we know that we
1141 * the right one to use in the predicate.
1144 * we can resolve them without failing over to full LL despite their context
1146 * that the current precedence level is greater than or equal to the precedence
1148 * predicate {3>=prec}? is true of the current prec, then one option is to
1149 * enter the loop to match it now. The other option is to exit the loop and
1150 * the left recursive rule to match the current operator in rule invocation
1152 * the same value and so we can decide to enter the loop instead of matching
1156 * (14,2,$-dipsIntoOuterContext,{2>=prec}?). The optimization allows us to
1160 * are both true, we have the option to evaluate them early in the decision
1161 * start state. We do this by stripping both predicates and choosing to
1167 * The basic filter mechanism is to remove configurations of the form (p, 2, pi)
1173 * resolves conflicts according to precedence levels. For example, for input
1179 * to
1183 * This filters because {3>=prec}? evals to true and collapses
1188 * We noticed a problem where a recursive call resets precedence to 0.
1191 * flag is carried along in closure(). so to avoid adding field, set bit
1195 * to a rule invocation with precedence level 0".
1200 * {@see ParserATNSimulator::computeStartState()} to the special start state
1202 * process applies the following changes to the start state's configuration
1218 * to the left-recursive rule, with the outer calls not being at the
1221 * The prediction context must be considered by this filter to address
1234 * which stepped out to `prog` (and then back in to `statement` from being
1284 /* In the future, this elimination step could be updated to also
1314 * corresponds to alternative i. altToPred[i] may have one of three values:
1394 * This method is used to improve the localization of error messages by
1400 * algorithm to identify an ATN configuration which successfully parsed the
1415 * capable of successfully parsing to the end of the decision rule is
1431 * @return int The value to return from {@see ParserATNSimulator::adaptivePredict()},
1483 * Walk the list of configurations and split them according to
1484 * those that have preds evaluating to true/false. If no pred, assume
1487 * Create a new set so as not to alter the incoming parameter.
1489 * Assumption: the input stream has been restored to the starting point
1490 * prediction, which is where predicates need to evaluate.
1522 * then we stop at the first predicate that evaluates to true. This
1587 * waste to pursue the closure. Might have to advance when we do
1671 // While we have context to pop back from, we may have
1676 // isPrecedenceFilterSuppressed() value to the new
1724 // make sure to not return here, because EOF transitions can act as
1768 // TODO: can remove? only care when we add to set per middle of this method
1808 * The optimization is to avoid adding the loop entry config when
1809 * the exit path can only lead back to the same
1814 * We need to detect any state that can reach loop entry on
1815 * epsilon w/o exiting rule. We don't have to look at FOLLOW
1816 * links, just ensure that all stack tops for config refer to key
1832 * config to the current config set for edge[0], the loop entry branch.
1836 * a. empty (we'd fall out of expr to do a global FOLLOW which could
1837 * even be to some weird spot in expr) or,
1842 * Do we need to evaluate predicates ever in closure for this case?
1851 * token as there are no epsilon-paths that lead to
1852 * StarLoopEntryState. We do not have to evaluate predicates
1863 * upon remaining input +b (in, say, a+b). Either paths lead to
1864 * valid parses. Closure can lead to consuming + immediately or by
1865 * falling out of this call to expr back into expr and loop back
1866 * again to StarLoopEntryState to match +b. In this special case,
1867 * we choose the more efficient path, which is to take the bypass
1871 * one path over the other. Both paths lead to consuming the same
1875 * closure had chosen to enter the choice block immediately.
1879 * always copies the same alt to any derived configs.
1884 * Looking through expr from left edge of stat only has to confirm
1888 * parsing rule expr that we must use the precedence to get the
1897 /* First check to see if we are in StarLoopEntryState generated during
1915 // Require all return states to return back to the same rule that p is in.
1940 // Verify that the top of each stack context leads to loop entry/exit
1961 // of (...)* internal block; the block end points to loop back
1962 // which points to p but we don't need to check that
2093 * the config sets. It also obviates the need to test predicates
2153 // the config sets. It also obviates the need to test predicates
2204 * @param ATNConfigSet $configs The {@see ATNConfigSet} to analyze.
2228 because alternative to has another way to continue, via [6|2|[]].
2246 However, alternative 3 will be able to continue and so we do not
2252 that we still need to pursue.
2320 * Add an edge to the DFA, if possible. This method calls
2321 * {@see ParserATNSimulator::addDFAState()} to ensure the `to` state is
2324 * returns without adding the edge to the DFA.
2326 * If `to` is `null`, this method returns `null`. Otherwise, this method
2328 * {@see ParserATNSimulator::addDFAState()} for the `to` state.
2333 * @param DFAState|null $to The target state for the edge
2335 * @return DFAState If `to` is `null` this method returns `null`,
2337 * {@see ParserATNSimulator::addDFAState()} on `to`.
2339 protected function addDFAEdge(DFA $dfa, ?DFAState $from, int $t, ?DFAState $to) : ?DFAState
2342 $this->log[] = \sprintf('EDGE %s -> %s upon %s', (string) $from, (string) $to, $this->getTokenName($t));
2345 if ($to === null) {
2349 $to = $this->addDFAState($dfa, $to);// used existing if possible not incoming
2352 return $to;
2359 $from->edges[$t + 1] = $to;
2365 return $to;
2369 * Add state `D` to the DFA if it is not already present, and return
2370 * the actual instance stored in the DFA. If a state equivalent to `D`
2372 * method returns `D` after adding it to the DFA.
2378 * @param DFAState $D The DFA state to add