Menu
I'm debugging a Regular Expression ^(A+)*B over a string AAAC (example from rexegg.com) by two separate debugging tools I have access:
Below is the results (regex101 in the left side):
The question I have is not mainly about the number of steps which is also important to me, but is how backtracks are done. Why do we see differences? (regex101 uses PCRE lib and I set RegexBuddy lib the same)
A comprehensive step by step explanation is really in my favor.
777
Use the test() method to check if a regular expression matches an entire string, e.g. /^hello$/. test(str) . The caret ^ and dollar sign $ match the beginning and end of the string. The test method returns true if the regex matches the entire string, and false otherwise.
$ means "Match the end of the string" (the position after the last character in the string).
Short for regular expression, a regex is a string of text that lets you create patterns that help match, locate, and manage text. Perl is a great example of a programming language that utilizes regular expressions.
A Regular Expression (or Regex) is a pattern (or filter) that describes a set of strings that matches the pattern. In other words, a regex accepts a certain set of strings and rejects the rest.
In short, "backtracking" is when a regex engine returns to a "flexible" match, attempting a different path to get a successful match.
For example, in the following pattern and input:
foo(bar|baz)
foobaz
The regex engine will match "foo", then attempt the first of the two options, matching "b" and then "a", but fails at "r". Rather than failing the whole match, though, it will "rewind the tape" and start with the second alternative, matching "b" then "a" and then "z"... success!
This also works with quantifiers. A quantifier is anything that encourages the engine to match a repeating pattern, including ?, *, + and {n,m} (depending on the engine).
A greedy quantifier (the default) will match as many repetitions as possible before moving on to the rest of the pattern. For example, given the pattern and input below:
\w+bar
foobar
The pattern \w+ will begin by matching the entire string: "foobar". However, when it moves on to the b, the regex engine has reach the end of the input and the match fails. Rather than simply giving up, the engine will ask the last greedy quantifier to give up one of its repetitions, now matching "fooba". The match still fails, so the engine asks \w+ to give up the "a" (failure), and then the "b". After giving up the "b", the engine can now match bar, and the match succeeds.
Another way of thinking of a regex is as a "tree", and backtracking is going back up a node and trying another path. Given the pattern foo(bar|baz) and the input "foobaz", the engine will attempt something like the following:
foo(bar|baz)
|\
| \
| : f (match)
| : o (match)
| : o (match)
| | (bar|baz)
| |\
| | \
| | : b (match)
| | : a (match)
| | : r (FAIL: go back up a level)
| | ^
| |\
| | \
| | : b (match)
| | : a (match)
| | : z (match)
| | /
| |/
| /
|/
SUCCESS
As to why you see differences in the "number" of backtracks... this probably has a lot to do with internal optimizations and logging level. For example, RegexBuddy does not appear to be logging the match to the empty string before ^, while regex101 does. In the end, though, it doesn't really matter what exact order you backtrack in (what order you climb back up the tree) so long as you end up with the same result.
You already know this, but for the benefit of anyone else who happens by, your regex was written to demonstrate "catastrophic backtracking" (aka "evil regex"), where the number of backtrack attempts grows exponentially as the length of the input increases. These regexes can be exploited to perform DoS attacks, so you must use caution not to introduce these into your patterns (as I found out).
166
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
