Jar*_*mex 9 regex theory pcre finite-automata backtracking
我目前正在研究正则表达式的问题,当与某个输入匹配时,它可能最终在指数时间内运行,例如两者(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?)*不是如此？这真的是问题的症结所在.
好吧，经过一番调查后，我最终发现这归因于 NFA 实现中“障碍”的使用。简而言之，障碍被放置在 NFA 中的战略点上（例如在 a* 的 NFA 构造中紧接在“a”转换之后的节点上）。他们要求比赛从上次击中障碍开始继续进行。这可以防止 NFA 陷入匹配无限数量 epsilon 的情况并允许其终止。
换句话说，不可能从一个障碍物到仅匹配电子移动的同一障碍物 - 如果发生这种情况，路线将被丢弃并从前一点发生回溯。这还有一个副作用，即 (a?)* 不容易受到指数爆炸的影响，因为 a? 第二次无法匹配 null。