in reply to Re^2: Perl regex in real life
in thread Perl regex in real life

Neither backtracking nor captures are really a problem needing to be fixed. Features like (?>) were added to help extend the sorts of things regular expressions can do.

To take your example, regular expressions are not the problem with why the wrong thing was matched. Your expression allowed that interpretation (or it would have with some minor changes). The problem is that you are using an expression that does not properly cover the case you claim to be looking for.

To take another example that I think shows why these features are more useful, let's match a US telephone number. A telephone number in the US can take many forms:

And that leaves out adding a 1 or 0 for long distance and extensions, which people often give as part of the number.

Matching this set of expressions requires optional characters which (if you are doing captures) requires backtracking. (Not really, but the implementation gets hairier if we discuss that part.)

So to match a phone number, we would need:

  m{ (
       (?: \( \d\d\d \) \s* ) | \d\d\d (?: -? | \s* ) ) ?
       \d\d\d (?: - | \s* ) \d\d\d\d
     )
   }x;

[download]

Obviously, this appears somewhat complicated and there is quite a bit of possibility for confusion. In this case, however, the problem is not the regex, it's the fact that the phone number format is specified fairly sloppily.

In fact, the times that I have often found the features you are questioning most useful are when I'm dealing with real world data. Because unlike the stuff (insert pompous tone) I generate, the real world is messy and inconsistent.

One of the nastiest problems I ever tried to solve was to extract tables of information from text files generated by people at various companies. You have no idea how many weird variations that people can come up with that a person can interpret, but are almost unparseable by computer. Without many of these features, we would not have gotten as far as we did.

G. Wade

Replies are listed 'Best First'.
Re^4: Perl regex in real life
by RezaRob (Initiate) on Nov 01, 2008 at 00:09 UTC
    Neither backtracking nor captures are really a problem needing to be fixed.
    Notice that I never said captures where a "problem". They are an important feature that backtracking tries to address in a way that doesn't loose backwards compatibility with NFA machines. 
    
    * (713) 445-7890
    * 713-445-7890
    * 7134457890
    * 713 445 7890

    [download]
    Matching this set of expressions requires optional characters which (if you are doing captures) requires backtracking. (Not really, but the implementation gets hairier if we discuss that part.) So to match a phone number, we would need: 
    m{ ( (?: \( \d\d\d \) \s* ) | \d\d\d (?: -? | \s* ) ) ? \d\d\d (?: - |
+ \s* ) \d\d\d\d ) }x;

    [download]
    I don't see any backtracking here. The "pointer" always only moves forward. The simplistic C-code example that I posted also has the star operator in it's regex, but that's not what causes it to backtrack(i.e. literally go back and erase a previous match.) A conditional like /\)*/ isn't really backtracking in it's own right, it either matches or doesn't match at all. However, to get the parenthesis in your example _precisely_ right, backreferences are actually needed, which is interesting.
    One of the nastiest problems I ever tried to solve was to extract tables of information from text files generated by people at various companies. You have no idea how many weird variations that people can come up with that a person can interpret, but are almost unparseable by computer. Without many of these features, we would not have gotten as far as we did.
    Fair enough, and you're right. I can see sometimes in the real world one just has to get a job done in this way and perhaps quickly. However, I should point out that the long term solution in these cases is a more intelligent system. Solving these with regex is just looking at the problem the wrong way. Think of what Google news does. Or Google translator for that matter. They don't, and can't, use regex for these technologies. You need some level of machine intelligence, that views the problem much more abstractly.

    Reza.
[reply]
[d/l]
[select]

      You are correct, of course. My example did not show backtracking in action. However, if the data I'm trying to match were lists of phone numbers:

      • 1. 713 445-7890
      • 20 (713) 445-7890

      backtracking then does become involved. Even though we only match one or two digits in the examples above, the expression does begin to match and then has to fail and try something else.

      I guess I really didn't understand your point. How would you propose a system like regular expressions to handle failing partial matches?

      As for using a more intelligent system, that is not a particularly useful suggestion when you are trying to develop the more intelligent system in the first place. Regular expressions are often used for lexing before making passing data to the more intelligent system.

      G. Wade
[reply]

In Section Seekers of Perl Wisdom