applyPrecedenceFilter method

ATNConfigSet applyPrecedenceFilter(ATNConfigSet configs)

This method transforms the start state computed by {@link #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 {@link SemanticContext#evalPrecedence}.
2. When {@link 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 {@link 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 {@code '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.

@param configs The configuration set computed by {@link #computeStartState} as the start state for the DFA. @return The transformed configuration set representing the start state for a precedence DFA at a particular precedence level (determined by calling {@link Parser#getPrecedence}).

Implementation

ATNConfigSet applyPrecedenceFilter(ATNConfigSet configs) {
  final statesFromAlt1 = <int, PredictionContext>{};
  final configSet = ATNConfigSet(configs.fullCtx);
  for (var config in configs) {
    // handle alt 1 first
    if (config.alt != 1) {
      continue;
    }

    final updatedContext = config.semanticContext.evalPrecedence(
      parser,
      _outerContext,
    );
    if (updatedContext == null) {
      // the configuration was eliminated
      continue;
    }
    assert(config.context != null);
    final configContext = config.context!;

    statesFromAlt1[config.state.stateNumber] = configContext;
    if (updatedContext != config.semanticContext) {
      configSet.add(
          ATNConfig.dup(config, semanticContext: updatedContext), mergeCache);
    } else {
      configSet.add(config, mergeCache);
    }
  }

  for (var config in configs) {
    if (config.alt == 1) {
      // already handled
      continue;
    }

    if (!config.isPrecedenceFilterSuppressed()) {
      /* In the future, this elimination step could be updated to also
				 * filter the prediction context for alternatives predicting alt>1
				 * (basically a graph subtraction algorithm).
				 */
      assert(config.context != null);
      final configContext = config.context!;
      final context = statesFromAlt1[config.state.stateNumber];
      if (context != null && context == configContext) {
        // eliminated
        continue;
      }
    }

    configSet.add(config, mergeCache);
  }

  return configSet;
}