Package org.antlr.v4.runtime.dfa

Class DFA

java.lang.Object
org.antlr.v4.runtime.dfa.DFA
public class DFA extends Object

  • Field Details

    • states

      @NotNull public final ConcurrentMap<DFAState,DFAState> states
      A set of all DFA states. Use Map so we can get old state back (Set only allows you to see if it's there).

      Note that this collection of states holds the DFA states for both SLL and LL prediction. Only the start state needs to be differentiated for these cases, which is tracked by the s0 and s0full fields.

    • s0

      @NotNull public final AtomicReference<DFAState> s0
      This is the start state for SLL prediction.

      When isPrecedenceDfa() is true, this state is not used directly. Rather, getPrecedenceStartState(int, boolean) is used to obtain the true SLL start state by traversing an outgoing edge corresponding to the current precedence level in the parser.

    • s0full

      @NotNull public final AtomicReference<DFAState> s0full
      This is the start state for full context prediction.
      See Also:

    • decision

      public final int decision

    • atnStartState

      @NotNull public final ATNState atnStartState
      From which ATN state did we create this DFA?

    • nextStateNumber

      private final AtomicInteger nextStateNumber

    • minDfaEdge

      private final int minDfaEdge
      This is the backing field for getMinDfaEdge().

    • maxDfaEdge

      private final int maxDfaEdge
      This is the backing field for getMaxDfaEdge().

    • EMPTY_PRECEDENCE_EDGES

      @NotNull private static final EmptyEdgeMap<DFAState> EMPTY_PRECEDENCE_EDGES
      This field initializes the outgoing edge map for the special starting DFA state created for precedence DFAs.

      The range of allowed values assigned to this map represent the precedence levels for which an edge will be stored in the DFA. If a precedence level is encountered outside this range, the DFA will not be able to hold an edge pointing to the start state for the decision, so prediction for this precedence level will always result in recomputing the start state. Should this occur, the existing start state can still be located within states so outgoing edges starting from the start state will not be dropped.

    • emptyEdgeMap

      @NotNull private final EmptyEdgeMap<DFAState> emptyEdgeMap
      This is the backing field for getEmptyEdgeMap().

    • emptyContextEdgeMap

      @NotNull private final EmptyEdgeMap<DFAState> emptyContextEdgeMap
      This is the backing field for getEmptyContextEdgeMap().

    • precedenceDfa

      private final boolean precedenceDfa
      true if this DFA is for a precedence decision; otherwise, false. This is the backing field for isPrecedenceDfa().

  • Constructor Details

    • DFA

      public DFA(@NotNull ATNState atnStartState)
      Constructs a DFA instance associated with a lexer mode.

      The start state for a DFA constructed with this method should be a TokensStartState, which is the start state for a lexer mode. The prediction made by this DFA determines the lexer rule which matches the current input.

      Parameters:
      atnStartState - The start state for the mode.

    • DFA

      public DFA(@NotNull ATNState atnStartState, int decision)
      Constructs a DFA instance associated with a decision.
      Parameters:
      atnStartState - The decision associated with this DFA.
      decision - The decision number.

  • Method Details

    • clear

      public final void clear()
      Clears all learned DFA states while reusing this DFA instance.

      Used by ATN.clearDFA() so repeated clear/rebuild cycles (for example cold-path benchmarks or long-running services that flush prediction caches) avoid reallocating one DFA per decision and mode. Precedence DFAs re-seed their synthetic start states; other DFAs reset s0/s0full to null.

    • getMinDfaEdge

      public final int getMinDfaEdge()
      Gets the minimum input symbol value which can be stored in this DFA.
      Returns:
      The minimum input symbol which can be stored in this DFA.
      See Also:

    • getMaxDfaEdge

      public final int getMaxDfaEdge()
      Gets the maximum input symbol value which can be stored in this DFA.
      Returns:
      The maximum input symbol which can be stored in this DFA.
      See Also:

    • getEmptyEdgeMap

      @NotNull public EmptyEdgeMap<DFAState> getEmptyEdgeMap()
      Gets an empty edge map initialized with the minimum and maximum symbol values allowed to be stored in this DFA.

      Setting a range of allowed symbol values for a DFA bounds the memory overhead for storing the map of outgoing edges. The various implementations of EdgeMap use this range to determine the best memory savings will be obtained from sparse storage (e.g. SingletonEdgeMap or SparseEdgeMap) or dense storage (ArrayEdgeMap). Symbols values outside the range are supported during prediction, but since DFA edges are never created for these symbols they will always recompute the target state through a match and closure operation.

      Empty edge maps are immutable objects which track the allowed range of input symbols that can be stored as edges in the DFA. By storing an empty edge map instance in the DFA, new instances of DFAState created for the DFA can be initialized with a non-null outgoing edge map with the proper symbol range without incurring extra allocations.

      Returns:
      The empty edge map used for initializing DFAState instances associated with this DFA.

    • getEmptyContextEdgeMap

      @NotNull public EmptyEdgeMap<DFAState> getEmptyContextEdgeMap()
      Gets an empty edge map initialized with the minimum and maximum context values allowed to be stored in this DFA.

      The value assigned to a context edge within the DFA is an ATN state number, so the range of allowed values for the context edge map is ATNState.INVALID_STATE_NUMBER through the number of states stored in ATN.states for the ATN.

      This empty edge map serves a purpose similar to getEmptyEdgeMap(). It is used for initializing DFAState instances without incurring memory overhead for the (especially) common case where no outgoing context edges are added to the DFA state.

      Returns:
      The empty context edge map used for initializing DFAState instances associated with this DFA.

    • isPrecedenceDfa

      public final boolean isPrecedenceDfa()
      Gets whether this DFA is a precedence DFA. Precedence DFAs use a special start state s0 which is not stored in states. The DFAState.edges array for this start state contains outgoing edges supplying individual start states corresponding to specific precedence values.
      Returns:
      true if this is a precedence DFA; otherwise, false.
      See Also:

    • getPrecedenceStartState

      public final DFAState getPrecedenceStartState(int precedence, boolean fullContext)
      Get the start state for a specific precedence value.
      Parameters:
      precedence - The current precedence.
      Returns:
      The start state corresponding to the specified precedence, or null if no start state exists for the specified precedence.
      Throws:
      IllegalStateException - if this is not a precedence DFA.
      See Also:

    • setPrecedenceStartState

      public final void setPrecedenceStartState(int precedence, boolean fullContext, DFAState startState)
      Set the start state for a specific precedence value.
      Parameters:
      precedence - The current precedence.
      startState - The start state corresponding to the specified precedence.
      Throws:
      IllegalStateException - if this is not a precedence DFA.
      See Also:

    • setPrecedenceDfa

      @Deprecated public final void setPrecedenceDfa(boolean precedenceDfa)
      Deprecated.
      This method no longer performs any action.
      Sets whether this is a precedence DFA.
      Parameters:
      precedenceDfa - true if this is a precedence DFA; otherwise, false
      Throws:
      UnsupportedOperationException - if precedenceDfa does not match the value of isPrecedenceDfa() for the current DFA.

    • isEmpty

      public boolean isEmpty()
      Returns true if this DFA has not yet learned any useful start state information.

      For ordinary (non-precedence) DFAs this is true when both s0 and s0full are still null. For precedence DFAs the synthetic start states always exist, so emptiness is defined by whether those states have any outgoing symbol edges yet.

      PERF: Precedence-DFA emptiness is answered via DFAState.isEdgesEmpty() — never via DFAState.getEdgeMap().isEmpty(), which would allocate a full boxed map on every ParserATNSimulator.adaptivePredict(org.antlr.v4.runtime.TokenStream, int, org.antlr.v4.runtime.ParserRuleContext) call for left-recursive expression decisions (the common case in languages such as Java and Groovy).

    • isContextSensitive

      public boolean isContextSensitive()
      Returns true if this DFA has learned at least one full-context start path.

      PERF: Precedence DFAs use DFAState.isEdgesEmpty() on s0full instead of materializing DFAState.getEdgeMap().

    • addState

      public DFAState addState(DFAState state)

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • toString

      @Deprecated public String toString(@Nullable String[] tokenNames)
      Deprecated.
      Use toString(Vocabulary) instead.

    • toString

      public String toString(@NotNull Vocabulary vocabulary)

    • toString

      @Deprecated public String toString(@Nullable String[] tokenNames, @Nullable String[] ruleNames)
      Deprecated.
      Use toString(Vocabulary, String[]) instead.

    • toString

      public String toString(@NotNull Vocabulary vocabulary, @Nullable String[] ruleNames)

    • toLexerString

      public String toLexerString()