#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;
}
dies erzeugt:
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.
kompiliert mit
g++ regex.cc -lboost_regex
BEARBEITEN
meine Plattform:
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
Antworten:
((\\w+)(::)?)+ ist einer der sogenannten "pathologischen" regulären Ausdrücke -- es dauert exponentiell, weil Sie zwei Ausdrücke haben, die direkt nacheinander voneinander abhängig sind. Das heißt, es scheitert an katastrophalem Backtracking.
Überlegen Sie, ob wir dem Beispiel des Links folgen und "etwas Komplizierteres" auf "x" reduzieren. Machen wir das mit \\w :
((x+)(::)?)+
Nehmen wir außerdem an, dass unsere Eingabe niemals :: haben wird . Dadurch wird die Regex tatsächlich komplexer. Wenn wir also die Komplexität wegwerfen, sollten wir die Dinge wirklich einfacher machen, wenn nichts anderes:
(x+)+
Jetzt haben Sie ein Lehrbuch-Problem mit verschachtelten Quantoren, wie es im obigen Link beschrieben wird.
Es gibt ein paar Möglichkeiten, dies zu beheben, aber der einfachste Weg ist wahrscheinlich, das Zurückverfolgen der inneren Übereinstimmung mit dem atomaren Gruppenmodifikator "(?>" zu verbieten ":
((?>\\w+)(::)?)+
Einige Code-Antworten
#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 ->
./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