c++ - 为什么 regex_match 抛出 "complexity exception"？

Question

我正在尝试测试(使用 boost::regex)文件中的一行是否仅包含由空格分隔的数字条目。我遇到了一个我不明白的异常(见下文)。如果有人能解释为什么抛出它，那就太好了。也许我在这里以定义模式的方式做了一些愚蠢的事情？这是代码:

// regex_test.cpp
#include <string>
#include <iostream>
#include <boost/regex.hpp>
using namespace std;
using namespace boost;

int main(){
  // My basic pattern to test for a single numeric expression
  const string numeric_value_pattern = "(?:-|\\+)?[[:d:]]+\\.?[[:d:]]*";
  // pattern for the full line
  const string numeric_sequence_pattern = "([[:s:]]*"+numeric_value_pattern+"[[:s:]]*)+";

  regex r(numeric_sequence_pattern);
  string line= "1 2 3 4.444444444444";
  bool match = regex_match(line, r);
  cout<<match<<endl;

  //...
}

我编译成功了

g++ -std=c++11 -L/usr/lib64/ -lboost_regex regex_test.cpp  

生成的程序到目前为止运行良好，match == true 如我所愿。但后来我测试了一条输入线，比如

string line= "1 2 3 4.44444444e-16"; 

当然，我的模式不是为了识别格式 4.44444444e-16 而构建的，我希望 match == false。但是，我收到以下运行时错误:

terminate called after throwing an instance of  
'boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<std::runtime_error> >'  
  what():  The complexity of matching the regular expression exceeded predefined bounds.  
Try refactoring the regular expression to make each choice made by the state machine unambiguous.  
This exception is thrown to prevent "eternal" matches that take an indefinite period time to locate.  

这是为什么？
注意:我给出的例子是极端的，因为在点之后少放一位数字就可以了。这意味着

string line= "1 2 3 4.4444444e-16";

只是导致 match == false 符合预期。所以，我很困惑。这里发生了什么？

已经谢谢了!

---

更新:
问题似乎解决了。鉴于 alejrb 的提示我将模式重构为

const string numeric_value_pattern = "(?:-|\\+)?[[:d:]]+(?:\\.[[:d:]]*)?";  

这似乎可以正常工作。不知何故，原始模式 [[:d:]]+\\.?[[:d:]]* 中的孤立可选 \\. 留下了许多可能性以不同的方式匹配一长串数字。
我希望模式现在是安全的。但是，如果有人找到使用它以新形式进行爆炸的方法，请告诉我!对我来说这是否仍然可能不是那么明显...

Answer 1

我会说您的正则表达式可能呈指数回溯。为了保护您免受输入时间过长将变得完全无法运行的循环，正则表达式引擎只是中止尝试。

经常导致此问题的模式之一是任何形式的 (x+x+)+ - 当您将第一个模式放在第二个模式中时，您会在此处构建。

http://www.regular-expressions.info/catastrophic.html 上有很好的讨论