Pradeep K. Pant Blog


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.




Copyright © 2007-2024 PRADEEP K. PANT

Source Code | RSS