正则表达式引擎详解

正则表达式引擎详解

承接上文

上篇文章我们介绍了如何基于自动机、LLR以及自底向上语法分析来构造一个正则表达式引擎，但是感觉前文太过直接去描述这些实现的底层原理，而忽略了去讲述正则表达式本身。因此，本文我们将从正则表达式本身出发，将更为全面的去讲解正则表达式以及表达式引擎的构造过程，来作为前文的一个补充。

正则表达式定义

在甩出一堆数学定义之前，我们先缓冲一下，感受两个概念，一个是语言，另一个是表达式：

语言：如我们平常所说的话，它由句子组成（各种句子的集合），句子又由字组成；正则表达式说的话（如果它会说话的话）就是正则语言

正则表达式：它就像我们平常接触的算术表达式一样，由操作符，运算对象组成，这里我们完全可以将它和算术表达式对应起来理解

算术表达式用来做计算，正则表达式用来描述语言，如：a*b，表示语言：{b, ab，aab，aaab，...}

有了上面粗浅的理解后，我们就可以深入（形式化）了，先上一些前菜（基本概念）：

基本概念

字母表：符号的有穷非空集合，常用 ∑ 表示，如：{0, 1} 是二进制字母表，{a,b,...z} 是小写字母表（符号你可以理解为 char）

串（又叫 单词）：是从某个字母表中选择的符号的有穷序列，如：0101 是二进制字母表中选出的串

空串：出现 0 次符号的串，记作：ε，是可从任何字母表中选择的串（可理解为代码中的空字符串）

串的连接：设 x，y 都是串，则它们的连接就是 xy（你可以理解为字符串的连接），长度为两个串之和

字母表的幂：

1. 无论什么字母表， 它的零次幂为：{ε}

2. n 次幂等于长度为 n 的所有串的集合，如：∑ = {0, 1}，则 ∑^1 = {0, 1}，∑^2 = {00, 01, 10, 11}

3. 字母表 ∑ 上所有串的集合，记为 ∑^*，如：{0, 1}^* = {ε, 0, 1, 00, 01, ...}

语言：全部都从某个字母表 ∑ 中选出的串的集合称为语言，记为：L，L 不必包含带有 ∑ 所有符号的串，即：L ⊆ ∑^*

正则语言：就是正则表达式表示/描述/声明的语言，它的所有串都是由声明该语言的正则表达式构造，如上面 a*b 的例子，记正则表达式为：E，那么它的语言记为：L(E)

正则语言的运算

是的，语言也可以被当作值进行计算，计算的结果是新的语言，这里介绍三种语言的运算

并运算：两个语言 L 和 M 的并，记作：L ∪ M，是只属于 L 或 只属于 M，或同时属于两者的串的集合，即：交集

连接运算：两个语言 L 和 M 的连接，记作：L . M 或者 LM，取 L 中任意一个串与 M 中任意一个串连接起来所组成的串的集合，如：L = {001, 01, 111}, M = {ε, 001}，则 LM = {001, 01, 111, 001001, 01001, 111001}

闭包（或 * 或 克林闭包）：记作：L*，从 L 中取任意多个串，可能有重复，把所有这些串连接起来，这样的所有串组成的语言，如：L = {0, 11}，则 L* = {ε, 011, 110, 11110, ...}，01011 和 101 都不是该语言的串，形式化的说：L* = L^0 ∪ L^1 ∪ L^2 ∪ ... ∪ L^n

构造正则表达式

终于可以定义正则表达式了，如果你看到了这里，那么恭喜你可以体验到数学归纳法的魅力了

所有的代数表达式都是由基本的表达式开始的，如常量，变量，然后把一组特定的运算应用到这些基本表达式身上后构成了更复杂的表达式，如算术表达式由实数和整数这样的常量开始，加上变量，通过 + 和 x 等运算符变成更复杂的算术表达式，正则表达式也可以被这样的归纳定义（你可以思考一下我们程序中有哪些结构也是归纳定义的）：

归纳基础：基础包含三个部分：

