Re: Hanging regex

On Sat, 2012-11-17 at 12:05 +0000, Ihe Onwuka wrote:
> First let me dissect the regex
> 
> 	   <xsl:analyze-string select="." flags="x"
> 			       regex="(.+?)
> 			              ((-?\d*\s*)+$)"

Whenever you have a repeatable part in your regular expression that can
match the empty string, your regular expression processor takes one more
step down the staircase to the undocumented Tenth Circle.

given the input "AB",
(.+)? could match the empty string before "A" (i.e. use the ?"?)
(-?\d*\s*)+ could match the next 140,000 empty strings before "A"
how long did you want to wait?

But try instead (-?\d+\s*)+
and "1234" could match that between one and four times.

Try [-\d\s]+ and it might go even faster.

Perl special-cases regular expressions that match the empty string, when
used to split strings, saying they match exactly once between each input
character, so that
  split /.*/, "hello" 
returns ("h", "e", "l", "l", "o"), but this is not a fundamental or even
common feature of regular expressions, just a rule that Perl has in
order to behave sensibly when you ask for the result of dividing a cake
by zero in a forest with no fallen trees.

Liam

-- 
Liam Quin - XML Activity Lead, W3C, http://www.w3.org/People/Quin/
Pictures from old books: http://fromoldbooks.org/
Ankh: irc.sorcery.net irc.gnome.org freenode/#xml