7 
#include <boost/regex.hpp>
#include <string>
#include <iostream>

using namespace boost;
static const regex regexp(
        "std::vector<"
            "(std::map<"
                   "(std::pair<((\\w+)(::)?)+, (\\w+)>,?)+"
             ">,?)+"
        ">");

std::string errorMsg =
"std::vector<"
        "std::map<"
                "std::pair<Test::Test, int>,"
                "std::pair<Test::Test, int>,"
                "std::pair<Test::Test, int>"
        ">,"
        "std::map<"
                "std::pair<Test::Test, int>,"
                "std::pair<Test::Test, int>,"
                "std::pair<Test::Test, int>"
        ">"
">";
int main()
{
    smatch result;
    if(regex_match(errorMsg, result, regexp))
    {  
        for (unsigned i = 0; i < result.size(); ++i)
        {  
            std::cout << result[i] << std::endl;
        }
    }

//    std::cout << errorMsg << std::endl;

    return 0;
}

これにより、次が生成されます。

terminate called after throwing an instance of 'boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<std::runtime_error>
>'   what():  Ran out of stack space trying to match the regular expression.

でコンパイル

g++ regex.cc -lboost_regex

編集

私のプラットフォーム:

g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
libboost-regex1.42
Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz
So the latest Ubuntu 64 bit
4

2 に答える 2

13

((\\w+)(::)?)+は、いわゆる「病理学的」正規表現の 1 つです。2 つの式が次々と依存しているため、指数関数的な時間がかかります。つまり、壊滅的なバックトラッキングが原因で失敗します。

リンクの例に従うかどうかを検討し、「より複雑なもの」を「x」に減らします。でそれをしましょう\\w：

  • ((x+)(::)?)+

また、入力が になることはないと仮定しましょう::。これを実際に使用すると、正規表現がより複雑になります。したがって、複雑さを捨てると、他に何もなくても、物事をより単純にする必要があります。

  • (x+)+

これで、上記のリンクで詳しく説明されているような、教科書のネストされた量指定子の問題が発生しました。

これを修正する方法はいくつかありますが、おそらく最も簡単な方法は、アトミック グループ修飾子" (?>" を使用して内部一致でバックトラッキングを禁止することです。

  • ((?>\\w+)(::)?)+
于 2010-12-21T02:19:51.373 に答える
1

ローカルでテストしたところ、問題なく動作しました。コンパイラが奇妙なことをしていると思います。

gccのバージョンは？何のプラットフォーム？ブーストのどのバージョン？

 -> ./regex
std::vector<std::map<std::pair<Test::Test, int>,std::pair<Test::Test, int>,std::pair<Test::Test, int>>,std::map<std::pair<Test::Test, int>,std::pair<Test::Test, int>,std::pair<Test::Test, int>>>
std::map<std::pair<Test::Test, int>,std::pair<Test::Test, int>,std::pair<Test::Test, int>>
std::pair<Test::Test, int>
Test
Test
::
int
于 2010-12-21T02:18:47.993 に答える