gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/dfa/DFAState.h

   1 /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
   2  * Use of this file is governed by the BSD 3-clause license that
   3  * can be found in the LICENSE.txt file in the project root.
   4  */
   5
   6 #pragma once
   7
   8 #include "antlr4-common.h"
   9
  10 namespace antlr4 {
  11 namespace dfa {
  12
  13   /// <summary>
  14   /// A DFA state represents a set of possible ATN configurations.
  15   ///  As Aho, Sethi, Ullman p. 117 says "The DFA uses its state
  16   ///  to keep track of all possible states the ATN can be in after
  17   ///  reading each input symbol.  That is to say, after reading
  18   ///  input a1a2..an, the DFA is in a state that represents the
  19   ///  subset T of the states of the ATN that are reachable from the
  20   ///  ATN's start state along some path labeled a1a2..an."
  21   ///  In conventional NFA->DFA conversion, therefore, the subset T
  22   ///  would be a bitset representing the set of states the
  23   ///  ATN could be in.  We need to track the alt predicted by each
  24   ///  state as well, however.  More importantly, we need to maintain
  25   ///  a stack of states, tracking the closure operations as they
  26   ///  jump from rule to rule, emulating rule invocations (method calls).
  27   ///  I have to add a stack to simulate the proper lookahead sequences for
  28   ///  the underlying LL grammar from which the ATN was derived.
  29   /// <p/>
  30   ///  I use a set of ATNConfig objects not simple states.  An ATNConfig
  31   ///  is both a state (ala normal conversion) and a RuleContext describing
  32   ///  the chain of rules (if any) followed to arrive at that state.
  33   /// <p/>
  34   ///  A DFA state may have multiple references to a particular state,
  35   ///  but with different ATN contexts (with same or different alts)
  36   ///  meaning that state was reached via a different set of rule invocations.
  37   /// </summary>
  38   class ANTLR4CPP_PUBLIC DFAState {
  39   public:
  40     class PredPrediction {
  41     public:
  42       Ref<atn::SemanticContext> pred; // never null; at least SemanticContext.NONE
  43       int alt;
  44
  45       PredPrediction(const Ref<atn::SemanticContext> &pred, int alt);
  46       virtual ~PredPrediction();
  47
  48       virtual std::string toString();
  49
  50     private:
  51       void InitializeInstanceFields();
  52     };
  53
  54     int stateNumber;
  55
  56     std::unique_ptr<atn::ATNConfigSet> configs;
  57
  58     /// {@code edges[symbol]} points to target of symbol. Shift up by 1 so (-1)
  59     ///  <seealso cref="Token#EOF"/> maps to {@code edges[0]}.
  60     // ml: this is a sparse list, so we use a map instead of a vector.
  61     //     Watch out: we no longer have the -1 offset, as it isn't needed anymore.
  62     std::unordered_map<size_t, DFAState *> edges;
  63
  64     bool isAcceptState;
  65
  66     /// if accept state, what ttype do we match or alt do we predict?
  67     /// This is set to <seealso cref="ATN#INVALID_ALT_NUMBER"/> when <seealso cref="#predicates"/>{@code !=null} or
  68     /// <seealso cref="#requiresFullContext"/>.
  69     size_t prediction;
  70
  71     Ref<atn::LexerActionExecutor> lexerActionExecutor;
  72
  73     /// <summary>
  74     /// Indicates that this state was created during SLL prediction that
  75     /// discovered a conflict between the configurations in the state. Future
  76     /// <seealso cref="ParserATNSimulator#execATN"/> invocations immediately jumped doing
  77     /// full context prediction if this field is true.
  78     /// </summary>
  79     bool requiresFullContext;
  80
  81     /// <summary>
  82     /// During SLL parsing, this is a list of predicates associated with the
  83     ///  ATN configurations of the DFA state. When we have predicates,
  84     ///  <seealso cref="#requiresFullContext"/> is {@code false} since full context prediction evaluates predicates
  85     ///  on-the-fly. If this is not null, then <seealso cref="#prediction"/> is
  86     ///  <seealso cref="ATN#INVALID_ALT_NUMBER"/>.
  87     /// <p/>
  88     ///  We only use these for non-<seealso cref="#requiresFullContext"/> but conflicting states. That
  89     ///  means we know from the context (it's $ or we don't dip into outer
  90     ///  context) that it's an ambiguity not a conflict.
  91     /// <p/>
  92     ///  This list is computed by <seealso cref="ParserATNSimulator#predicateDFAState"/>.
  93     /// </summary>
  94     std::vector<PredPrediction *> predicates;
  95
  96     /// Map a predicate to a predicted alternative.
  97     DFAState();
  98     DFAState(int state);
  99     DFAState(std::unique_ptr<atn::ATNConfigSet> configs);
 100     virtual ~DFAState();
 101
 102     /// <summary>
 103     /// Get the set of all alts mentioned by all ATN configurations in this
 104     ///  DFA state.
 105     /// </summary>
 106     virtual std::set<size_t> getAltSet();
 107
 108     virtual size_t hashCode() const;
 109
 110     /// Two DFAState instances are equal if their ATN configuration sets
 111     /// are the same. This method is used to see if a state already exists.
 112     ///
 113     /// Because the number of alternatives and number of ATN configurations are
 114     /// finite, there is a finite number of DFA states that can be processed.
 115     /// This is necessary to show that the algorithm terminates.
 116     ///
 117     /// Cannot test the DFA state numbers here because in
 118     /// ParserATNSimulator#addDFAState we need to know if any other state
 119     /// exists that has this exact set of ATN configurations. The
 120     /// stateNumber is irrelevant.
 121     bool operator == (const DFAState &o) const;
 122
 123     virtual std::string toString();
 124
 125     struct Hasher
 126     {
 127       size_t operator()(DFAState *k) const {
 128         return k->hashCode();
 129       }
 130     };
 131
 132     struct Comparer {
 133       bool operator()(DFAState *lhs, DFAState *rhs) const
 134       {
 135         return *lhs == *rhs;
 136       }
 137     };
 138
 139   private:
 140     void InitializeInstanceFields();
 141   };
 142
 143 } // namespace atn
 144 } // namespace antlr4