如何使用DFA正则表达式匹配器实现正则表达式断言/环视（例如\b样式单词边界）

Question

我想在基于DFA的正则表达式匹配器中实现“单词边界”匹配。有人能告诉我如何做吗？

为了提供一些背景，我目前正在使用 "dk.brics.automaton" 库，但它不支持断言（例如\b，单词边界）。我需要使用基于DFA的引擎，因为我的主要目标实际上是确定正则表达式的等价性，而不是执行实际的匹配。

此外，下面这个问题的答案似乎表明这是可能的：基于DFA的正则表达式匹配 - 如何获取所有匹配项？，其中说:

"同样，我们通过添加具有特殊指令的 epsilon 转换到模拟器来管理此过程。如果断言通过，则状态指针继续，否则将被丢弃。"

然而，我无法完全理解这是什么意思。 它是否建议只能使用一种特殊类型的 epsilon 转换来查看其端点并且只能在其端点满足断言时遍历它，或者可以通过某种方式配置“正常”的 epsilon 转换来完成？ 如果我需要这些“特殊”类型的 epsilon 转换，那么如何对其进行确定化（即转换为标准 DFA）？

非常感谢任何有关如何实际实现这一点的说明。

- user1255384

---

这只是意味着有一些任意的代码被 epsilon 转换触发，如果前一个字符和当前字符不符合 \b 的条件，则会失败。因此，您需要在某个地方保留“前一个字符”。 - andrew cooke

Answer 1

使用纯DFA实现无法执行lookaround类型的正则表达式引擎。由于您需要跟踪以前看到过的内容，因此您正在将引擎转变为一种在内存中保留上下文以进行模式匹配的不同类型的引擎。

对于正则表达式引擎来处理这种情况，意味着它需要具有特殊的转换来查看已解析的上下文。普通的DFA无法做到这一点，因为这个上下文被抛弃了。顺便说一下，这也是捕获组缓慢的原因，以及为什么在某些引擎上匹配(.*)something(.*)非常缓慢，因为它会将大量字符复制到缓冲区中以保持这个上下文。

我想你要尝试最小化两个结果DFAs，并查看它们是否相等，以解决你的问题。如果您在状态最小化算法中将每个“特殊”转换处理为唯一的并且只能与等于其自身的转换合并，则可能仍然可以实现这一点。

- Dervall