java - 如何使用 DFA 正则表达式匹配器实现正则表达式断言/环视(即\b 样式词边界)

Question

我想在基于 DFA 的正则表达式匹配器中实现“词边界”匹配。谁能告诉我这是怎么做到的？

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

此外，以下问题的答案似乎表明这是可能的: DFA based regular expression matching - how to get all matches?通过说

"Again, we manage this by adding an epsilon transition with special instructions to the simulator. If the assertion passes, then the state pointer continues, otherwise it is discarded."

不过，我不太明白这是什么意思。这是否表明它只能通过一种特殊类型的 epsilon 转换来完成，这种转换会查看其端点，并且只有在其端点满足断言时才能遍历，或者它是否可以通过以某种方式配置的“正常”epsilon 转换来完成？如果我需要这些“特殊”类型的 epsilon 转换，那么如何确定它们(即转换为标准 DFA)？

非常感谢任何关于如何实际实现它的描述的指针。

Answer 1

您不能使用纯 DFA 实现来执行环视类型的正则表达式引擎。由于您需要跟踪之前看到的内容，因此您正在将引擎变成一个不同的野兽，它将上下文保存在内存中以便进行模式匹配。

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

我假设您将尝试最小化两个生成的 DFA 并查看它们是否相等，以便解决您的问题。如果您在执行状态最小化算法时将每个“特殊”转换处理为唯一且只能与与其自身相等的转换合并，则这仍然可以实现。