我目前正在研究正则表达式的问题,当与某个输入匹配时,它可能最终在指数时间内运行,例如两者(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?)*不是如此？这真的是问题的症结所在.
好吧,我正在尝试创建一个函数来确定元组列表是否是可传递的,即如果(x,y)和(y,z)在列表中,那么(x,z)也在列表中.
例如,[(1,2), (2,3), (1,3)]是传递性的.
现在,来自Prolog背景,以下内容对我有意义:
transitive xs = and [elem (x, z) xs | (x, y) <- xs , (y, z) <- xs ]
但是,它不起作用.似乎'y'没有像我预期的那样获得单个值,但是当涉及到第二个元组时,它被'重新分配'.相反,我们必须使用:
transitive xs = and [elem (x, z) xs | (x, y1) <- xs , (y2, z) <- xs, y1 == y2 ]
为什么会这样？为什么第一个例子不会导致错误,这是否违背了函数式编程语言的"引用透明度"原则？
"但是,在纯函数和逻辑语言中,由于引用透明性的要求,变量被绑定到表达式并在其整个生命周期中保持单个值." - 维基百科
谢谢!
我目前在使用EasyMock进行单元测试时遇到问题。
Expectation failure on verify:
FileConverter.convert(file, file2): expected: 1, actual: 1
这是该类中唯一的失败，并且在下面的verify方法上失败。我已经尝试过搜索该消息，但是这只会显示“ expected：1，actual：1 （+1） ”的结果，而+1表示错误有所不同。
我试图简化失败的EasyMock测试的结构以进行演示。请原谅任何错别字：
@Test
public void testScan() {
String[] testFiles = { "file", "file2" };
FileConverter converterMock = EasyMock.createMock(FileConverter.class);
Poller poller = new Poller(new File("testFolder"), converterMock);
for (String testFile : testFiles) {
converterMock.convert(new File(testFile));
EasyMock.expectLastCall().once();
}
EasyMock.replay(converterMock);
for (String testFile : testFiles) {
poller.scan();
}
EasyMock.verify(converterMock);
}
我认为代码本身并不特别相关，但是出于完整性考虑，我将其包括在内-我真正想要的是解释EasyMock.verify方法的上下文中“预期1，实际1”的含义。
提前致谢！