public Class ParserATNSimulator

By default we do full context-sensitive LL(*) parsing not Strong LL(*) parsing. If we fail with Strong LL(*) we try full LL(*). That means we rewind and use context information when closure operations fall off the end of the rule that holds the decision were evaluating.

Annotations

@NotNull

See comment on LexerInterpreter.addDFAState.

Annotations

@NotNull

Annotations

@NotNull

See comment on LexerInterpreter.addDFAState.

Annotations

@NotNull

This method 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. When ATNConfig#isPrecedenceFilterSuppressed is false, 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. This transformation 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 ATNConfig#isPrecedenceFilterSuppressed property marks ATN configurations which do not meet this condition, and therefore are not eligible for elimination during the filtering process.

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';

If 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.

Parameters

configs:ATNConfigSet

The configuration set computed by computeStartState as the start state for the DFA.

Returns:ATNConfigSet

The transformed configuration set representing the start state for a precedence DFA at a particular precedence level (determined by calling Parser#getPrecedence).

Annotations

@NotNull

Annotations

@NotNull

Compute a target state for an edge in the DFA, and attempt to add the computed state and corresponding edge to the DFA.

Parameters

s:DFAState

The current DFA state

t:int

The next input symbol

Returns:Tuple2<DFAState, ParserRuleContext>

The computed target DFA state for the given input symbol t. If t does not lead to a valid DFA state, this method returns ERROR.

Annotations

@NotNull

Annotations

@NotNull

Look through a list of predicate/alt pairs, returning alts for the pairs that win. A null predicate indicates an alt containing an unpredicated config which behaves as "always true."

Evaluate a semantic context within a specific parser context.

This method might not be called for every semantic context evaluated during the prediction process. In particular, we currently do not evaluate the following but it may change in the future:

• Precedence predicates (represented by SemanticContext.PrecedencePredicate) are not currently evaluated through this method.
• Operator predicates (represented by SemanticContext.AND and SemanticContext.OR) are evaluated as a single semantic context, rather than evaluating the operands individually. Implementations which require evaluation results from individual predicates should override this method to explicitly handle evaluation of the operands within operator predicates.

Parameters

pred:SemanticContext

The semantic context to evaluate

parserCallStack:ParserRuleContext

The parser context in which to evaluate the semantic context

alt:int

The alternative which is guarded by pred

Since

4.3

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? if in non-greedy decision is there a config at a rule stop state? We also have some key operations to do: add an edge from previous DFA state to potentially new DFA 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 We should isolate those operations, which are side-effecting, to the main work loop. We can isolate lots of code into other functions, but they should be side effect free. They can return package that indicates whether we should report something, whether we need to add a DFA edge, whether we need to augment accept state with semantic context or rule invocation context. Actually, it seems like we always add predicates if they exist, so that can simply be done in the main loop for any accept state creation or modification request. cover these cases: dead end single alt single alt + preds conflict conflict + preds TODO: greedy + those

Annotations

@Nullable

Get an existing target state for an edge in the DFA. If the target state for the edge has not yet been computed or is otherwise not available, this method returns null.

Parameters

s:DFAState

The current DFA state

t:int

The next input symbol

Returns:DFAState

The existing target DFA state for the given input symbol t, or null if the target state for this edge is not already cached

Annotations

@Nullable

Annotations

@Nullable

This method is used to improve the localization of error messages by choosing an alternative rather than throwing 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 no configuration in configs reached the end of the decision rule, return ATN#INVALID_ALT_NUMBER.
• If all configurations in configs which reached the end of the decision rule predict the same alternative, return that alternative.
• If the configurations in configs which reached the end of the decision rule predict multiple alternatives (call this S), choose an alternative in the following order.
  1. Filter the configurations in configs to only those configurations which remain viable after evaluating semantic predicates. If the set of these filtered configurations which also reached the end of the decision rule is not empty, return the minimum alternative represented in this set.
  2. Otherwise, choose the minimum alternative in S.

In some scenarios, the algorithm described above could predict an alternative which will result in a FailedPredicateException in 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 throwing 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.

Parameters

input:TokenStream

The input TokenStream

startIndex:int

The start index for the current prediction, which is the input index where any semantic context in configs should be evaluated

previous:SimulatorState

The ATN simulation state immediately before the ERROR state was reached

Returns:int

The value to return from adaptivePredict, or ATN#INVALID_ALT_NUMBER if a suitable alternative was not identified and adaptivePredict should report an error instead.

Determines if a particular DFA state should be treated as an accept state for the current prediction mode. In addition to the useContext parameter, the getPredictionMode() method provides the prediction mode controlling the prediction algorithm as a whole.

The default implementation simply returns the value of DFAState#isAcceptState() except for conflict states when useContext is true and getPredictionMode() is PredictionMode#LL_EXACT_AMBIG_DETECTION. In that case, only conflict states where ATNConfigSet#isExactConflict() is true are considered accept states.

Parameters

state:DFAState

The DFA state to check.

useContext:boolean

true if the prediction algorithm is currently considering the full parser context; otherwise, false if the algorithm is currently performing a local context prediction.

Returns:boolean

true if the specified state is an accept state; otherwise, false.

Annotations

@NotNull

Annotations

@Nullable

collect and set D's semantic context

Annotations

@Nullable

Return 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.

Parameters

configs:ATNConfigSet

the configuration set to update

contextCache:PredictionContextCache

the PredictionContext cache

Returns:ATNConfigSet

configs if all configurations in configs are in a rule stop state, otherwise return a new configuration set containing only the configurations from configs which are in a rule stop state

Annotations

@NotNull

If context sensitive parsing, we know it's ambiguity not conflict

Annotations

@NotNull