Re: regex step counting (Halting problem)

> and ensure that they never enter the world of ridiculous step count.

Sidenote: Are you aware of the Halting problem?

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

update

though there is an ongoing discussion if Perl RegExes (without embedded (?{Perl code}) ) are Turing complete and which features should be stripped off to make them "uncomplete".

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery
FootballPerl is like chess, only without the dice}

Comment on Re: regex step counting (Halting problem) Download Code

Replies are listed 'Best First'.
Re^2: regex step counting (Halting problem) by Corion (Patriarch) on Dec 03, 2019 at 14:45 UTC
You don't need to solve the halting problem to enforce and/or check that a regex stops after a time limit or step limit. If you're launching the regex engine with user-supplied input, I'm not sure whether you can single-step through the regexp, but most likely you can do something like what Regexp::Debugger does and limit the amount of steps there. Alternatively, declare an upper time limit which you allow for user-supplied regular expressions. The problematic part of the halting problem only comes into play for stuff that runs very long but not infinitely long. For the OP, these two cases fall into the same category.	[reply]
Re^3: regex step counting (Halting problem) by LanX (Saint) on Dec 03, 2019 at 14:51 UTC
I never said that he has to solve the halting problem. His approach is to test against a set of input strings.° I wouldn't be surprised if a finit input set can't cover all cases for arbitrary regexes. This also highly depends on the allowed RegEx grammar, like embedded Perl code (at the extreme). Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice} °) "a few hundred sample lines"	[reply]