Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re^2: regex step counting

by Random_Walk (Prior)
on Dec 03, 2019 at 17:07 UTC ( #11109610=note: print w/replies, xml ) Need Help??


in reply to Re: regex step counting
in thread regex step counting

Thanks, I like this answer.

While talk of the halting problem further down is interesting, I have a real world situation now where users are putting out bad regex on production servers. The regex they have access ltoo is actualy not Perl, but a very limited subset of Java's regex. It has .* though and they manage to shoot themselves in the foot with abundant use of .* I don't really need 100% accurate count of how many steps they are taking, just an idea if they are in the region of up to a few hundred steps per line, or way beyond it. If they breach some arbitrary limit we will ask them to come to us for regex guidance. So counting the lines from a re debug will be close enough for my purpose.

Cheers,
R.

Pereant, qui ante nos nostra dixerunt!

Replies are listed 'Best First'.
Re^3: regex step counting
by LanX (Cardinal) on Dec 03, 2019 at 22:21 UTC
    > not Perl, but a very limited subset of Java's regex

    I was afraid you'd say this, different engines do different guessing and optimizations.

    Something very fast in Perl can be a nightmare elsewhere, and vice versa.

    > I don't really need 100% accurate count of how many steps they are taking, just an idea if they are in the region of up to a few hundred steps per line

    It really depends on how limited your grammar is.

    The point why I mentioned the halting problem is, that the proof shows a way to construct a pathological case for every approach.

    In other words, if your tests are limited it's possible to construct a troublesome regex which will pass them. (Provided the grammar is rich enough)

    Hence no guaranties whatsoever!

    Good luck! :)

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery FootballPerl is like chess, only without the dice

    ) actually it's pretty trivially done, if the regex has no length restriction.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://11109610]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (7)
As of 2021-04-22 17:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?