The forward tracking quantifier modifier

Because of backtracking, we might sometimes match more than we hoped for. The task below is to catch all the div tags in an HTML document and put them in a vector. Our naïve solution gives the wrong answer:

  • '<div>a</div><span>c</span><div>b</div>'.scan /<div>.*<\/div>/ #=> ["<div>a</div><span>c</span><div>b</div>"]

Quantifiers are greedy in regex. They devour as much as they can. The dot in the idiom .* matches anything except newline (remember Barbapapa?). And the asterisk means that this anything is repeated as many times as possible. Since the string ends with a “</div>” the entire substring “a</div><span>c</span><div>b” will be consumed by .*.

There are many stories about greedy people who claim more than they need. As Louis Blanc wrote already 1840 in The Organization of Work: “From each according to his abilities, to each according to his needs.” We don’t think that the asterisk and the dot in the above example needs to consume more than the substring “<div>a</div>”. Alexander Pushkin describes in The Tale of the Fisherman and the Fish how a magic fish promises to fulfill any of the fisherman’s whishes. The fisherman’s wife starts asking the fish for bigger and better things — and she gets them — until she eventually wants to become Ruler of the Sea. Then the magic fish takes back everything he gave the fisherman’s wife.

As a complement to backtracking, regex also provides forward tracking. The quantifier tries to take as little as it can and then holds to see if the whole expression can be matched. If the entire expression can’t be matched, then the quantifier will capture one more letter and holds to see if it’s now possible to match everything. The method is repeated until either we can match everything or we can confirm that there’s no possible way to create a match. Does it matter if we use forward tracking instead of backtracking? Well, the strings that can be matched with backtracking can also be matched with forward tracking and vice versa. But, when there are multiple possible matches, forward tracking will sometimes choose a different match than backtracking does.

There is no special symbol for forward tracking quantifiers. Instead, there’s modifier symbol — written as a question mark — that can be used right after any quantifier. While * means repeat as many times as possible, *? means repeat as few times as possible. Similarly, we can modify all the other quantifiers:

  • At least one, as few as possible: +?
  • Zero or one, preferably zero: ??
  • Between 3 and 5, as few as possible: {3.5}?

Note that the question mark that modifies quantifiers isn’t the same question mark that’s used as the conditional quantifier. They can even be used in conjunction, as ?? shows above.

Here are some examples. The first one is the solution to the div tag problem:

  • '<div>a</div><span>c</span><div>b</div>'.scan /<div>.*?<\/div>/ #=> ["<div>a</div>", "<div>b</div>"]
  • 'aa'[/a?/] #=> "a"
  • 'aa'[/a??/] #=> ""
  • 'aaaaa'[/a{2,4}/] #=> "aaaa"
  • 'aaaaa'[/a{2,4}?/] #=> "aa"
  • 'aaaaa'[/a{2,}/] #=> "aaaaa"
  • 'aaaaa'[/a{2,}?/] #=> "aa"
  • 'aaaaa'[/a{,4}/] #=> "aaaa"
  • 'aaaaa'[/a{,4}?/] #=> ""

Pomodoro Technique Illustrated -- New book from The Pragmatic Programmers, LLC

Advertisements


%d bloggers like this: