Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Mark Leighton Fisher (4252)

Mark Leighton Fisher
  (email not shown publicly)
http://mark-fisher.home.mindspring.com/

I am a Systems Engineer at Regenstrief Institute [regenstrief.org]. I also own Fisher's Creek Consulting [comcast.net].
Friday January 11, 2008
12:06 PM

Regular Expression Matching Can Be Simple And Fast

[ #35365 ]

Regular Expression Matching Can Be Simple And Fast is worth a look. re::engine::Plan9 should let you test this approach.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • I figured it out on my own and thought I had figured out something new.
  • ... but I wish their conclusion wasn't so bozo:

    Regular expression matching can be simple and fast, using finite automata-based techniques that have been known for decades. In contrast, Perl, PCRE, Python, Ruby, Java, and many other languages have regular expression implementations based on recursive backtracking that are simple but can be excruciatingly slow.

    ... for pathetic expressions!

    We're indeed talking about the regular expression /a?a?a?aaa/ which no experienced Perl code would ever use in real code

    • Rewrite it, for example, as

      /(?:a(?:a(?:a)?)?)?aaa/

      Err, come again? Surely you mean “/a{3,6}/”?

      • Even better. :)

        I'm just saying that every pathetic regexp can most likely be rewritten into something that is not pathetic witout much trouble — and possibly even be optimized.

  • I thought the article was important enough to post but I have to confess, I've never run into the problems shown in the article. I've even written my own (simple) regex matcher in C without running into those problems. Maybe this is an example of Jamie Zawinski's

    Some people, when confronted with a problem, think “I know, I'll use regular expressions.” Now they have two problems.

    or Abraham Maslow's:

    If you only have a hammer then you treat everything like a nail.

    Sometimes, you really don't