1. 常量 ε 和 Ø 是正则表达式，分别表示语言：{ε} 和 Ø （即：不存在），即：L(ε) = {ε}，L(Ø) = Ø

2. 若 a 是任意符号，则 a 是正则表达式，表示语言：{a}，即：L(a) = {a}

3. 变量 L （大写斜体符号表示），它代表任意语言

归纳步骤：步骤包含四个部分（即：引入 4 种操作符）：

1. 如果 E 和 F 都是正则表达式，则 E | F 是正则表达式，表示 L(E) 和 L(F) 的并（参考上面语言的并运算），即：L(E | F) = L(E) ∪ L(F)

2. 如果 E 和 F 都是正则表达式，则 EF （也可写为：E.F ）是正则表达式，即：L(EF) = L(E)L(F) （参考上面语言的连接运算），如：0，1 是正则表达式，那么 01 表示的语言就是 {01}

3. 如果 E 是正则表达式，则 E * 是正则表达式，表示 L(E) 的闭包（参考上面语言的闭包运算），即：L(E*) =(L(E))*

4. 如果 E 是正则表达式，则 （E）（E 前后加上括号）也是正则表达式，与 E 表示相同的语言，即：L((E)) = L(E)

运算符优先级：* > . > | ，即 星 大于 连接 ，大于 并，若想调整运算顺序则添加括号

至此正则表达式的定义结束，我们完全可以像定义算术表达式那般定义正则表达式，现在该你一个正则表达式：abb|aba ，它其实是由基础的常量正则：a 和 b，通过连接（.）和 | 运算符组合而成，它所表示的语言，也可以通过 a 和 b 表示的语言：{a}，{b} 通过并运算和连接运算得到：{abb, aba}

现在你应该可以将平常说的字符组，量词，多选分支这些概念和上面的操作符对应起来了吧

注：现代正则表达式有更多的功能，比如：+，？，{n}，锚点等等，这些不会在本文讨论，这些功能都可以基于本文讨论的正则表达式扩展出来，你可以认为本文探讨的是正则表达式内核

正则表达式的代数定律（简化表达式）

真就数学课呗，代数定律都出来了，是的，如果把正则表达式看作像算术表达式一样的代数的话，那么它一定也会有类似 结合律，分配律这样的代数定律，这样的定律的好处是什么呢？

化简正则表达式，或者叫简化正则表达式，代数定律可以保证，简化后的正则和原始的是等价的（即：表示同一种语言），而这两者在程序视角看来，执行效率是不同的，往往简化后的更高效

当你写出一个很复杂的正则表达式时，也可以参考这些定律看看能否进行简化

结合律 & 交换律

以下斜体字母均为正则表达式

• L | M = M | L

• (L | M ) | N = L | (M | N)

• (LM)N = L(MN)

注意：LM ≠ ML

单位元

• ε L = L ε = L

注：零元不太用，故省略了

分配律

• L(M|N) = LM | LN

• (M|N) L = ML | NL

幂等律

• L | L = L

闭包相关定律

• (L *) * = L *

• ε * = ε

• L + = LL * = L * L ，即：正则表达式里的 + 可以用 * 实现

• L * = L + | ε

• (L +) + = L + （我自己证明的，不过直觉上就能看出来）

• L ? = ε | L ，即：正则表达式里的 ? 可以用 ε 和 | 来实现

至此我们回过头来看看我们的问题表达式：^[_a-z]([a-zA-Z0-9]+)*$，其中的 ([a-zA-Z0-9]+)* 等价于：([a-zA-Z0-9]+)+|ε 等价于：[a-zA-Z0-9]+|ε 也即：[a-zA-Z0-9]*

注：证明定律，可以通过对应到其语言的运算来证明（简单情况），也可通过泵引理（这里不谈，感兴趣可以自行搜索）来证明（通用）

实现正则表达式引擎

现在我们了解了正则表达式的本质，也了解了怎么通过代数法则去简化表达式，是否就可以结束了呢？

不，我们现在还在理论世界中，现实世界还有一个问题要我们思考：回溯

回溯（Backtracking）是搜索算法上的一个现象，当使用深度优先进行搜索时，如果当前路径无法进行下去，那么就会回到分叉口，寻找另一条路继续搜索

这一块很多算法书，或者正则表达式的书里都有讲到

但是如果要正真理解回溯，或者说是正则表达式的匹配原理（它是如何执行的，为什么要 DFS），没有什么是比自己实现一个正则引擎来的更有效

什么是正则表达式引擎

首先它是一个程序，正则引擎包含几个部分：

1. 将正则表达式编译为可进行串匹配的可执行机器（程序）

2. 执行这个机器（程序），进行匹配，如果匹配返回 true，若不匹配则返回 false

稍微形式化一点，正则引擎接受一段正则表达式，然后帮我们构造这样一个程序：该程序接受一段字符串，返回的结果是这个串是否属于该正则表达式定义的语言

这个构造出来的程序，其实是某种抽象机器的程序实现，该抽象机器我们称之为：有穷自动机

从上面的描述中，我们不难看出，有穷自动机等价于正则表达式（克林定理），也就是说正则语言，可以通过有穷自动机来描述（正则表达式可视为自动机的 DSL）

有穷自动机

非形式化的来说，自动机是一个包含多状态（状态数量是有限的），且可以在状态之间转换的抽象机器，当读取一个输入时，就从一个状态转换到下一个状态，它有一个初始状态，和一个或多个接受状态

根据可转换状态数，可以分为两类：若读取一个输入只能进入确定的某个状态，则称为确定型有穷自动机（DFA），如果有多个候选状态可以进入，则称为非确定型有穷自动机（NFA）

确定型有穷自动机（DFA）

形式化的来说，一个确定型有穷状态机包扩：

1. 一个有穷状态集合，记作：Q

2. 一个有穷输入符号集合，记作：∑

3. 一个状态转移函数，记作：δ，δ(q，a) = p，指的是：状态 q 接受 a 符号，进入状态 p

4. 一个初始状态 q0 ∈ Q

5. 一个终结状态或接受状态的集合 F，F ⊆ Q

一般用个 5 元组去表示，比如 DFA： A = (Q, ∑, δ, q0, F)，如下是个具体的例子（用转移图表示自动机）：

Q = {q0, q1, q2, q3}，∑ = {a, b}，初始状态：q0，F = {q3}，状态转移函数 δ :

δ(q0, a) = q1， δ(q1, b) = q2， δ(q2, b) = q2，δ(q2, a) = q3

它描述的正则语言，与正则表达式：abb*a 等价，当输入为："aba" 时到达接受状态 q3，匹配结束，若输入为："abc" 时，因为在 q2 状态无法流转，且 q2 不是接受状态，故匹配失败

非确定型有穷自动机（NFA）

非确定型有穷自动机构造和确定型类似，区别在于状态转移函数 δ 上，它接受一个状态和符号后，返回的是一个状态的集合，如：δ(q，a) = {p, s}，q 接受 a 后可以进入状态 p 或 s，照样看个例子：

状态 q1 在接受 b 后可以进入自己，或 q2，这就是非确定的含义，同样，我们可以用 5 元组去表示：N = (Q, ∑, δ, q0, F)

带 ε 转移的非确定型有穷自动机（ε-NFA）

它是一种特殊的 NFA，同样看个例子先：

带 ε 转移，意外这状态可以不接受任何符号，直接流转到另一个状态，如上面的 q2

引入 ε-NFA 其实是为了便利，尤其是它和正则表达式的关系非常密切

注：上面三种自动机表示语言都是一样的，故它们都是等价的

将正则表达式编译为 ε-NFA

有了有穷自动机后，我们就可以运行这个机器去做串的匹配了，但是在探讨运行自动机之前，我们先要将正则表达式编译为自动机，这个编译过程就是前面说的输入正则表达式，构造一个自动机的程序

我们使用 Thompson 构造算法（或叫：McNaughton-Yamada-Thompson algorithm），该算法的核心是通过结构归纳法来构造对应 ε-NFA，故名思义，就是基于正则表达式的结构（前面说定义的时候说过，它是通过归纳的方式构造的）进行归纳构造的，将正则表达式 R 转换为 NFA（后面省略 ε），首先将 R 的子表达式是转换为 NFA，再通过操作符构造更复杂的 NFA

