如何从零写一个正则表达式引擎？
从零开始构建一个正则表达式引擎，这绝对是一项充满挑战但又极其有趣的项目。它不仅仅是关于匹配字符的逻辑，更是关于状态机、解析器和算法的深度融合。如果你想深入理解正则表达式的底层原理，动手实现一个引擎绝对是最好的方式。
我将尽量以一种非AI的、更具人情味和技术细节的方式来阐述这个过程，仿佛我是一个在深夜代码的开发者，一边喝着咖啡，一边思考如何让这个小小的匹配器变得更强大。
第一步：理解正则表达式的本质——“状态”
首先，我们得明白正则表达式到底是什么。它不是简单的字符串查找，而是一门描述“模式”的语言。而匹配一个模式的过程，本质上就是在一系列“状态”之间跳转。
想象一下，我们正在寻找一个模式 `abc`。
当我们看到 `a` 时，我们处于一个“期待 `a`”的状态。
如果我们看到了 `a`，我们就进入“期待 `b` 或 `c`”的状态。
如果我们看到了 `b`，我们又回到“期待 `b` 或 `c`”的状态（因为 `b` 可以匹配零个或多个 `b`）。
如果我们看到了 `c`，我们就成功了！
这种状态的转移，正是我们构建引擎的核心思想。最能描述这种状态转移的是一种叫做 有限状态自动机 (Finite State Automaton, FSA) 的数学模型。
FSA 通常有两种：
1. 确定性有限状态自动机 (Deterministic Finite Automaton, DFA)：对于每个状态和每个输入字符，只有一个确定的下一个状态。
2. 非确定性有限状态自动机 (Nondeterministic Finite Automaton, NFA)：对于每个状态和每个输入字符，可能存在多个可能的下一个状态，甚至可能在不消耗任何输入字符的情况下转移到另一个状态（epsilon 迁移，εtransition）。
第二步：选择你的“武器”——NFA还是DFA？
理论上，NFA 和 DFA 的表达能力是等价的，即任何一个能被NFA识别的语言，也能被DFA识别，反之亦然。但是，它们在实现上的选择会影响你的引擎的设计思路。
NFA 路线：
优点：从正则表达式到NFA的转换通常更直接、更简单。你可以一步步地构建 NFA 的状态和转移。而且，处理像 `|` (或) 这样的操作时，NFA 的结构更自然。
缺点：匹配过程可能涉及回溯（backtracking）。当遇到分叉时，NFA 需要“同时”尝试所有可能的路径，这在实现上可能需要递归或堆栈来管理。如果模式很复杂，回溯可能会导致性能问题，尤其是一些邪恶的正则表达式（catastrophic backtracking）。
DFA 路线：
优点：一旦构建好 DFA，匹配过程就是线性的、无需回溯的。它会非常快！引擎只需要跟踪当前状态和下一个输入字符，然后查找相应的状态转移即可。
缺点：从正则表达式转换到 DFA 的过程比较复杂，通常需要先构建 NFA，然后再将 NFA 转换为 DFA (NFA to DFA conversion)。这个转换过程可能会产生大量的状态，尤其是对于包含量词（``, `+`, `?`）和分支（`|`）的复杂正则表达式。
我的建议是（如果你想从零开始，有点挑战但更具学习价值）：先从 NFA 入手。 NFA 的构建更直观，你能更好地理解正则表达式的语法是如何映射到状态机上的。然后再考虑如何优化，比如将 NFA 转换为 DFA（或者直接设计一个基于 NFA 的模拟器，但要小心回溯）。
第三步：构建 NFA——正则表达式的骨架
好的，我们决定走 NFA 的路线。一个正则表达式可以被看作是一个语法树，树的叶子节点是匹配单个字符的单元（比如 `a`，`.`），内部节点是各种操作符（比如 `.` 连接、`|` 或、`` 量词）。
我们可以利用这个语法树来递归地构建 NFA。每个正则表达式片段都会对应一个 NFA，它有一个开始状态和一个结束状态。
核心组件：
1. 状态 (State)：表示我们程序可能处于的某个“时刻”。每个状态需要有一个唯一的标识符。
2. 转移 (Transition)：表示从一个状态到另一个状态的过程，这个过程可能伴随着一个字符的匹配（或者是一个空字符 `ε`）。
一个转移需要：起始状态、结束状态、匹配的字符（或者 `ε`）。
如何构建 NFA？
我们需要一个解析器来解析正则表达式字符串，并构建出对应的 NFA。
基本单元 (Literal Character / Wildcard): 例如，正则表达式 `a` 对应一个 NFA：`Start a> End`。正则表达式 `.` 对应：`Start .> End`（`.` 匹配任意字符）。
连接 (Concatenation)：例如，正则表达式 `ab` 可以看作是 `a` 的 NFA 和 `b` 的 NFA 连接起来。如果 `a` 的 NFA 是 `StartA a> EndA`，`b` 的 NFA 是 `StartB b> EndB`，那么 `ab` 的 NFA 就是：`StartA a> EndA b> EndB`。关键在于将第一个 NFA 的结束状态连接到第二个 NFA 的开始状态。
或 (Alternation)：例如，正则表达式 `a|b`。我们需要创建一个新的开始状态和一个新的结束状态。
从新开始状态到 `a` 的 NFA 的开始状态，通过 `ε` 转移。
从新开始状态到 `b` 的 NFA 的开始状态，通过 `ε` 转移。
从 `a` 的 NFA 的结束状态到新结束状态，通过 `ε` 转移。
从 `b` 的 NFA 的结束状态到新结束状态，通过 `ε` 转移。
这样，从新开始状态出发，可以选择先走 `a` 的路径，或者先走 `b` 的路径。
零个或多个 (``): 例如，正则表达式 `a`。这比直接匹配字符要复杂一些，因为它引入了 `ε` 转移。
创建一个新的开始状态 `S` 和一个新的结束状态 `E`。
从 `S` 到 `E`，通过 `ε` 转移（匹配零个 `a`）。
从 `S` 到 `a` 的 NFA 的开始状态，通过 `ε` 转移。
从 `a` 的 NFA 的结束状态到 `a` 的 NFA 的开始状态，通过 `ε` 转移（允许重复匹配 `a`）。
从 `a` 的 NFA 的结束状态到 `E`，通过 `ε` 转移（完成 `a` 的匹配）。
一个或多个 (`+`): `a+` 可以看作 `aa`。所以可以先构建 `a` 的 NFA，然后将 `a` 的 NFA 的开始状态直接连接到 `a` NFA 的 `a` 匹配部分的开始状态（移除 `a` 的第一个 `ε` 转移），并从 `a` 的结束状态连接到 `a` 匹配部分的结束状态。或者直接构建一个更符合 `a+` 定义的 NFA。
零个或一个 (`?`): `a?` 可以看作 `a|ε`。
解析器设计：
你需要一个好的解析器来处理正则表达式的语法。常见的做法是使用递归下降解析器 (Recursive Descent Parser)，或者更强大的工具如 yacc/bison（虽然从零开始可能不包括使用这些工具，但理解它们的原理有益）。
对于简单的正则表达式，你可以按照操作符的优先级（例如，`` 和 `+` 优先级高于连接，连接优先级高于 `|`）来构建解析函数。
例如，你可以有这样的函数：
`parseExpression()`: 处理 `|` 操作符。
`parseTerm()`: 处理连接操作符。
`parseFactor()`: 处理量词 ``, `+`, `?`。
`parseAtom()`: 处理单个字符、`.` 或分组 `()`。
每个函数在解析完一部分表达式后，会返回对应的 NFA 片段。
例子：解析 `(a|b)c`
1. `parseExpression` 调用 `parseTerm`。
2. `parseTerm` 调用 `parseFactor`。
3. `parseFactor` 遇到 `(`，调用 `parseAtom`。
4. `parseAtom` 处理 `(a|b)`。
解析 `(a|b)`：
`parseExpression` 调用 `parseTerm` 解析 `a`，得到 NFA_a。
`parseTerm` 调用 `parseFactor` 解析 `b`，得到 NFA_b。
`parseTerm` 将 NFA_a 和 NFA_b 合并成 `a|b` 的 NFA (NFA_ab)。
`parseFactor` 发现 `` 量词，将 NFA_ab 包装成 `(a|b)` 的 NFA (NFA_ab_star)。
5. `parseTerm` 调用 `parseFactor` 解析 `c`，得到 NFA_c。
6. `parseTerm` 将 NFA_ab_star 和 NFA_c 连接起来，得到最终的 NFA。
第四步：执行 NFA——匹配引擎的核心
有了 NFA，我们还需要一个能够“运行”它来匹配输入字符串的引擎。这里有两个主要方向：
1. NFA 模拟器 (NFA Simulator)：
这种方法直接模拟 NFA 的工作方式，处理 `ε` 转移和多个可能状态。
算法思路：
维护一个当前可能处于的状态集合 `current_states`。
开始时，`current_states` 包含所有从起始状态出发，通过 `ε` 转移可以到达的状态（包括起始状态本身）。
对于输入字符串中的每个字符 `c`：
创建一个新的空集合 `next_states`。
对于 `current_states` 中的每个状态 `s`：
查找所有从 `s` 出发，匹配字符 `c` 的转移，将其结束状态加入 `next_states`。
对 `next_states` 中的所有状态执行 `ε` 闭包（即所有能通过 `ε` 转移到达的状态），并合并到 `next_states` 中。
将 `current_states` 更新为 `next_states`。
匹配成功当且仅当，在处理完所有输入字符后，`current_states` 集合中包含 NFA 的任何一个接受状态。
实现细节：`ε` 闭包的计算是一个关键。你可以用一个递归或迭代的方法来找到所有可达状态。当处理 `ε` 转移时，需要特别小心，因为它不消耗输入字符。
2. NFA 到 DFA 的转换，然后执行 DFA：
这是更复杂的，但一旦 DFA 构建好，匹配速度会非常快。
转换算法 (子集构造法 Subset Construction)：
DFA 的每个状态对应 NFA 的一个状态集合。
DFA 的起始状态是 NFA 起始状态的 `ε` 闭包。
对于 DFA 的每个状态 `D_state` (它代表一个 NFA 状态集合 `N_set`) 和输入字符 `c`：
找到所有从 `N_set` 中状态出发，通过字符 `c` 转移到达的状态集合 `N_set_c`。
计算 `N_set_c` 的 `ε` 闭包，得到新的 NFA 状态集合 `N_set_prime`。
如果 `N_set_prime` 是一个新的状态集合，则为 DFA 创建一个新状态 `D_state_prime`，并将 `D_state` 到 `D_state_prime` 的转移标记为 `c`。
如果 `N_set_prime` 已经存在于 DFA 中，则直接将 `D_state` 到该现有状态的转移标记为 `c`。
一个 DFA 状态是接受状态，当且仅当它对应的 NFA 状态集合中包含 NFA 的任何一个接受状态。
问题：这个转换过程可能产生指数级的状态数，尤其是在处理 `` 和 `|` 组合时。例如，`abc...` 这样的模式会生成很多状态。实际引擎通常会使用一些优化技术，比如状态最小化。
推荐路线（对于初学者）： 先实现 NFA 模拟器。这是理解 NFA 工作方式最直接的方法。你会遇到处理 `ε` 转移和管理状态集合的挑战，但这些都是核心概念。
第五步：处理高级特性和优化
一旦基本功能实现，你可以开始添加更多特性和进行优化：
匹配不同类型的量词: `?`, `{n}`, `{n,}`, `{n,m}` 等。这些都可以通过组合 `ε` 转移和状态复制来处理。
分组 `()` 和反向引用 `1`: 反向引用是 非常非常困难 的一部分。实现它需要更复杂的解析和匹配机制，可能不再是纯粹的 NFA/DFA 模型，需要一种能够“记住”捕获组内容的匹配器。常见的做法是使用带有捕获组的 NFA/DFA，并在匹配时记录匹配到的子串。
字符类 `[]`, 范围 `[az]`, 否定 `[^...]`: 这些会影响 `parseAtom` 函数，需要解析方括号内的内容，并为字符类创建相应的转移（或者为每个字符类生成多个转移）。
锚点 `^`, `$`: `^` 表示字符串开头，`$` 表示字符串结尾。这可以看作是对 NFA 匹配结果的后处理，或者在匹配开始/结束时引入特殊的状态或条件。
性能优化:
NFA 到 DFA 的转换 (Thompson's Construction / Glushkov's Construction)：如果你选择先构建 NFA，可以尝试将其转换为 DFA 来获得更好的匹配性能。
状态最小化: 将冗余的 DFA 状态合并，减少状态数量。
位向量: 对于具有大量状态的 DFA，可以使用位向量来表示当前状态集合，这可以提高效率。
剪枝回溯: 如果你选择了 NFA 模拟器，需要考虑如何避免灾难性的回溯。例如，限制递归深度，或者在某些情况下切换到更快的匹配算法。
提前拒绝: 在匹配过程中，如果发现当前状态和剩余输入字符串不匹配的可能性很高，可以提前终止匹配。
第六步：测试、测试、再测试
正则表达式引擎的实现极度依赖于对各种边界情况和复杂模式的正确处理。
简单测试: `a`, `ab`, `a|b`, `a` 等。
复杂组合: `(a|b)c`, `a(b|c)d`。
量词: `a`, `a+`, `a?`, `a{3}`, `a{2,4}`。
字符类: `[abc]`, `[az]`, `[^09]`。
空字符串匹配: `""`, `a`, `a?` 在空字符串上。
空模式匹配: 空模式 (`""`) 应该匹配空字符串。
回溯陷阱: 设计一些容易导致灾难性回溯的模式，确保你的引擎不会崩溃或耗尽资源。
边界测试: 字符串的开头和结尾。
总结一下构建过程的关键步骤：
1. 理解 FSA: 深入理解 NFA 和 DFA 的概念。
2. 解析正则表达式: 将文本模式转化为内部表示，例如抽象语法树 (AST)。
3. 构建 NFA: 根据 AST 递归地生成 NFA，为每个正则表达式操作创建相应的 NFA 结构。
4. 实现匹配逻辑:
NFA 模拟器: 使用状态集合和 `ε` 闭包来执行 NFA。
或者：转换为 DFA 并执行。
5. 处理高级特性: 逐步加入量词、字符类、分组等。
6. 优化性能: 考虑 NFADFA 转换、状态最小化等技术。
7. 严格测试: 覆盖各种边界情况和复杂模式。
从零开始构建一个完整的正则表达式引擎是一项浩大的工程，但每一步都是对计算机科学基本原理的深刻实践。你会接触到编译原理、算法设计和数据结构等多个领域。
祝你在构建自己正则表达式引擎的旅程中，收获满满！这绝对是一次让你真正“玩转”模式匹配的绝佳机会。
我将尽量以一种非AI的、更具人情味和技术细节的方式来阐述这个过程，仿佛我是一个在深夜代码的开发者，一边喝着咖啡，一边思考如何让这个小小的匹配器变得更强大。
第一步：理解正则表达式的本质——“状态”
首先，我们得明白正则表达式到底是什么。它不是简单的字符串查找，而是一门描述“模式”的语言。而匹配一个模式的过程，本质上就是在一系列“状态”之间跳转。
想象一下，我们正在寻找一个模式 `abc`。
当我们看到 `a` 时，我们处于一个“期待 `a`”的状态。
如果我们看到了 `a`，我们就进入“期待 `b` 或 `c`”的状态。
如果我们看到了 `b`，我们又回到“期待 `b` 或 `c`”的状态（因为 `b` 可以匹配零个或多个 `b`）。
如果我们看到了 `c`，我们就成功了！
这种状态的转移，正是我们构建引擎的核心思想。最能描述这种状态转移的是一种叫做 有限状态自动机 (Finite State Automaton, FSA) 的数学模型。
FSA 通常有两种：
1. 确定性有限状态自动机 (Deterministic Finite Automaton, DFA)：对于每个状态和每个输入字符，只有一个确定的下一个状态。
2. 非确定性有限状态自动机 (Nondeterministic Finite Automaton, NFA)：对于每个状态和每个输入字符，可能存在多个可能的下一个状态，甚至可能在不消耗任何输入字符的情况下转移到另一个状态（epsilon 迁移，εtransition）。
第二步：选择你的“武器”——NFA还是DFA？
理论上，NFA 和 DFA 的表达能力是等价的，即任何一个能被NFA识别的语言，也能被DFA识别，反之亦然。但是，它们在实现上的选择会影响你的引擎的设计思路。
NFA 路线：
优点：从正则表达式到NFA的转换通常更直接、更简单。你可以一步步地构建 NFA 的状态和转移。而且，处理像 `|` (或) 这样的操作时，NFA 的结构更自然。
缺点：匹配过程可能涉及回溯（backtracking）。当遇到分叉时，NFA 需要“同时”尝试所有可能的路径，这在实现上可能需要递归或堆栈来管理。如果模式很复杂，回溯可能会导致性能问题，尤其是一些邪恶的正则表达式（catastrophic backtracking）。
DFA 路线：
优点：一旦构建好 DFA，匹配过程就是线性的、无需回溯的。它会非常快！引擎只需要跟踪当前状态和下一个输入字符，然后查找相应的状态转移即可。
缺点：从正则表达式转换到 DFA 的过程比较复杂，通常需要先构建 NFA，然后再将 NFA 转换为 DFA (NFA to DFA conversion)。这个转换过程可能会产生大量的状态，尤其是对于包含量词（``, `+`, `?`）和分支（`|`）的复杂正则表达式。
我的建议是（如果你想从零开始，有点挑战但更具学习价值）：先从 NFA 入手。 NFA 的构建更直观，你能更好地理解正则表达式的语法是如何映射到状态机上的。然后再考虑如何优化，比如将 NFA 转换为 DFA（或者直接设计一个基于 NFA 的模拟器，但要小心回溯）。
第三步：构建 NFA——正则表达式的骨架
好的，我们决定走 NFA 的路线。一个正则表达式可以被看作是一个语法树，树的叶子节点是匹配单个字符的单元（比如 `a`，`.`），内部节点是各种操作符（比如 `.` 连接、`|` 或、`` 量词）。
我们可以利用这个语法树来递归地构建 NFA。每个正则表达式片段都会对应一个 NFA，它有一个开始状态和一个结束状态。
核心组件：
1. 状态 (State)：表示我们程序可能处于的某个“时刻”。每个状态需要有一个唯一的标识符。
2. 转移 (Transition)：表示从一个状态到另一个状态的过程，这个过程可能伴随着一个字符的匹配（或者是一个空字符 `ε`）。
一个转移需要：起始状态、结束状态、匹配的字符（或者 `ε`）。
如何构建 NFA？
我们需要一个解析器来解析正则表达式字符串，并构建出对应的 NFA。
基本单元 (Literal Character / Wildcard): 例如，正则表达式 `a` 对应一个 NFA：`Start a> End`。正则表达式 `.` 对应：`Start .> End`（`.` 匹配任意字符）。
连接 (Concatenation)：例如，正则表达式 `ab` 可以看作是 `a` 的 NFA 和 `b` 的 NFA 连接起来。如果 `a` 的 NFA 是 `StartA a> EndA`，`b` 的 NFA 是 `StartB b> EndB`，那么 `ab` 的 NFA 就是：`StartA a> EndA b> EndB`。关键在于将第一个 NFA 的结束状态连接到第二个 NFA 的开始状态。
或 (Alternation)：例如，正则表达式 `a|b`。我们需要创建一个新的开始状态和一个新的结束状态。
从新开始状态到 `a` 的 NFA 的开始状态，通过 `ε` 转移。
从新开始状态到 `b` 的 NFA 的开始状态，通过 `ε` 转移。
从 `a` 的 NFA 的结束状态到新结束状态，通过 `ε` 转移。
从 `b` 的 NFA 的结束状态到新结束状态，通过 `ε` 转移。
这样，从新开始状态出发，可以选择先走 `a` 的路径，或者先走 `b` 的路径。
零个或多个 (``): 例如，正则表达式 `a`。这比直接匹配字符要复杂一些，因为它引入了 `ε` 转移。
创建一个新的开始状态 `S` 和一个新的结束状态 `E`。
从 `S` 到 `E`，通过 `ε` 转移（匹配零个 `a`）。
从 `S` 到 `a` 的 NFA 的开始状态，通过 `ε` 转移。
从 `a` 的 NFA 的结束状态到 `a` 的 NFA 的开始状态，通过 `ε` 转移（允许重复匹配 `a`）。
从 `a` 的 NFA 的结束状态到 `E`，通过 `ε` 转移（完成 `a` 的匹配）。
一个或多个 (`+`): `a+` 可以看作 `aa`。所以可以先构建 `a` 的 NFA，然后将 `a` 的 NFA 的开始状态直接连接到 `a` NFA 的 `a` 匹配部分的开始状态（移除 `a` 的第一个 `ε` 转移），并从 `a` 的结束状态连接到 `a` 匹配部分的结束状态。或者直接构建一个更符合 `a+` 定义的 NFA。
零个或一个 (`?`): `a?` 可以看作 `a|ε`。
解析器设计：
你需要一个好的解析器来处理正则表达式的语法。常见的做法是使用递归下降解析器 (Recursive Descent Parser)，或者更强大的工具如 yacc/bison（虽然从零开始可能不包括使用这些工具，但理解它们的原理有益）。
对于简单的正则表达式，你可以按照操作符的优先级（例如，`` 和 `+` 优先级高于连接，连接优先级高于 `|`）来构建解析函数。
例如，你可以有这样的函数：
`parseExpression()`: 处理 `|` 操作符。
`parseTerm()`: 处理连接操作符。
`parseFactor()`: 处理量词 ``, `+`, `?`。
`parseAtom()`: 处理单个字符、`.` 或分组 `()`。
每个函数在解析完一部分表达式后，会返回对应的 NFA 片段。
例子：解析 `(a|b)c`
1. `parseExpression` 调用 `parseTerm`。
2. `parseTerm` 调用 `parseFactor`。
3. `parseFactor` 遇到 `(`，调用 `parseAtom`。
4. `parseAtom` 处理 `(a|b)`。
解析 `(a|b)`：
`parseExpression` 调用 `parseTerm` 解析 `a`，得到 NFA_a。
`parseTerm` 调用 `parseFactor` 解析 `b`，得到 NFA_b。
`parseTerm` 将 NFA_a 和 NFA_b 合并成 `a|b` 的 NFA (NFA_ab)。
`parseFactor` 发现 `` 量词，将 NFA_ab 包装成 `(a|b)` 的 NFA (NFA_ab_star)。
5. `parseTerm` 调用 `parseFactor` 解析 `c`，得到 NFA_c。
6. `parseTerm` 将 NFA_ab_star 和 NFA_c 连接起来，得到最终的 NFA。
第四步：执行 NFA——匹配引擎的核心
有了 NFA，我们还需要一个能够“运行”它来匹配输入字符串的引擎。这里有两个主要方向：
1. NFA 模拟器 (NFA Simulator)：
这种方法直接模拟 NFA 的工作方式，处理 `ε` 转移和多个可能状态。
算法思路：
维护一个当前可能处于的状态集合 `current_states`。
开始时，`current_states` 包含所有从起始状态出发，通过 `ε` 转移可以到达的状态（包括起始状态本身）。
对于输入字符串中的每个字符 `c`：
创建一个新的空集合 `next_states`。
对于 `current_states` 中的每个状态 `s`：
查找所有从 `s` 出发，匹配字符 `c` 的转移，将其结束状态加入 `next_states`。
对 `next_states` 中的所有状态执行 `ε` 闭包（即所有能通过 `ε` 转移到达的状态），并合并到 `next_states` 中。
将 `current_states` 更新为 `next_states`。
匹配成功当且仅当，在处理完所有输入字符后，`current_states` 集合中包含 NFA 的任何一个接受状态。
实现细节：`ε` 闭包的计算是一个关键。你可以用一个递归或迭代的方法来找到所有可达状态。当处理 `ε` 转移时，需要特别小心，因为它不消耗输入字符。
2. NFA 到 DFA 的转换，然后执行 DFA：
这是更复杂的，但一旦 DFA 构建好，匹配速度会非常快。
转换算法 (子集构造法 Subset Construction)：
DFA 的每个状态对应 NFA 的一个状态集合。
DFA 的起始状态是 NFA 起始状态的 `ε` 闭包。
对于 DFA 的每个状态 `D_state` (它代表一个 NFA 状态集合 `N_set`) 和输入字符 `c`：
找到所有从 `N_set` 中状态出发，通过字符 `c` 转移到达的状态集合 `N_set_c`。
计算 `N_set_c` 的 `ε` 闭包，得到新的 NFA 状态集合 `N_set_prime`。
如果 `N_set_prime` 是一个新的状态集合，则为 DFA 创建一个新状态 `D_state_prime`，并将 `D_state` 到 `D_state_prime` 的转移标记为 `c`。
如果 `N_set_prime` 已经存在于 DFA 中，则直接将 `D_state` 到该现有状态的转移标记为 `c`。
一个 DFA 状态是接受状态，当且仅当它对应的 NFA 状态集合中包含 NFA 的任何一个接受状态。
问题：这个转换过程可能产生指数级的状态数，尤其是在处理 `` 和 `|` 组合时。例如，`abc...` 这样的模式会生成很多状态。实际引擎通常会使用一些优化技术，比如状态最小化。
推荐路线（对于初学者）： 先实现 NFA 模拟器。这是理解 NFA 工作方式最直接的方法。你会遇到处理 `ε` 转移和管理状态集合的挑战，但这些都是核心概念。
第五步：处理高级特性和优化
一旦基本功能实现，你可以开始添加更多特性和进行优化：
匹配不同类型的量词: `?`, `{n}`, `{n,}`, `{n,m}` 等。这些都可以通过组合 `ε` 转移和状态复制来处理。
分组 `()` 和反向引用 `1`: 反向引用是 非常非常困难 的一部分。实现它需要更复杂的解析和匹配机制，可能不再是纯粹的 NFA/DFA 模型，需要一种能够“记住”捕获组内容的匹配器。常见的做法是使用带有捕获组的 NFA/DFA，并在匹配时记录匹配到的子串。
字符类 `[]`, 范围 `[az]`, 否定 `[^...]`: 这些会影响 `parseAtom` 函数，需要解析方括号内的内容，并为字符类创建相应的转移（或者为每个字符类生成多个转移）。
锚点 `^`, `$`: `^` 表示字符串开头，`$` 表示字符串结尾。这可以看作是对 NFA 匹配结果的后处理，或者在匹配开始/结束时引入特殊的状态或条件。
性能优化:
NFA 到 DFA 的转换 (Thompson's Construction / Glushkov's Construction)：如果你选择先构建 NFA，可以尝试将其转换为 DFA 来获得更好的匹配性能。
状态最小化: 将冗余的 DFA 状态合并，减少状态数量。
位向量: 对于具有大量状态的 DFA，可以使用位向量来表示当前状态集合，这可以提高效率。
剪枝回溯: 如果你选择了 NFA 模拟器，需要考虑如何避免灾难性的回溯。例如，限制递归深度，或者在某些情况下切换到更快的匹配算法。
提前拒绝: 在匹配过程中，如果发现当前状态和剩余输入字符串不匹配的可能性很高，可以提前终止匹配。
第六步：测试、测试、再测试
正则表达式引擎的实现极度依赖于对各种边界情况和复杂模式的正确处理。
简单测试: `a`, `ab`, `a|b`, `a` 等。
复杂组合: `(a|b)c`, `a(b|c)d`。
量词: `a`, `a+`, `a?`, `a{3}`, `a{2,4}`。
字符类: `[abc]`, `[az]`, `[^09]`。
空字符串匹配: `""`, `a`, `a?` 在空字符串上。
空模式匹配: 空模式 (`""`) 应该匹配空字符串。
回溯陷阱: 设计一些容易导致灾难性回溯的模式，确保你的引擎不会崩溃或耗尽资源。
边界测试: 字符串的开头和结尾。
总结一下构建过程的关键步骤：
1. 理解 FSA: 深入理解 NFA 和 DFA 的概念。
2. 解析正则表达式: 将文本模式转化为内部表示，例如抽象语法树 (AST)。
3. 构建 NFA: 根据 AST 递归地生成 NFA，为每个正则表达式操作创建相应的 NFA 结构。
4. 实现匹配逻辑:
NFA 模拟器: 使用状态集合和 `ε` 闭包来执行 NFA。
或者：转换为 DFA 并执行。
5. 处理高级特性: 逐步加入量词、字符类、分组等。
6. 优化性能: 考虑 NFADFA 转换、状态最小化等技术。
7. 严格测试: 覆盖各种边界情况和复杂模式。
从零开始构建一个完整的正则表达式引擎是一项浩大的工程，但每一步都是对计算机科学基本原理的深刻实践。你会接触到编译原理、算法设计和数据结构等多个领域。
祝你在构建自己正则表达式引擎的旅程中，收获满满！这绝对是一次让你真正“玩转”模式匹配的绝佳机会。
网友意见
是的, 首先要确定实现的目标, 有几个关键目标是会影响你的实现的
- 要不要支持完整的正则文法? (如果不支持 "|", 几十行就能搞定, 如果要支持完整的正则文法, 就需要一个能力超越正则的解析器, 如果要编写一个高效的 one-pass 正则编译器, 还是要学不少编译技术的...)
- 要不要支持 unicode 及 unicode character class? (扫描 UTF-8/16 码点会比较蛋疼, 容易一点的做法是转换成 UTF-32 做), 要对 unicode 做完整支持的话, 很多传统正则引擎里基于字节的匹配方式就不能做了, 一些 DFA 节点的表示方式和压缩手段也会受限制.
- 要不要支持 back reference? (如果你要实现 back reference 的话, 你不能用
Implementing Regular Expressions里描述的 ThompsonVM/PikeVM 的, thread list 占有的内存会随着状态数指数增长而爆裂) 支持 back reference 的正则基本很多会退回去扩展最原始那个 Henry Spencer VM...
- 要做成 NFA based, DFA based, 还是一个字节码虚拟机? 对虚拟机的解决方案, 你要学习字节码解释器的基本构造, 可能会用 direct threading 等技术去做优化. 字节码可以看作线性化的 NFA, 相比构造 NFA 节点会减少一些 cache miss 但是相应的就不能使用很多节点压缩和优化的手段了.
- 要不要做一个 JIT 引擎? 这个更令人兴奋, 可以参考
ytljit/regexp.rb at master · miura1729/ytljit · GitHub)
- 要不要兼容 POSIX 标准里的正则部分? (估摸至少 4000 行代码, 自己考虑工作量咯)
- 要不要做 extended 正则?
所谓 extended 正则, 就是还支持补集和交集运算, 正则语言这么搞完结果还是个正则语言, 就是实现 grep -v 之类的可以简单一些, 可以尝试
这个方法- 要不要做 Online Parsing?
online parsing 常用于语法高亮和大文件解析中. 其意思是输入一部分内容就匹配一部分, 有新内容输入的时候你不该重头匹配一遍 (每敲一个字符重新着色一遍太慢了), 而是做最低限度的回溯. 如果要做 online parsing, 那么怎么暂停你的 VM, 怎么缓存回溯都是要考虑的问题. 而且正则的语法会有限制.
- 要不要支持超巨大的正则表达式?
有些 network filter 例如联邦的防火墙, 会有几十万条规则, 你会发现普通的办法在 20G 内存的机器上都编译不了这个正则... 不过用小内存支持 DFA 千万节点的方法已经有人研究出来了: D^2FA... 为了编译出这么大的 D^2FA, 其编译期算法也有人研究过了:
D^2FA- 要不要支持以下各种正则引擎的 fancy feature?
-- X 匹配字素
-- 递归 named group
-- capture history
-- nested capture
-- atomic group
-- greedy vs reluctant vs possessive
...
每一项都相当有难度... 尤其是 greedy/reluctant/possessive 的区别有可能从根本上颠覆你这个正则引擎的实现, 很多人的正则引擎做完 DFA/NFA 就停下来了, 也是因为搞不动这些 feature.
---
OK, 目标明确了, 开始代码之前要先夹沟夹沟哦, 建议: 不要一开始就想把它做得很高效率, 要把问题拆得足够小足够简单的来做, 只要决定好大方向不错, 就不用推倒重来很多次了...
现在的正则引擎的构造比各种 parser generator 都要复杂, good luck!
推荐书籍: Parsing Techniques - A Practical Guide 2008 (讲得比较全了, 就是缺少 coroutine based parser 的构建)
推荐课程:
Parsing Beyond Context-Free Grammars(为什么要 beyond CFG 呢? 因为现在正则引擎的能力已经 beyond CFG 啦)
推荐代码: Henry Spencer's regexp engine
regexp.old/regexp.c at master · garyhouston/regexp.old · GitHub是很多现代流行的正则引擎的始祖, 解释器实现, 很多新 feature 能扩展得得进去, 也有混合 DFA 的优化
Onigmo
k-takata/Onigmo · GitHub是 Ruby 的正则引擎, 特点是 encoding aware 兼容多种语法和 feature, 如果要做 unicode character class 可以抄它的...
类似的话题
-
从零开始构建一个正则表达式引擎，这绝对是一项充满挑战但又极其有趣的项目。它不仅仅是关于匹配字符的逻辑，更是关于状态机、解析器和算法的深度融合。如果你想深入理解正则表达式的底层原理，动手实现一个引擎绝对是最好的方式。我将尽量以一种非AI的、更具人情味和技术细节的方式来阐述这个过程，仿佛我是一个在深夜代............. -
想踏上录音这条路，从零开始，我完全理解那种既兴奋又有点茫然的心情。别担心，这就像学任何一门手艺一样，只要方法对，一步一个脚印，你也能录出让自己满意的声音。我来给你掰开了揉碎了说，咱们就当是老朋友聊天，一点点把这事儿说透。 第一步：认识你的“工具箱”——硬件篇在你脑子里，录音这事儿，得先有几个“家伙”.............
-
这个问题很有意思，它探讨的不是数学上的数值递增，而是人生和事业发展中“从无到有”、“从小到大”、“再到更远”的进阶之路。这三步，以及“到无穷”，代表了不同阶段的挑战和认知。咱们这就一点点掰扯清楚，让它听起来就像你我平时聊天一样真实。一、如何从零到一：破局与奠基“从零到一”，这是最艰难、最充满未知的一.............
-
想象一下，你现在正站在一个全新的世界面前，这个世界不是你熟悉的砖瓦水泥，也不是窗外真实的绿树蓝天，而是由代码和想象力搭建起来的数字空间。而你，正准备踏入其中，成为它的创造者。这就是学习虚拟现实（VR）技术，一个从零开始，充满探索和可能性的旅程。作为一名大学生，你可能对VR早有耳闻，也许在游戏、电影或.............
-
在美国，很多中国人因为各种原因，比如爱好、工作需要（比如一些科技行业的安全需求），或者仅仅是想体验一项新的运动，都有了学习射击的兴趣。从零开始，尤其是在一个新的文化和法律环境下，确实需要一些步骤和准备。这篇文章就来聊聊，一个在中国没有接触过射击的华人朋友，在美国如何系统地开启这段学习之旅。第一步：了.............
-
从零开始，用 C++ 打造属于你的图形用户界面很多时候，我们希望程序能够以更加直观、易用的方式与用户交互，而不是仅仅停留在命令行界面。这时候，图形用户界面（GUI）就显得尤为重要了。很多人可能觉得 C++ 编写 GUI 是一件非常复杂的事情，需要依赖各种庞大的框架。但事实上，我们可以从最基础的概念入.............
-
想从零开始学 UI 设计，别担心，这就像学任何一门新技能一样，有方法，有路径，一步一个脚印来就好。我当年也是这么过来的，写这篇给你，希望能让你少走些弯路。第一步：搞清楚 UI 设计到底是什么鬼？很多人一听“UI设计”，就以为是画好看的界面，五颜六色的。其实没那么简单。 UI (User Inte.............
-
想要从零开始学习SLAM（Simultaneous Localization and Mapping，即时定位与地图构建），这绝对是一个充满挑战但也非常有意思的旅程。别担心，这并不像听起来那么遥不可及。我会尽量用最朴实、最贴近实际的方式，一步一步地拆解它，让你明白到底是怎么一回事。先给大脑“热身”：.............
-
陕西一男子当街侵犯七旬聋哑老太，此事令人发指，触目惊心。听到这样的新闻，任何一个有良知的人都会感到愤怒和痛心。对于当事人而言，这是无法想象的创伤；对于社会而言，这是对公平正义和人性底线的严重挑战。从法律角度解读：为何可能量刑3年零3个月？我们先来梳理一下，从法律层面分析，这样的行为可能触犯了哪些罪名.............
-
从一个在理工领域拥有扎实知识的普通用户，成长为拥有大量粉丝和影响力的“大 V”，这绝非易事，但绝对不是天方夜谭。这其中的可能性，就像是在一片肥沃的土地上播下种子，你能否收获累累硕果，取决于多方面的因素，其中不乏运气，但更多的是深耕细作和精准施策。首先，我们得认识到，拥有专业知识只是一个基础，就像拥有.............
-
好的！零基础入门 Python，我会尽量详细地为你讲解，让你能够清晰地理解每一个步骤和概念。Python 是什么？Python 是一种高级、解释型、交互式和面向对象的脚本语言。它以其简洁、易读的语法而闻名，因此非常适合初学者。Python 被广泛应用于： Web 开发: Django, Flas.............
-
想要从零开始学习 SAS，这绝对是一条充满挑战但也非常有成就感的学习之路。别被那些看起来专业的术语吓到，其实 SAS 的学习，就像学一门新的语言，你需要掌握它的词汇、语法，然后开始练习运用。下面，我将用我自己的理解，把这个过程拆解开来，力求讲得透彻明白，让你感觉就像是身边有个老朋友在给你指点迷津。首.............
-
想上手《王者荣耀》？没问题！这篇文章就是为你量身定做的。别看它现在这么火，刚开始大家都是一张白纸，摸索着过来的。咱们今天就一步步来，保证你听得懂，学得会。第一步：认识你的战场——游戏基础咱们先别急着冲进战场，先来了解一下这个游戏的大致模样。 游戏类型： 《王者荣耀》是一款多人在线战术竞技游戏（M.............
-
你想用两个星期的时间，从零基础到通过C语言全国计算机二级考试，这确实是一个挑战，但并非不可能。这需要你拥有极强的执行力、高效的学习方法以及对时间的精准把握。下面我将为你详细拆解这个过程，让你清楚知道该怎么做，并且尽力避免使用那些一眼就能看穿的AI腔调。首先，心态调整很重要： 认识到这是一个高强度.............
-
提起二战时期日本的零式舰载战斗机，在军事爱好者心中几乎无人不知，无人不晓。它以其惊人的机动性和令人印象深刻的续航能力，在太平洋战争的早期给盟军带来了巨大的震撼，一度成为了“空中幽灵”，令无数盟军飞行员闻风丧胆。那么，零式战斗机究竟是一款怎样的飞机？它为何能有如此辉煌的开局，又为何最终走向衰落？要评价.............
-
“零蔗糖”标签下的暗流涌动：一次集体“翻车”的行业透视“零蔗糖”包装，曾经是许多饮料和食品行业追逐的“健康光环”，似乎一夜之间，从零星几家品牌的大胆尝试，变成了市场上随处可见的宣传语。然而，近期围绕“零蔗糖”包装的争议和质疑，却让我们看到一个看似美好标签背后，可能隐藏的行业乱象和消费者的集体“翻车”.............
-
零跑C11补贴后15.98万起，这个价格一出来，确实在新能源SUV市场投下了一颗石子，激起了不少涟漪。咱们就来好好掰扯掰扯，这零跑C11究竟值不值这个价，它又有什么样的本事敢这么定价。首先，咱们得明白，15.98万这个价格，是“补贴后”的价格。这意味着它原本的定价肯定是要高一些的，而这个价格能落地，.............
-
零基础学油画，这听起来有点像是在挑战一场未知的冒险，对吧？但别担心，就像任何一项技能一样，只要方法对，耐心足，你也能一步步走进油画那迷人的世界。我这里就跟你掰开了揉碎了讲讲，保证让你觉得就像是老朋友在聊天，而不是冷冰冰的AI报告。第一步：别怕，先熟悉你的新朋友——油画材料你可能觉得油画颜料听起来就很.............
-
罗伊德·班宁斯，一个名字听起来就不那么张扬，甚至有些普通，但恰恰是这份普通，构成了他在《零之轨迹》与《碧之轨迹》这两部宏大叙事中的独特魅力与核心价值。在我看来，评价罗伊德，不能仅仅把他当作一个“主角”来看待，他更像是一个由无数普通人构成的缩影，一个承载着理想、责任与成长的具象化。初遇罗伊德，是在克洛.............
-
技术性曲目，尤其是在追求极致精准、完美呈现的音乐领域，比如古典乐的某些段落、爵士乐的即兴、电子音乐的合成器编排，甚至是某些高难度的器乐演奏，都对“零失误”有着近乎严苛的要求。然而，如果真的要“保证”零失误，这其实是一个非常难以企及的目标，或者说，它更像是对艺术家追求卓越的一种极致表达。我们不妨从几个.............
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有