6

Some of regular expression have exponential time of execution due to bad syntax and non-obvious details. Is there any common way to analyze and learn if some regular expression have linear or exponential execution time?

Improve this question
3
  • apparently Regex is evil Commented Feb 9, 2018 at 6:45
  • 1
    @uhoh, yes - now I know it for sure Commented Feb 9, 2018 at 8:01
  • Thanks for the warning, I'm going to avoid it for now. ;-) Commented Feb 9, 2018 at 8:02

1 Answer 1

Reset to default
4

I tend to just use perl and switch on use re 'debug'; before doing a regex operation.

This prints the steps the regex is going through to process, and quickly gives an idea of efficiency.

There's no hard and fast rules - the big warning sign I look for is whether this regex will need to backtrack. See: Catastrophic Backtracking

This can happen more easily when you're using lookahead/lookbehind (but doesn't have to).

In the grand scheme of things though - it pays to remember that whilst regex is a programming language, it's starting point is as a power search-and-replace. And thus implementing complicated logic in it, means you're creating code that's hard to maintain and debug - and so you shouldn't.

One of the useful tricks in perl - it can run in much the same way as sed/grep/awk using command line.

So you can enable regex debugging, and then do 'sed style':

perl -pe 's/search/replace' somefile

But then you can add 'debug' regex:

perl -Mre=debug -pe 's/search/replace/' somefile

Which will debug it whilst you're going.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Catastrophic backtracking is the most serious offender - beware of nested quantifiers.
I think I just discovered a reason to use Perl :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.