More backtracking examples

Backtracking might be costly so one should try to avoid useless backtracking. Perl regx have  special form of parentheses: (?>…). These are called Perl’s “don’t-ever-backtrack-into-me” markers. They will tell the regex engine that the enclosed sub-pattern can safely be skipped over during backtracking. As we know that the re-matching the contents either won’t succeed or, if it does succeed, won’t help the overall match. So these markers helps to avoid useless backtracking and saves a lot of time.

Some more useful links and examples can be found at:

http://codenode.com/2010/02/28/debugging-perl-regex-backtracking/

Perl Regx documentation page Perlre on Perldoc

Perl Best Practices by Damian Conway

Backtracking example1

Let’s say you want to find the word following “foo” in the string “Food is on the foo table.”:

#!/usr/bin/perl

# Example of backtracking algorithm

use 5.006;

use strict;

use warnings;

$_ = "Food is on the foo table.";

if ( /b(foo)s+(w+)/i ) {

print "$2 follows $1.n";

}

When the match runs, the first part of the regular expression (b(foo) ) finds a possible match right at the beginning of the string, and loads up $1 with “Foo”. However, as soon as the matching engine sees that there’s no whitespace following the  “Foo” that it had saved in $1, it realizes its mistake and starts over again one character after where it had the tentative match. This time it goes all the way until the next occurrence of “foo”. The complete regular expression matches this time and you get the expected output of “table follows foo.”

Still more examples to come …keep watching

Thanks

Backtracking with Perl Regular expression

Wikipedia says Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c (“backtracks”) as soon as it determines that  cannot possibly be completed to a valid solution.

What it meant for Perl:

In fact Backtracking mechanism is core functionality of languages like PROLOG. Perl implements it using regex engine.

Adding backtracking mechanism to our programming arsenal will bring alot of new functionality. This will help us solve problems that otherwise cost us alot of time and effort.

A fundamental feature of Perl regular expression matching involves the notion called backtracking, which is currently used (when needed) by all regular non-possessive expression quantifiers, namely **?+ ,+?{n,m}, and {n,m}?. Backtracking is often optimized internally.

For a regular expression to match, the entire regular expression must match, not just part of it. So if the beginning of a pattern containing a quantifier succeeds in a way that causes later parts in the pattern to fail, the matching engine backs up and recalculates the beginning part–that’s why it’s called backtracking.

I will try to explain backtracking with an example in my next post.

Thanks

Perl 6 book project on github

A Perl 6 book is in development on github. One can try and fork source code. You can catch the authors on

#perl6book on irc.freenode.net. For more info like steps to build the book, pl see the README on github.
PDF versions of this book can be found at
http://puffin.ch/perl/6/ and http://github.com/perl6/book/downloads


Enjoy learning  Perl6 logo