5

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

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

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

“同样，我们通过向模拟器添加带有特殊指令的 epsilon 转换来管理这一点。如果断言通过，则状态指针继续，否则将被丢弃。”

然而，我不太明白这意味着什么。是否暗示它只能通过查看其端点的特殊类型的 epsilon 转换来完成，并且只有在其端点满足断言时才能被遍历，还是可以通过以某种方式配置的“正常”epsilon 转换来完成？如果我需要这些“特殊”类型的 epsilon 转换，那么如何确定这些（即转换为标准 DFA）？

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

4

1 回答 1

1

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

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

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

于 2012-04-19T10:52:01.940 回答