killing your regexp engine


Take a look at the following regexp: ^[0-2]~(([0-9A-F]{2})+|~)+$. All nice and cute, isn't it? Well, don't think too fast. I have some input text that can literally kill your regexp engine if you try to match against this regexp (the match will take an exponential time to match each time the input text grows by 2 characters).

There are "killable" regexp engines, and "non-killable", so I guess it all boils down to how much the regexp engine suck. Without a big surprise, Perl's is not killable, when Ruby's, Python's and Java's are.


Killable:


Semi-killable:


Not killable:


Last update: Wed May 4 15:32:44 2005