backtracking in regular expression matching

[ccwork]

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?
Thanks.

 

[Sam Holden]

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?

Matching occurs starting at the left, each "element" being greedy (unless
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...).

 

[Thens]

On 16 Sep 2003 03:14:01 -0700
(e-mail address removed) (ccwork) wrote:

# 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?

You can use the 're' module to throw some more debug information to
you.

use re qw /debug/;
-- or --
use re qw /debugcolor/; # same with colored output

see perldoc re for more details.

Regards,
Thens.