regex_search failes (exception: Memory exhausted)

[anonymous]

Sorry for using Japanese. In this code, boost::regex_search() failes and throws Exception(Memory exhausted). I tried both VC++7.1/VC++8.0.

I remember boost 1.33, 1.34, 1.35 gave the same result, but I don't know why.

I think, using back-reference and relatively long input line tends to result in this kind of failure.

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

int main()
{
	boost::wregex re(L"(.+)［＃「\\1」に傍点］");

	std::wstring s =
	L"　女はやがて帰って来た［＃「帰って来た」は底本では「帰った来た」］。"
	L"今度は正面が見えた。三四郎の弁当はもうしまいがけである。"
	L"下を向いて一生懸命に箸《はし》を突っ込んで二口三口ほおばったが、"
	L"女は、どうもまだ元の席へ帰らないらしい。"
	L"もしやと思って、ひょいと目を上げて見るとやっぱり正面に立っていた。"
	L"しかし三四郎が目を上げると同時に女は動きだした。"
	L"ただ三四郎の横を通って、自分の座へ帰るべきところを、すぐと前へ来て、"
	L"からだを横へ向けて、窓から首を出して、静かに外をながめだした。"
	L"風が強くあたって、鬢《びん》がふわふわするところが三四郎の目にはいった。"
	L"この時三四郎はからになった弁当の折《おり》を力いっぱいに窓からほうり出した。"
	L"女の窓と三四郎の窓は一軒おきの隣であった。"
	L"風に逆らってなげた折の蓋《ふた》が白く舞いもどったように見えた時、"
	L"三四郎はとんだことをしたのかと気がついて、ふと女の顔を見た。"
	L"顔はあいにく列車の外に出ていた。"
	L"けれども、女は静かに首を引っ込めて更紗《さらさ》のハンケチで"
	L"額のところを丁寧にふき始めた。"
	L"三四郎はともかくもあやまるほうが安全だと考えた。"
	L"「ごめんなさい」と言った。";

	try {
		boost::wsmatch what;
		boost::regex_search(s, what, re);
	} catch (const std::exception& ex) {
		std::cerr << "Caught exception: " << ex.what() << std::endl;
	}
	return 0;
}

[John Maddock]

The problem here is that matching a back-reference is an NP-complete problem - Boost.Regex has a built in limiter that causes it to throw an exception rather than go on trying to find a match "for ever". Other engines just carry on regardless - so while they may find a match in this particular case (eventually), with a bit more text they might equally well hang the machine. In short, there ain't no good solution except to rewrite your regular expression :-( Can't help much there as I can't tell what you're trying to do from the Japanese.

HTH, John.