归纳基础：对应两种基本表达式

• 识别空串（ε）的 NFA

• 识别单个符号的 NFA，如下图只识别 a 的 NFA

归纳步骤：对应三种构造

• 并（Union）：R = S | T，正则表达式 S 和 T 的并 R，对应于 NFA(S) 和 NFA(T) 的并，即引入新的初始状态 i 和新的接受状态 f，然后改 i 添加两个 ε-trainsitions，连接 NFA(S) 和 NFA(T) 的初始状态，将 NFA(S) 和 NFA(T) 的接受状态改为非接受状态，并添加 ε-trainsitions 指向新的接受状态 f，至此构造完成

• 连接（Concatenation）：R = ST， 正则表达式 S 和 T 的连接 R，对应于 NFA(S) 和 NFA(T) 的连接，即串联两个 NFA，将 NFA(S) 的接受状态改为非接受，然后构造一个 ε-trainsition 指向 NFA(T) 的初始状态

• 闭包（Closure (Kleene Star)）：R = S*，将 NFA(S) 的接受状态指向初始状态（添加 ε-trainsition），引入新的初始状态 i，新接受状态 f，添加 ε-trainsition 让 i 指向 f，i 通过 ε-trainsition 连接 NFA(S) 的初始状态，NFA(S) 的接受状态改为非接受，并添加 ε-trainsition 指向 f

至此三种构造描述完毕，我们通过两种归纳基础加上三种归纳步骤，即可将一个复杂的正则表达式转换为一个 NFA

习题：通过上面介绍的算法将正则表达式 (a∣b)*c 转换为 NFA (答案在下面参考文献里)

提示：先构造 a、b、c 的 NFA，再基于 | 和 * 构造新 NFA

在程序实现时，我们需要将正则表达式进行预处理，处理的方式有两种，一种是将正则表达式解析为一颗语法树，然后遍历语法树，构造为 NFA（有趣的是这个语法解析器又可以基于正则表达式来实现，真实套娃）；另一种是以表达式的视角进行处理，不用解析为一颗树，我们先将表达式进行转换，添加上连接操作符（.）然后再将中缀表达式转换为后缀表达式（请回忆一下大学数据结构课程），转换为后缀表示之后，就可以基于一个栈来构造 NFA 了

下面就是实现 Thompson 构造算法了，首先我们定义一个类型来表示 NFA 状态（其实它也可以用于表示一个 NFA）：

@Getter
@Setter
@AllArgsConstructor
public class State {
    /**
     * 是否是接受状态
     */
    private boolean isEnd;
    /**
     * 状态转换函数（接受符号）
     */
    private Map<Character, State> transition;
    /**
     * 状态转换函数（接受空串：ε）
     */
    private List<State> epsilonTransitions;

    public static State create(boolean isEnd) {
        return new State(isEnd, new HashMap<>(), new LinkedList<>());
    }

    public void addEpsilonTransitions(State to) {
        this.epsilonTransitions.add(to);
    }

    public void addTransition(Character symbol, State to) {
        this.transition.put(symbol, to);
    }
}

再用一个类型表示 NFA (这里用的转移图，虽然叫 Table)：

@Value(staticConstructor = "of")
public class Table {
    State start;
    State end;
}

它只需要保存 start 节点和 end 节点，其它节点（状态）都会被 start 串起来，最终到 end 节点，其次这种结构非常方便用于实现 Thompson 构造算法（这个 start 和 end 很容易和上面的图示对应起来）

然后基于归纳基础，构造两种 NFA：

    /**
     * 归纳基底：仅包含 ε 的 nfa
     */
    private static Table fromEpsilon() {
        State start = State.create(false);
        State end = State.create(true);
        start.addEpsilonTransitions(end);
        return Table.of(start, end);
    }

    /**
     * 归纳基底：仅包含符号的 nfa
     */
    private static Table fromSymbol(Character symbol) {
        State start = State.create(false);
        State end = State.create(true);
        start.addTransition(symbol, end);
        return Table.of(start, end);
    }

