可以编写一个在某些情况下需要指数运行时间的正则表达式.这样的例子是(aa|aa)*.如果输入奇数个as,则需要指数运行时间.
这很容易测试.如果输入仅包含as并且长度为51,则正则表达式需要几秒钟才能计算(在我的机器上).相反,如果输入长度为52,则其计算时间不明显(我使用JavaRE的内置Regex-parser对其进行了测试).
我写了一个正则表达式解析器来找到这种行为的原因,但我没有找到它.我的解析器可以基于正则表达式构建AST或NFA.之后,它可以将NFA翻译为DFA.为此,它使用了powerset构造算法.
当我解析上面提到的Rgex时,解析器会创建一个具有7种状态的NFA - 转换后,DFA中只剩下3个状态.DFA代表更明智的正则表达式(aa)*,可以非常快速地解析.
因此,我不明白为什么有解析器可以这么慢.这是什么原因？他们不会将NFA翻译成DFA吗？如果是的话,为什么不呢？他们计算得如此之慢的技术原因是什么？
我不确定我是否完全理解以下正则表达式搜索的内容:
>>> import re
>>> template = re.compile("(\w+)+\.")
>>> target = "a" * 30
>>> template.search(target)
search()呼叫需要几分钟才能完成,CPU使用率达到100%.对于2.7.5和3.3.3 Python版本,该行为都是可重现的.
有趣的事实是,如果字符串的长度小于20-25个字符,那么很快就会search()返回.
怎么了？
我有一个字符串，其中有带双引号的部分。我试图用单引号替换所有双引号，除了那些有转义的双引号 ie: \"。
我正在尝试构建一个与所有匹配的正则表达式，"除了像\"
所以当我使用时，preg_replace我会得到如下。
"love" -> 'love'
"John said \"HI\"" - > 'John said \"HI\"'
我尝试了以下完全相反的方法。
[<^\\]"