Lines Matching full:we
44 * We begin with ATN simulation to build paths in a DFA. Subsequent prediction
50 * All of that is done without using the outer context because we want to create
51 * a DFA that is not dependent upon the rule invocation stack when we do a
52 * prediction. One DFA works in all contexts. We avoid using context not
57 * stacks in the configurations. When lack of context leads to a conflict, we
61 * When SLL yields a configuration set with conflict, we rewind the input and
64 * from the start rule. If we get a conflict using full context, then we can
65 * definitively say we have a true ambiguity for that input sequence. If we
70 * The next time we reach this DFA state with an SLL conflict, through DFA
71 * simulation, we will again retry the ATN simulation using full context mode.
72 * This is slow because we can't save the results and have to "interpret" the
73 * ATN each time we get that input.
77 * We could cache results from full context to predicted alternative easily and
84 * to keep this algorithm simple. By launching multiple threads, we can improve
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
95 * original A B C. To make a prediction cache work, we have to track the exact
105 * We avoid doing full context retry when the outer context is empty, we did not
107 * or when we force SLL mode.
138 * ATN simulation whereas, if we had evaluated predicates on-the-fly during
139 * closure, the DFA state configuration sets would be different and we couldn't
142 * When building a DFA accept state during ATN simulation, we evaluate any
144 * more than 1 alternative, we report an ambiguity. If there are 0 alternatives,
145 * we throw an exception. Alternatives without predicates act like they have
150 * When we start in the DFA and reach an accept state that's predicated, we test
152 * alternatives are viable, we throw an exception.
175 * decision when looking up a DFA state to see if it already exists. We must
182 * safe as long as we can guarantee that all threads referencing
196 * point in doing full LL, which is slower. We only have to try LL if we get a
204 * If it does not get a syntax error, then we're done. If it does get a syntax
205 * error, we need to retry with the combined SLL/LL strategy.
222 * Let's say we have a set of SLL conflicting alternatives `{1, 2, 3}` and
229 * Of course, if the input is invalid, then we will get an error for sure in
268 * isn't synchronized but we're ok since two threads shouldn't reuse same
270 * This maps graphs a and b to merged result c. (a,b)→c. We can avoid
271 * the merge if we ever see a and b again. Note that (b,a)→c should
348 … // Now we are certain to have a specific decision's DFA, but do we still need an initial state?
384 * If this is a precedence DFA, we use applyPrecedenceFilter
386 * state. We then use DFA.setPrecedenceStartState to set the
428 * There are some key conditions we're looking for after computing a new
435 * We also have some key operations to do:
497 * We will get an error no matter what so delay until after
500 * If conflict in states that dip out, choose min since we
659 // Create new target state; we'll add to DFA after it's complete
690 // in SLL-only mode, we will stop at this state and return the minimum alt
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.
735 $dfaState->prediction = ATN::INVALID_ALT_NUMBER; // make sure we use preds
754 DFAState $D, // how far we got before failing over
780 * We will get an error no matter what so delay until after
783 * If conflict in states that dip out, choose min since we
827 // In exact ambiguity mode, we never try to terminate early.
828 // Just keeps scarfing until we know what the conflict is
837 // we're not sure what the ambiguity is yet.
850 // without conflict, then we know that it's a full LL decision not SLL.
857 /* We do not check predicates here because we have checked them on-the-fly
860 * In non-exact ambiguity detection mode, we might actually be able to
862 * needed to check. We only emit ambiguity warnings in exact ambiguity
865 * For example, we might know that we have conflicting configurations.
879 * next sequence, however, is associated with a conflict. We stop
881 * the fact that we should predict alternative 1. We just can't say for
915 // First figure out where we can reach on input t
995 /* After consuming EOF no additional input is possible, so we are
1018 * configurations reached the end of the start rule, in which case we
1114 * predicates evaluated when we reach conflict state (or unique prediction).
1115 * As we cannot evaluate these predicates out of context, the resulting
1126 * We convert that to the following:
1135 * both predicates by falling off the edge of e. This is because we have
1138 * it back to the enter or exit decision. In this case, we know that we
1139 * cannot evaluate those predicates because we have fallen off the edge
1143 * Because we have special information, that these are precedence predicates,
1144 * we can resolve them without failing over to full LL despite their context
1145 * sensitive nature. We make an assumption that prec[-1] <= prec[0], meaning
1151 * further up the stack. But, we know that all of those prec are lower or
1152 * the same value and so we can decide to enter the loop instead of matching
1153 * it later. That means we can strip out the other configuration for the exit branch.
1155 * So imagine we have (14,1,$,{2>=prec}?) and then
1157 * collapse these two configurations. We know that if {2>=prec}? is true
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
1174 * 1+2+3 at the first +, we see prediction filtering.
1188 * We noticed a problem where a recursive call resets precedence to 0.
1522 * then we stop at the first predicate that evaluates to true. This
1584 * TODO: If we are doing predicates, there is no point in pursuing
1585 * closure operations if we reach a DFA state that uniquely predicts
1586 * alternative. We will not be caching that DFA state and it is a
1587 * waste to pursue the closure. Might have to advance when we do
1633 … // We hit rule end. If we have context info, use it run thru all possible stack tops in ctx
1644 // we have no context info, just chase follow links (if greedy)
1671 // While we have context to pop back from, we may have
1673 // Make sure we track that we are now out of context.
1698 // Else if we have no context info, just chase follow links (if greedy)
1747 // We can't get here if incoming config was rule stop and we had context
1748 // track how far we dip into outer context. Might
1749 // come in handy and we avoid evaluating context dependent
1768 // TODO: can remove? only care when we add to set per middle of this method
1783 … // latch when newDepth goes negative - once we step out of the entry context we can't return
1811 * (traversing only epsilon edges, so we're still in closure, in
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
1819 * To verify we are in the right situation we must first check
1821 * Then we check that each stack top of context is a return state
1836 * a. empty (we'd fall out of expr to do a global FOLLOW which could
1842 * Do we need to evaluate predicates ever in closure for this case?
1852 * StarLoopEntryState. We do not have to evaluate predicates
1853 * therefore if we are in the generated StarLoopEntryState of a LR
1860 * How do we know this always gives same prediction answer?
1867 * we choose the more efficient path, which is to take the bypass
1881 * How do we know this optimization doesn't mess up precedence in
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
1900 * global FOLLOW so we can't perform optimization
1901 * Are we the special loop entry/exit state? or SLL wildcard
1962 // which points to p but we don't need to check that
2091 /* In full context mode, we can evaluate predicates on-the-fly
2151 // In full context mode, we can evaluate predicates on-the-fly
2220 ambiguous states. If we have another state associated with conflicting
2221 alternatives, we should keep going. For example, the following grammar
2227 12|1|[] and 12|2|[] conflict, but we cannot stop processing this node
2229 The key is that we have a single state that has config's only associated
2232 we don't consider any conflicts that include alternative 2. So, we
2233 ignore the conflict between alts 1 and 2. We ignore a set of
2237 It's also the case that we might have two conflicting configurations but
2243 After matching input A, we reach the stop state for rule A, state 1.
2246 However, alternative 3 will be able to continue and so we do not
2247 stop working on this state. In the previous example, we're concerned
2249 3 is not associated with the conflicting configs, but since we can continue
2250 looking for input reasonably, I don't declare the state done. We
2251 ignore a set of conflicting alts when we have an alternative
2252 that we still need to pursue.
2477 * If context sensitive parsing, we know it's ambiguity not conflict.