再实现归纳步骤：

    /**
     * 两个 nfa 的连接
     */
    private static Table concat(Table first, Table second) {
        first.getEnd().addEpsilonTransitions(second.getStart());
        first.getEnd().setEnd(false);
        return Table.of(first.getStart(), second.getEnd());
    }

    /**
     * 两个 nfa 的并
     */
    private static Table union(Table first, Table second) {
        State newStart = State.create(false);
        newStart.addEpsilonTransitions(first.getStart());
        newStart.addEpsilonTransitions(second.getStart());

        State newEnd = State.create(true);
        first.getEnd().addEpsilonTransitions(newEnd);
        first.getEnd().setEnd(false);
        second.getEnd().addEpsilonTransitions(newEnd);
        second.getEnd().setEnd(false);
        return Table.of(newStart, newEnd);
    }

    /**
     * nfa 的闭包
     */
    private static Table closure(Table nfa) {
        State newStart = State.create(false);
        State newEnd = State.create(true);

        newStart.addEpsilonTransitions(newEnd);
        newStart.addEpsilonTransitions(nfa.getStart());
        nfa.getEnd().addEpsilonTransitions(newEnd);
        nfa.getEnd().addEpsilonTransitions(nfa.getStart());
        nfa.getEnd().setEnd(false);
        return Table.of(newStart, newEnd);
    }

完全和上面的图示对应，然后我们基于一个栈将后缀表达式转换为 NFA：

    /**
     * 后缀正则表达式转为 NFA
     */
    public static Table toNFA(String postifx) {
        if (postifx.isEmpty()) {
            return fromEpsilon();
        }
        Stack<Table> stack = new Stack<>();
        for(char token : postifx.toCharArray()) {
            switch (token) {
                case '*':
                    stack.push(closure(stack.pop()));
                    break;
                case '|': {
                    Table right = stack.pop();
                    Table left = stack.pop();
                    stack.push(union(left, right));
                    break;
                }
                case '.': {
                    Table right = stack.pop();
                    Table left = stack.pop();
                    stack.push(concat(left, right));
                    break;
                }
                default:
                    stack.push(fromSymbol(token));
                    break;
            }
        }
        return stack.pop();
    }

比如要构造 (a∣b)*c 的 NFA，具体过程如下所示：

1. 先添加连接操作符： (a∣b)*c -> (a∣b)*.c

2. 转换为后缀表达式：(a∣b)*.c -> ab∣*c. （看到这一步，你应该明白为什么用栈去构建了）

3. 构造 NFA，过程如下：

至此我们的自动机构造完毕，下一步，进行搜索

搜索算法

递归回溯搜索

有了自动机，就可以运行它了，我们将需要匹配的串输入给自动机，让它进行状态流转，如果最后到了串尾，且当前状态是接受状态，则返回成功，因为 NFA 可能有多条路可以走，所以最简单的搜索算法就是基于 NFA 的递归回溯搜索算法（本质是就是一种深度优先搜索）

这种算法的效率并不算高，它的最坏时间复杂度可以达到 O(2^n)，因为它本质上是一种群举算法，最坏情况会遍历所有路径，如我们前面 checkstyle 的例子，它就会走所有路线（且没有一条满足）

Thompson 搜索算法（多状态搜索算法）

Thompson 在论文《Regular Expression Search Algorithm》中介绍了一种搜索算法，就是不一次只选则一条路走，而是同时选择多条路走，这样可以大大提高效率，如下例子，匹配 "abb" 时：

q0 可以同时走到 q1 和 q5 上，q1 和 q5 同时接受 a，所以下一步又同时走到 q2 和 q6，再同时接受 b，到 q3 和 q7，再读入 b 时，只能走到 q8，q8 又可直接到接受状态 q9，匹配结束，返回成功

该算法将每次状态流转为另一个状态，变成了另一个状态集合，该集合又可继续接收符号流转到下一个状态集合，直到串尾，若当前状态集合包含接受状态则表示匹配成功

