comment on

> 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.

In reply to Re^3: regex step counting by LanX
in thread regex step counting by Random_Walk

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Syntactic Confectionery Delight
	PerlMonks