Re: [Boost-bugs] [Boost C++ Libraries] #2934: exception generated by regex_search

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #2934: exception generated by regex_search
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-04-11 08:33:18

#2934: exception generated by regex_search
-----------------------------------------+----------------------------------
  Reporter:  patidarsantosh2k_at_[hidden]  |       Owner:  johnmaddock
      Type:  Bugs                        |      Status:  closed     
 Milestone:  Boost 1.39.0                |   Component:  regex      
   Version:  Boost 1.38.0                |    Severity:  Problem    
Resolution:  wontfix                     |    Keywords:             
-----------------------------------------+----------------------------------
Changes (by anonymous):

  * status:  new => closed
  * resolution:  => wontfix

Comment:

 The basic problem here is that Perl regular expression matching is NP-
 complete in the worst case, in order to prevent Boost.Regex consuming an
 inordinate amount of time in the "bad" cases it throws an exception when
 the number of states visited grows too large.

 The solution is generally to try and improve the regular expression to
 reduce the amount of backtracking going on - either by using the Perl-
 style (?>...) construct to "atomically" match a partial regex with no
 backtracking, or by replacing ".*" with something more specific - for
 example should ".*e" really be "[^e]*e" ?  Or something else?

 HTH, John.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/2934#comment:2>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.