要实现该算法，我们需要处理一下状态的 ε-闭包，因为我们发现当状态有 ε-trainsitions 可以直接跳到一个状态（也必须要这么做），状态 q 的 ε-闭包 eclose(q) 定义为：

归纳基础：状态 q 属于 eclose(q)

归纳步骤：如果 p 属于 eclose(q)，并且有从 p 到 r 的 ε-trainsition，则 r 属于 eclose(q)

代码实现为：

    /**
     * 计算 NFA 状态 state 的 ε-闭包
     * visited 防止无限递归
     */
    private static Set<State> eclose(State state, Set<State> visited) {
        Set<State> res = new HashSet<>();
        if (!visited.contains(state)) {
            // 1) 自身
            res.add(state);
            visited.add(state);
        }
        // 2) 递归求 eclose(ε-trainsitions)
        res.addAll(state.getEpsilonTransitions().stream()
                .map(s -> eclose(s, visited))
                .reduce((r, s) -> {
                    r.addAll(s);
                    return r;
                }).orElse(new HashSet<>()));
        return res;
    }

然后 Thompson 搜索算法 即可实现为：

   private static boolean multipleStatesSearch(Table nfa, String word) {
        Set<State> currentStates = eclose(nfa.getStart(), new HashSet<>());
        for (char symbol : word.toCharArray()) {
            Set<State> nextStates = new HashSet<>();
            for (State state : currentStates) {
                State next = state.getTransition().get(symbol);
                if (next != null) {
                    nextStates = eclose(next, new HashSet<>());
                }
            }
            currentStates = nextStates;
        }
        return currentStates.stream().anyMatch(State::isEnd);
    }

从初始状态的 ε-闭包开始依次往后走，每走一步都会求其 ε-闭包（消除 ε-trainsition），该算法的复杂度是 O(n^2)

最后我们将所有代码拼在一起，就变成了一个正则引擎：

    public static Function<String, Boolean> compile(String regx) {
        Table nfa = NFAOp.toNFA(Expr.toPostfix(Expr.addConcatOperator(regx)));
        return word -> NFAOp.recognizeByMState(nfa, word);
    }

    public static void main(String[] args) {
        Function<String, Boolean> match = compile("a*b");
        System.out.println(match.apply(""));
        System.out.println(match.apply("b"));
        System.out.println(match.apply("aab"));
        System.out.println(match.apply("abb"));
    }

转换为 DFA 进行搜索

你以为结束了？不，还没有，任何的 NFA 都可以转换为其等价的 DFA，我们知道 DFA 是确定型的，每次状态流转不会需要选择路径，这就意味着我们可以将 NFA 转换为 DFA 然后进行搜索，以达到一个更高的效率

我们通过子集构造算法将 NFA 转为 DFA，设我们有一个 ε-NFA E = (Qe, ∑, δe, q0, Fe)，其对应的 DFA D 为：

D = (Qd, ∑, δd, qd, Fd)，字母表是相同的，其余每部分定义如下：

1. Qd 是 Qe 子集的集合，即：Qd = {S| S ⊆ Qe 使得 S = eclose(S)}

2. qd = eclose(q0)

3. Fd 是至少包含 Fe 中一个接受状态的状态集合

4. 对于所有属于 ∑ 的 a 和属于 Qd 的集合 S，δd(S, a) 的计算方法如下：

   1. 设 S = {p1, p2, ..., pk}

   2. 计算 δe(p1, a) ∪ δe(p2, a) ... ∪ δe(pk, a)，设这个集合为：{r1, r2, .. rm}

   3. 则 δd(S, a) = eclose(r1) ∪ eclose(r2) ... ∪ eclose(rm)

老实说上面定义写的非常清楚，新的 DFA 的初始状态为原来 NFA 初始状态的 ε-闭包，接受状态也变成了包含原接受状态的集合，δd 的类型也变成了状态集合到状态集合到转换，只是每次转换的时候要求一遍 ε-闭包

习题：将上面 Thompson 搜索算法 的 NFA 转换为对应的 DFA

代码实现，我们先定义一个表示 DFA 的状态（其实这个状态表示了整个 DFA 的流转图）：

