Lucene introduces NFA

org.apache.lucene.util.automaton.MinimizationOperations#minimize

Determinate and minimize ：

  /**
   * Minimizes (and determinizes if not already deterministic) the given
   * automaton using Hopcroft's algorighm.
   * @param maxDeterminizedStates maximum number of states determinizing the
   *  automaton can result in.  Set higher to allow more complex queries and
   *  lower to prevent memory exhaustion.
   */
  public static Automaton minimize(Automaton a, int maxDeterminizedStates) {

  }

org.apache.lucene.search.AutomatonQuery#getTermsEnum

take label by c At the end of state In a Dstate in

    private int nextState(int charClass) {
      initTransitions();
      assert charClass < transitions.length;
      if (transitions[charClass] == NOT_COMPUTED) {
        assignTransition(charClass, findDState(step(points[charClass])));
        // we could potentially update more than one char classes
        if (minimalTransition != null) {
          // to the left
          int cls = charClass;
          while (cls > 0 && points[--cls] >= minimalTransition.min) {
            assert transitions[cls] == NOT_COMPUTED || transitions[cls] == transitions[charClass];
            assignTransition(cls, transitions[charClass]);
          }
          // to the right
          cls = charClass;
          while (cls < points.length - 1 && points[++cls] <= minimalTransition.max) {
            assert transitions[cls] == NOT_COMPUTED || transitions[cls] == transitions[charClass];
            assignTransition(cls, transitions[charClass]);
          }
          minimalTransition = null;
        }
      }
      return transitions[charClass];
    }

among  

assignTransition(charClass, findDState(step(points[charClass])));

findDState Back to DFA Status number in

 

org.apache.lucene.util.automaton.NFARunAutomaton.DState#step

    /**
     * given a list of NFA states and a character c, compute the output list of NFA state which is
     * wrapped as a DFA state
     */
    private DState step(int c) {
      statesSet.reset(); // TODO: fork IntHashSet from hppc instead?
      int numTransitions;
      int left = -1, right = alphabetSize;
      for (int nfaState : nfaStates) {
        numTransitions = automaton.initTransition(nfaState, stepTransition);
        // TODO: binary search should be faster, since transitions are sorted
        for (int i = 0; i < numTransitions; i++) {
          automaton.getNextTransition(stepTransition);
          if (stepTransition.min <= c && stepTransition.max >= c) {
            statesSet.incr(stepTransition.dest);
            left = Math.max(stepTransition.min, left);
            right = Math.min(stepTransition.max, right);
          }
          if (stepTransition.max < c) {
            left = Math.max(stepTransition.max + 1, left);
          }
          if (stepTransition.min > c) {
            right = Math.min(stepTransition.min - 1, right);
            // transitions in automaton are sorted
            break;
          }
        }
      }
      if (statesSet.size() == 0) {
        return null;
      }
      minimalTransition = new Transition();
      minimalTransition.min = left;
      minimalTransition.max = right;
      return new DState(statesSet.getArray());
    }

  /**
   * return the ordinal of given DFA state, generate a new ordinal if the given DFA state is a new
   * one
   */
  private int findDState(DState dState) {
    if (dState == null) {
      return MISSING;
    }
    int ord = dStateToOrd.getOrDefault(dState, -1);
    if (ord >= 0) {
      return ord;
    }
    ord = dStateToOrd.size();
    dStateToOrd.put(dState, ord);
    assert ord >= dStates.length || dStates[ord] == null;
    if (ord >= dStates.length) {
      dStates = ArrayUtil.grow(dStates, ord + 1);
    }
    dStates[ord] = dState;
    return ord;
  }

Reference documents ：

[LUCENE-10010] Should we have a NFA Query? - ASF JIRAhttps://issues.apache.org/jira/browse/LUCENE-10010

What is? NFA( Uncertain finite automata ) and DFA( Definite finite automata ) - Bubgit - Blog Garden The knowledge points in this section are 《 Compiler principle 》 The third chapter - Lexical analysis , The learning reference textbook is Tsinghua University Press 《 Compiler principle 》 The third edition ： Antecedents feed ： alphabet ∑1 and ∑2 The product of the ( product)： ∑1∑2 ={ab|a ∈∑1, b ∈ ∑2}https://www.cnblogs.com/Bubgit/p/10240790.html

Regular Expression Matching Can Be Simple And Fasthttps://swtch.com/~rsc/regexp/regexp1.html

The compilation principle constructs the normal formula from the normal grammar （ Regular expressions ） – OmegaXYZhttps://www.omegaxyz.com/2019/01/25/rg2re/

Compiler principle （4）： Grammatical analysis —— Top down analysis _ Fengqing's blog -CSDN Blog _ Compilation principle top-down parsing method Statement ： This series of articles , According to Chinese universities MOOC network The compilation principle of Harbin Institute of Technology Learning notes from this course . One 、 Top down analysis outlines the leftmost derivation (Left-most Derivation) Rightmost derivation (Right-most Derivation) Top down analysis (Top-Down Parsing) From the top of the analysis tree （ The root node ） To the bottom （ Leaf nodes ） The direction construction analysis tree can be regarded as a symbol starting from grammar S Deduce the word string w Every step of the process of derivation , Need to be ...https://blog.csdn.net/weixin_44226857/article/details/104240028

Compiler principle （ Harbin Institute of technology ）_ Bili, Bili _bilibilihttps://www.icourse163.org/learn/HIT-1002123007 Compilation principles of Harbin Institute of technology compilation principles video of Harbin Institute of Technology , From Chinese universities mooc network , If infringement, please contact me to delete .https://www.bilibili.com/video/BV1zW411t7YE?from=search&seid=11305774085050474112&spm_id_from=333.337.0.0