2009/3/12 Deviloper <devilo...@slived.net> > Can somebody explain what Backtracking is? > > thanx, > B. >
In a nutshell, consider the following regex: /foo((b+)ar)/ a regex engine will check every character in the string that is checked against until it reaches the first "f". When reached, it will mark the place and check the next character, if its not an 'o', the mark will be removed. If it is, the next character will be checked and so on. When the string's end will be reached, it will report whether a match was found (and where it was found). Now, in Perl, we would like to use that ((b+)ar) as $1, $2 and so on. This means, that when the engine needs to mark not only the location of the 'f', but also the 'b', when reached. Assuming the string 'snafoobbbar', the engine will need to backtrack over to the first 'b', and each time save the 'b+' string for future reference. When the first 'b' is reached, $1 is now (assuming a match) 'b' and $2 is (potentially) 'bar'. The next character is also a 'b', and with that $1 is now 'bb' and $2 (potentially) 'bbar'. The engine have to make those adjustments accordingly, with each iteration forcing it to readjust all the variables it saves. I do recommend J. Freidl's "Mastering Regular Expressions" for a better understanding of how those engines function, at least theoretically (as the actual algorithmic implementation might differ much from my basic explanation, or from the descriptions in the book). -- Erez It's time to grow out of the browser; we have nothing to lose but our metaphors. -- To unsubscribe, e-mail: beginners-unsubscr...@perl.org For additional commands, e-mail: beginners-h...@perl.org http://learn.perl.org/
