Re^4: Perl regex in real life

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.

Comment on Re^4: Perl regex in real life Select or Download Code

Replies are listed 'Best First'.
Re^5: Perl regex in real life by gwadej (Chaplain) on Nov 02, 2008 at 17:35 UTC
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]

Replies are listed 'Best First'.

Re^5: Perl regex in real life
by gwadej (Chaplain) on Nov 02, 2008 at 17:35 UTC

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]