5 ms·
There are features of some regular expressions for which the only known solution is backtracking. If you want those features then you "require backtracking".
by stuckagain 10y ago
There are features of some regular expressions for which the only known solution is backtracking. If you want those features then you "require backtracking".
- ue_ 10y agoOut of interest, what are some of these? I have a hard time believing that the implementors of the Perl regex engine chose to write it that way for no reason while the Thompson NFA figures are thrown about. I knew there must havevbeen something this 'implementation detail' was good for.
- eridius 10y agoI believe backreferences require backtracking.
- tatref 10y agoNo, but variable size lookahead/behind do. This is because the engine has to go back if the remaining part of a regex fails. For some examples, see http://www.regular-expressions.info/recursebacktrack.html http://www.regular-expressions.info/recursebacktrack.html) EDIT: you are correct, backreferences do require backtracking, my bad.
- geofft 10y agoAn easy example is matching palindromes. You simply can't match a palindrome by moving forward only; you have to go back and see if every letter matches. So, if you want to search for the longest palindrome in a string, you'll necessarily be doing a lot of backtracking. There's no RE2-compatible regular expression for matching palindromes, but additional features as found in PCRE and similar "regex" engines can do it with backreferences or with look-around assertions. See http://stackoverflow.com/q/3746487 http://stackoverflow.com/q/3746487 and http://stackoverflow.com/q/3664881 http://stackoverflow.com/q/3664881 for two ways to write such a regex.