5 ms·

What is backtracking?

by 0xFFC 10y ago

bowmessage 10y ago
http://stackoverflow.com/questions/9011592/in-regular-expressions-what-is-a-backtracking-back-referencing http://stackoverflow.com/questions/9011592/in-regular-expres...
Phritzy 10y ago
https://regex101.com/r/G23xYd/2 https://regex101.com/r/G23xYd/2
- deleted 10y ago
  [deleted]
kbenson 10y ago
A feature of certain types of regular expression engines. It allows for certain types of regular expressions but at the cost of possibly going exponential if you aren't careful about your expression. [1] 1: http://www.regular-expressions.info/catastrophic.html http://www.regular-expressions.info/catastrophic.html
carussell 10y ago
Looks like there's (a lot of) confusion in these comments about the difference between backtracking and backreferences. The `\2` in Phritzy's snippet is a backreference. Backtracking is an implementation strategy for writing a regular expression engine. I don't know why anyone choosing an engine would "require backtracking". It's an implementation detail, not a feature. (Although the fact that Thompson NFAs avoid exponential time complexity inherent to backtracking is something that I suppose could be considered a feature.) Here's a link to some real literature: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- 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 ago
    Out 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 ago
      I believe backreferences require backtracking.
      - tatref 10y ago
        No, 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 ago
      An 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.
- geofft 10y ago
  From the RE2 wiki: "As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported." From your link: One common regular expression extension that does provide additional power is called backreferences. A backreference like \1 or \2 matches the string matched by a previous parenthesized expression, and only that string: (cat|dog)\1 matches catcat and dogdog but not catdog nor dogcat. 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, but they could employ much faster algorithms when presented with regular expressions that don't have backreferences, like the ones considered above. This article is about those faster algorithms. If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. If you do not need backreferences or similar things, then your regex engine may still choose to use backtracking, but does not need to. RE2 is a regex engine that prioritizes never using backtracking as an implementation detail, and therefore does not support backreferences as a matter of external API. RE2 is not able to evaluate Phritzy's regex.
  - carussell 10y ago
    > If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. There's a morphism that maps Phritzy's pattern to an equivalent pattern that can be matched with a Thompson NFA. (It's a similar strategy to the one that allows you to take an NFA and turn it into a DFA.) You can perform a sort of "static decomposition" on a subset of patterns containing backreferences, such that /(cat|dog)\1/ for example decomposes into /catcat|dogdog/. The caveat is that this isn't fully generalizable for all patterns containing backreferences. But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ RE2 chooses not to support any PCRE-style backreferences, because RE2 is a pattern matching engine meant to support patterns that are actually regular, and backreferences are not regular.

What is backtracking?

by 0xFFC 10y ago

What is backtracking?

http://stackoverflow.com/questions/9011592/in-regular-expressions-what-is-a-backtracking-back-referencing http://stackoverflow.com/questions/9011592/in-regular-expres...

Phritzy 10y ago

https://regex101.com/r/G23xYd/2 https://regex101.com/r/G23xYd/2

deleted 10y ago
[deleted]

kbenson 10y ago

A feature of certain types of regular expression engines. It allows for certain types of regular expressions but at the cost of possibly going exponential if you aren't careful about your expression. [1] 1: http://www.regular-expressions.info/catastrophic.html http://www.regular-expressions.info/catastrophic.html

carussell 10y ago

Looks like there's (a lot of) confusion in these comments about the difference between backtracking and backreferences. The `\2` in Phritzy's snippet is a backreference. Backtracking is an implementation strategy for writing a regular expression engine. I don't know why anyone choosing an engine would "require backtracking". It's an implementation detail, not a feature. (Although the fact that Thompson NFAs avoid exponential time complexity inherent to backtracking is something that I suppose could be considered a feature.) Here's a link to some real literature: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html

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 ago
  Out 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 ago
    I believe backreferences require backtracking.
    - tatref 10y ago
      No, 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 ago
    An 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.
geofft 10y ago
From the RE2 wiki: "As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported." From your link: One common regular expression extension that does provide additional power is called backreferences. A backreference like \1 or \2 matches the string matched by a previous parenthesized expression, and only that string: (cat|dog)\1 matches catcat and dogdog but not catdog nor dogcat. 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, but they could employ much faster algorithms when presented with regular expressions that don't have backreferences, like the ones considered above. This article is about those faster algorithms. If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. If you do not need backreferences or similar things, then your regex engine may still choose to use backtracking, but does not need to. RE2 is a regex engine that prioritizes never using backtracking as an implementation detail, and therefore does not support backreferences as a matter of external API. RE2 is not able to evaluate Phritzy's regex.
- carussell 10y ago
  > If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. There's a morphism that maps Phritzy's pattern to an equivalent pattern that can be matched with a Thompson NFA. (It's a similar strategy to the one that allows you to take an NFA and turn it into a DFA.) You can perform a sort of "static decomposition" on a subset of patterns containing backreferences, such that /(cat|dog)\1/ for example decomposes into /catcat|dogdog/. The caveat is that this isn't fully generalizable for all patterns containing backreferences. But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ RE2 chooses not to support any PCRE-style backreferences, because RE2 is a pattern matching engine meant to support patterns that are actually regular, and backreferences are not regular.