use*_*384 5 java regex word-boundary dfa regular-language
我想在基于 DFA 的正则表达式匹配器中实现“词边界”匹配。有人能告诉我这是怎么做的吗？
提供一些背景知识，我目前正在使用“dk.brics.automaton”库，但它不支持断言（例如\b，词边界）。我需要使用基于 DFA 的引擎，因为我的主要目标实际上是确定正则表达式的等效性，而不是进行实际匹配。
此外，以下问题的答案似乎表明这是可能的： 基于 DFA 的正则表达式匹配 - 如何获取所有匹配？ 说
“同样，我们通过向模拟器添加带有特殊指令的 epsilon 转换来管理它。如果断言通过，则状态指针继续，否则将被丢弃。”
然而，我不太明白这意味着什么。它是否暗示它只能使用一种特殊类型的 epsilon 转换来完成，该类型查看其端点并且只有在其端点满足断言时才能遍历，或者可以使用以某种方式配置的“正常”epsilon 转换来完成？如果我需要这些“特殊”类型的 epsilon 转换，那么如何确定这些转换（即转换为标准 DFA）？
非常感谢有关如何实际实现这一点的任何描述的指针。
您无法使用纯 DFA 实现来执行环视类型正则表达式引擎。由于您需要跟踪以前看到的内容，因此您正在将引擎变成一个不同的野兽，它将上下文保留在内存中以便进行模式匹配。
对于正则表达式引擎来说，处理这个问题意味着它需要有特殊的转换来查看已解析内容的上下文。普通的 DFA 无法做到这一点，因为这个上下文被丢弃了。顺便说一句，这也是为什么捕获组很慢以及为什么匹配(.*)something(.*)在某些引擎上非常慢的原因，因为它会将大量字符复制到缓冲区中以保留此上下文。
我想您将尝试最小化两个生成的 DFA，并查看它们是否相等以解决您的问题。如果在执行状态最小化算法时将每个“特殊”转换处理为唯一的并且只能与等于其自身的转换合并，则这可能仍然是可以实现的。