Professional Web Applications Themes

backtracking in regular expression matching - PERL Miscellaneous

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

  1. #1

    Default backtracking in regular expression matching

    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.
    ccwork Guest

  2. #2

    Default Re: backtracking in regular expression matching

    On 16 Sep 2003 03:14:01 -0700, ccwork <ccworkhotmail.com> 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?
    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...).

    --
    Sam Holden

    Sam Holden Guest

  3. #3

    Default Re: backtracking in regular expression matching

    On 16 Sep 2003 03:14:01 -0700
    [email]ccworkhotmail.com[/email] (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.

    Thens Guest

  4. #4

    Default Re: backtracking in regular expression matching

    Hi,
    But how to interpret the 500 lines output? Any website recommended?
    Thanks.
    "Thens" <thensNOSPAMti.com>
    ???????:20030916174054.5c20a7b0.thensNOSPAMti.com ...
    > On 16 Sep 2003 03:14:01 -0700
    > [email]ccworkhotmail.com[/email] (ccwork) wrote:
    >
    > 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.
    >

    ccwork Guest

Similar Threads

  1. Regular Expression - Need Help
    By _andyK in forum Coldfusion - Advanced Techniques
    Replies: 8
    Last Post: May 20th, 08:22 PM
  2. Replies: 9
    Last Post: September 11th, 10:39 PM
  3. Regular Expression Matching
    By Mike Miller in forum PERL Beginners
    Replies: 1
    Last Post: August 15th, 03:56 AM
  4. help with regular expression
    By gnet in forum PERL Miscellaneous
    Replies: 4
    Last Post: August 8th, 05:06 PM
  5. Regular Expression....?
    By Rajeev Soni in forum ASP.NET General
    Replies: 8
    Last Post: July 24th, 04:46 AM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139