Boost logo

Boost Users :

Subject: Re: [Boost-users] boost::xpressive - Regex stack space exhausted
From: OvermindDL1 (overminddl1_at_[hidden])
Date: 2010-07-22 05:40:52


On Thu, Jul 22, 2010 at 3:29 AM, Pavol Supa <pavol.supa_at_[hidden]> wrote:
> On Wed, Jul 21, 2010 at 10:52 PM, Eric Niebler <eric_at_[hidden]> wrote:
>> On 7/21/2010 2:39 PM, Pavol Supa wrote:
>>> Hi,
>>>
>>> I need to match a hex-written byte array, optionally separated with
>>> spaces. So i tried:
>>>
>>> boost::xpressive::sregex r = * ( * blank >> repeat<2,2> (xdigit));
>>> smatch match;
>>> regex_match (input, match, r);
>>>
>>> when i use input of approx. 150 hex pairs, i get an exception "Regex
>>> stack space exhausted" (i use default stack size by Visual studio
>>> 2008)
>>>
>>> This pattern looks quite simple, so I'd like to know, if there is some
>>> fundamental problem with this expressions.
>>
>> Yes. See
>> http://www.boost.org/doc/libs/1_43_0/doc/html/xpressive/user_s_guide.html#boost_xpressive.user_s_guide.tips_n_tricks.beware_nested_quantifiers
>>
>> Not only will this pattern tear through stack, it'll run very slowly.
>> Try this instead:
>>
>> * ( keep(*blank) >> repeat<2,2> (xdigit))
>
> So, i tried it. It throws exceptions at ~230 hexdigit pairs.
> I played with "keep"s, the only 'better' combination is
>
> * keep ( (*blank) >> repeat<2,2> (xdigit))
>
> which throws when input has 300 pairs

If you were using Boost.Spirit.Qi, then it should 'just work', that
rule in Boost.Spirit.Qi for a simple match like the above Regex
version is would be:
  boost::spirit::qi::rule<Iterator, boost::spirit::blank_type> r =
*lexeme[xdigit >> xdigit];

It can also parse and stuff it all into a string, a vector, or
whatever, as characters or parse it into integers/shorts/whatever,
basically any parsing need can be easily fulfilled, you really should
try Boost.Spirit.Qi.


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net