Почему boost rege исчерпал пространство стека? - PullRequest
Новая
       13

Почему boost rege исчерпал пространство стека?

7 голосов
/ 21 декабря 2010 
#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

EDIT

моя платформа: 

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

Ответы [ 2 ]

13 голосов
/ 21 декабря 2010

((\\w+)(::)?)+ является одним из так называемых «патологических» регулярных выражений - оно займет экспоненциальное время, потому что у вас есть два выражения, которые зависят друг от друга одно за другим.То есть, он терпит неудачу из-за катастрофического возврата .

. Подумайте, если мы последуем примеру ссылки, и уменьшим «что-то более сложное» до «x».Давайте сделаем это с \\w:

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

Давайте также предположим, что на нашем входе никогда не будет ::.Наличие этого на самом деле делает регулярное выражение более сложным, поэтому, если мы отбрасываем сложность, то нам действительно следует упростить ситуацию, если ничего больше:

  • (x+)+

Теперь выВозникла проблема с вложенным квантификатором из учебника, как подробно описано в ссылке выше.

Есть несколько способов исправить это, но самый простой способ - просто запретить возврат к внутреннему совпадению с использованием атомарного Модификатор группы"(?>":

  • ((?>\\w+)(::)?)+
1 голос
/ 21 декабря 2010

Протестировал его локально, и он работал нормально, я думаю, ваш компилятор делает что-то странное.

Какая версия 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
...