4 ms·

I'm not sure the date of the linked page, but this is why RE2[0] was created. Russ Cox has some examples where PCRE falls over flat[1]. EDIT: Looks like the o

• brudgers 11y ago
  From the Cox article: As far as the theoretical term is concerned, regular expressions with backreferences are not regular expressions. The power that backreferences add comes at great cost: in the worst case, the best known implementations require exponential search algorithms, like the one Perl uses. Perl (and the other languages) could not now remove backreference support, of course. Cox then proposes a hybrid engine that can be quicker when capture groups aren't needed. TCL has this sort of hybrid implementation, http://wiki.tcl.tk/396 http://wiki.tcl.tk/396. It's worst case performance won't be big-O better than Perl's for pathological cases that require backtracking. If P no more or less equals NP today than in 2001, the article's conclusion has not lost correctness.
  • thaumasiotes 11y ago
    > Cox then proposes a hybrid engine that can be quicker when capture groups aren't needed. Capture groups aren't the same thing as backreferences. You can do capturing groups fine in linear time (or at least, something close to linear time).
    • brudgers 11y ago
      Thanks for the clarification. This page was helpful: https://msdn.microsoft.com/en-us/library/thwdfzxy(v=vs.110).aspx https://msdn.microsoft.com/en-us/library/thwdfzxy(v=vs.110)....
  • mjd 11y ago
    I believe the GNU regex library also uses a hybrid algorithm.
  • dtamhk 11y ago
    Actually at the 4th Ed. of the Camel Book, there is a page or two devoted to rsc's engine CHAPTER 5 Pattern Matching Fancy Patterns - Alternate Engines Starting with v5.10, you can even swap out Perl’s entire regex engine and replace it with an alternate pattern-matching library. ... Table 5-18. Alternate regex engines re::engine::RE2 - Russ Cox’s RE2 regex engine ... One engine of special note is Russ Cox’s RE2 library. It’s a C and C++ library that’s used in the Go programming language, among many other places. The interesting thing is that it maintains a high level Perl compatibility, including good UTF-8 support, while avoiding the potential pitfalls of catastrophic backtracking. It does this because unlike Perl, whose engine is a recursive backtracker, RE2 uses a hybrid NFA/DFA approach that never gets bogged down in pathological cases. This can be critical in time-sensitive applications where you want to let users provide their own pattern, but you cannot risk letting their search take forever. First written for Google’s Code Search, where time is of the essence, RE2 is also used via its Perl interface at http://grep.cpan.me http://grep.cpan.me. This site lets you enter a search pattern that runs over everything in CPAN. ...
    • brudgers 11y ago
      The possibility of exponential runtimes can only be eliminated by limiting the input language in ways that Perl Regular Expressions do not [i.e. eliminating the NP-hard languages]. Swapping out the engine for one that does not bog down means reducing the expressive power. See this answer on SE-Computer Science: http://cs.stackexchange.com/a/46837 http://cs.stackexchange.com/a/46837 or this discussion on lambda-the-ultimate: http://lambda-the-ultimate.org/node/2961 http://lambda-the-ultimate.org/node/2961
      • eru 11y ago
        > [i.e. eliminating the NP-hard languages] You have to eliminate even harsher. Prime factoring is also expressible in Perl regular expression.
• mjd 11y ago
  The linked page was first published 1 February 1998. The reduction from 3COL was added 12 June 1999.