12

我目前正在研究正则表达式的问题，当与某个输入匹配时，它可能最终会在指数时间内运行，例如(a*)*，当与字符串 aaaaab 匹配时(a|a)*可能会出现“灾难性回溯” - 对于每个额外的“a”在匹配的字符串，尝试匹配字符串所需的时间加倍。仅当引擎使用回溯/NFA 方法尝试在失败之前尝试树中所有可能的分支时才会出现这种情况，例如 PCRE 中使用的方法。

我的问题是，为什么不(a?)*脆弱？根据我对回溯的理解，字符串 "aaaab" 中应该发生的事情本质上是(a|a)*. 如果我们使用标准的 Thomspson NFA 构造来构造 NFA，那么对于发生的每个 epsilon 转换，引擎肯定必须继续采用它们并以与两个 a 的情况相同的方式回溯？例如（省略一些步骤以及 @ 替换 epsilon 的位置）：

"aaaa" 匹配，但不能匹配 'b'，失败（回溯）
"aaaa@" 匹配，'b' 失败（回溯）
"aaa@a" 匹配，'b' 失败（回溯）
"aaa@a@ " 匹配，'b' 失败（回溯）
...
"@a@a@a@a@" 匹配，'b' 失败（回溯）

尝试所有可能的 epsilons 和 a 组合，肯定会导致路由的指数级爆炸？

从 NFA 中删除 epsilon 转换是有意义的，但我相信这具有从(a*)*模式中删除所有非确定性的效果。不过，这绝对是脆弱的，所以我不完全确定发生了什么！

非常感谢您！

编辑： Qtax 已经指出，当使用传统回溯遍历 NFA 时，epsilons 不能仍然存在，否则(@)*将尝试永远匹配。那么，什么样的 NFA 实施可能会导致指数级增长，而(a*)*不是这样呢？这确实是问题的症结所在。(a|a)*(a?)*

4

1 回答 1

4

好的，经过一番调查，我最终发现这是由于在 NFA 实现中使用了“障碍”。简而言之，障碍被放置在 NFA 中的战略点（例如在 NFA 构造 a* 中的“a”转换之后的节点上）。他们要求比赛从上一次击中障碍时开始。这可以防止 NFA 陷入与无限数量的 epsilon 匹配的情况并允许它终止。

换句话说，不可能从一个障碍到仅匹配电子移动的同一障碍 - 如果发生这种情况，路线将被丢弃并从前一点开始回溯。这还有一个副作用，即 (a?)* 不容易受到指数爆炸的影响，因为 a? 第二次无法匹配 null 。

于 2012-08-28T16:58:47.003 回答