On 16 Sep 2003 03:14:01 -0700, ccwork <ccworkhotmail.com> wrote:Matching occurs starting at the left, each "element" being greedy (unless> Hi,
> For the pattern "(((.*)cd)*)*cdcd" and string "ababcdcdcdef", can
> anyone tell me the detail meachanism of backtracking? This regular
> expression have two level of backtracking, the "((.*)cd)*" and
> "(((.*)cd)*)*", so which one take precedence?
specified otherwise with ?). Backtracking occurs when a match fails.
You have a '**' construct in the regex which will cause *large* amounts
of backtracking, since it leads to *lots* of ways of matching the same
string (even worse there's a .* inside that as well).
But it works from the left greedily, at each step. With backtracking
occuring when some part of the expression can't match. The backtracking
causes the previous greedy expression to match fewer characters (with
non-greedy expressions it would match more...).