@Getter
@Setter
@AllArgsConstructor
public class DFAState {
    /**
     * NFA 的状态子集：S ⊆ Q(nfa) 使得 S = ECOLSE(S)
     */
    private Set<State> nfaStates;
    /**
     * 状态转换函数（接受符号）
     */
    private Map<Character, DFAState> transitions;
    /**
     * 是否是接受状态
     */
    private boolean isEnd;
}

子集构造算法实现：

    /**
     * 判断 NFA 状态子集合 S 是否为 DFA 的接受状态
     */
    private static boolean isEnd(Set<State> states) {
        return states.stream().anyMatch(State::isEnd);
    }

    /**
     * 获取某 NFA 状态集合 S 在某符号上的 下一个状态的 ε-闭包集合
     */
    private static Set<State> getNextState(Set<State> states, Character symbol) {
        Set<State> res = new HashSet<>();
        for (State s : states) {
            State next = s.getTransition().get(symbol);
            if (next != null) {
                res.addAll(eclose(next, new HashSet<>()));
            }
        }
        return res;
    }

    /**
     * 计算 DFA 某状态（对于 NFA 状态集合）的状态转移函数
     */
    private static Map<Character, Set<State>> getTransitions(Set<State> states) {
        // 符号集合
        Set<Character> symbols = states.stream()
                .flatMap(s -> s.getTransition().keySet().stream())
                .collect(Collectors.toSet());
        Map<Character, Set<State>> res = new HashMap<>();
        for (Character symbol : symbols) {
            res.put(symbol, getNextState(states, symbol));
        }
        return res;
    }

    /**
     * 根据初始状态集合构造 DFA
     */
    private static DFAState createDFAState(Set<State> states) {
        if (getTransitions(states).isEmpty()) {
            return DFAState.create(states, new HashMap<>(), isEnd(states));
        } else {
            Map<Character, Set<State>> transitions = getTransitions(states);
            DFAState dfaState = DFAState.create(states, isEnd(states));
            dfaState.setTransitions(MapUtils.mapValue(transitions, s -> {
                if (s.containsAll(states) && states.containsAll(s)) {
                    return dfaState;
                }
                return createDFAState(s);
            }));
            return dfaState;
        }
    }

    private static DFAState convertToDFA(Table nfa) {
        DFAState dfaStart = createDFAState(eclose(nfa.getStart(), new HashSet<>()));
        return dfaStart;
    }

然后就可以基于此 DFA 进行搜索了：

    private static boolean searchByDFA(DFAState state, String word, int position) {
        if (position == word.length()) {
            return state.isEnd();
        } else {
            Character symbol = word.charAt(position);
            DFAState next = state.getTransitions().get(symbol);
            if (next != null) {
                return searchByDFA(next, word, position + 1);
            } else {
                return false;
            }
        }
    }		
    public static boolean recognizeByDFA(Table nfa, String word) {
        return searchByDFA(convertToDFA(nfa), word, 0);
    }

搜索算法非常简单，就是顺着 DFA 流转就行（注意：不会有回溯）

仔细比较 DFA 的搜索算法和 Thompson 搜索算法，发现其实 Thompson 搜索算法就是在一遍搜索的同时构造 DFA 进行搜索

总结

现在你应该更加了解正则表达式是怎么回事了吧？包括怎么去分析自己写的表达式的性能，所谓正则表达式的可视化，其实就是画的自动机；限于篇幅本文讲到的都是正则表达式核心方面的内容，还有一些其它方面的知识（比如：正则语言的性质），以后有机会再补充，本文虽洋洋洒洒近万字，但是还是停留在理论层面，实战应用方面，希望你能拿起这些理论武器去优化你的表达式

完整项目地址：https://github.com/Panda-Hope/Regex-Resolver

参考

• Implementing a Regular Expression Engine
• Regular Expression Matching Can Be Simple And Fast
• 《自动机理论、语言和计算导论（原书第3版）》

• 《正则指引》

• 《JavaScript 正则表达式迷你书（1.1 版）》

• Ken Thompson (1968) Regular Expression Search Algorithm （不建议看原文，有些年代）