自制正则表达式引擎

RegexExp regexExp=RegexParser.parse("(a|b)*abb");
log.info(RegexExpTreeFormatter.format(regexExp));

[Concat]
├──[Repeat:*]
│  └──[Or]
│     ├──[Char:a]
│     └──[Char:b]
└──[Concat]
   ├──[Char:a]
   └──[Concat]
      ├──[Char:b]
      └──[Char:b]

public abstract class RegexExp
{

    /**
     * 访问者模式, 子类实现具体的 accept 方法
     *
     * @param visitor 访问者
     * @return 返回 T
     */
    public abstract <T, C> T accept(RegexExpVisitor<T, C> visitor, C context);
}

public interface RegexExpVisitor<T, C>
{
    // --------------- 基于 RegexNode 具体类型分发 ------------------------

    // 单个字符
    T visitChar(CharExp node, C context);
    T visitCharRange(CharRangeExp node, C context);
    T visitCharClass(CharClassExp node, C context);
    T visitConcat(ConcatExp node, C context);
    T visitOr(OrExp node, C context);
    T visitRepeat(RepeatExp node, C context);
    T visitMetaChar(MetaCharExp node, C context);

    // 泛型入口
    default T process(RegexExp node, C context)
    {
        return node.accept(this, context);
    }
}

public interface Graph
{
    State getStart();
}

public class Transition
{
    private Transition(Edge edge, State state)
    {
        this.edge = edge;
        this.state = state;
    }

    private final Edge edge;
    private final State state;
}

public class SubGraph
{
    private Edge inEdge;
    private State start;
    private State end;
}

NFAGraph nfaGraph=NFAGraph.build(regexExp);
log.info(nfaGraph.toMermaidJsChart());

    /**
     * 子集构造法从NFA生成DFA.
     *
     * @return DFAGraph
     */
    public DFAGraph toDFA()
    {
        // 计算 ϵ−closure(0)
        Set<Integer> startSet = computeEpsilonClosure(this.start.getStateId());
        // 子集构造法
        State state = createDFAState(startSet);
        // 构建DFA Graph, stateManager是状态管理器
        return DFAGraph.of(state, stateManager, false);
    }

DFAGraph dfa=nfa.toDFA();
log.info(dfa.toMermaidJsChart());

log.info(dfa.printStateMapping());
/**
<<<<<<<<<<<< NFA -> DFA >>>>>>>>>>>>>
s_0<==>(s_7,s_8,s_0,s_1,s_2,s_4)
s_4<==>(s_5,s_6,s_7,s_8,s_1,s_2,s_4)
s_1<==>(s_6,s_7,s_8,s_9,s_10,s_1,s_2,s_3,s_4)
s_2<==>(s_5,s_6,s_7,s_8,s_11,s_12,s_1,s_2,s_4)
s_3<==>(s_5,s_6,s_7,s_8,s_13,s_1,s_2,s_4)
*/

    /**
     * DFA 化简 (Hopcroft)算法
     *
     * @return
     */
    public DFAGraph simplify()
    {
        // DFA 状态和DFA状态所在集合
        Map<Integer, Set<Integer>> dfaStateSetIndexMap = new HashMap<>();
        // 将所有DFA 状态分为 终结状态集合和非终结状态集合
        Set<Set<Integer>> sets = initSplitedSet(start.getStateId(), dfaStateSetIndexMap);
        // 分割DFA状态集进行化简
        trySplitSet(sets, dfaStateSetIndexMap);
        Set<Integer> stateSet = searchDFAIndexMap(this.start.getStateId(), dfaStateSetIndexMap);
        State start = createMinimizationDFAState(stateSet, dfaStateSetIndexMap);
        return new DFAGraph(start, stateManager, true);
    }

DFAGraph minDfa=dfa.simplify();
log.info(minDfa.toMermaidJsChart());

log.info(minDfa.printStateMapping());
/**
<<<<<<<<<<<< mini DFA -> DFA >>>>>>>>>>>>>
s_0<==>(s_0,s_4)
s_1<==>(s_1)
s_2<==>(s_2)
s_3<==>(s_3)
*/

    public boolean matches(String str)
    {
        State state = dfaGraph.getStart();
        for (int i = 0, length = str.length(); i < length; i++) {
            char ch = str.charAt(i);
            Optional<State> to = state.getTransitionsOfInputEdge(Edge.character(ch)).stream().findFirst().map(Transition::getState);
            if (!to.isPresent()) {
                return false;
            }
            state = to.get();
        }
        return state.isAccept();
    }

    public boolean matches(String str)
    {
      Set<Integer> set= nfaGraph.computeEpsilonClosure(nfaGraph.getStart().getStateId());
      for (int i = 0, length = str.length(); i < length; i++) {
          char ch = str.charAt(i);
          set = nfaGraph.findDFAMoveSet(set,Edge.character(ch));
      }
        return nfaGraph.isNFASetAccept(set);
    }