6 ms·
Thanks, that link works. It looks like it did something similar to the strategy I described, but it ordered the states differently. It also inserted a lot of
by btilly 16y ago
Thanks, that link works.
It looks like it did something similar to the strategy I described, but it ordered the states differently. It also inserted a lot of unnecessary parentheses. I also dislike the need for \ everywhere. With Perl compatible REs you don't need them, and that gets rid of a lot of line noise.
I'm tempted to put together a Python program to generate these, with options to control how much they expand out.
- eru 16y agoI removed most of the unnecessary parenthesis, now. I also put my program on http://github.com/matthiasgoergens/Div7 http://github.com/matthiasgoergens/Div7 I targeted grep, because I know that grep handles regular expressions properly. Perl does a very bad job, according to http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html Perl can take an exponential time to match (or reject). grep always finishes in linear time. Because grep does regular expressions according to theory. While Perl does something strange. To quote: "This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep. The two approaches have wildly different performance characteristics ... The trends shown in the graph continue: the Thompson NFA handles a 100-character string in under 200 microseconds, while Perl would require over 10^15 years." P.S. Good news: I found out that grep -E makes the backslash unnecessary. At http://pastebin.com/Dr7xk8in http://pastebin.com/Dr7xk8in you will find the new and shorter version.
- btilly 16y agoThere are disaster regular expressions where Perl will be slow. But most of the common disasters disappeared a number of years ago. And your regular expression is one that is unlikely to have performance problems due to backtracking. (Though the regular expression engine may hate the size.) That said, Russ Cox is generally well worth listening to.