Re^2: Checking whether a string is a prefix of any string matching a given regular expression

Thank you for your insightful reply, Hugo.

Regarding /^a/ and /a/: I don’t see any problem with either. You can make errors when typing against the former, as you said, and my algorithm detects those errors. On the other hand, you can never make an error when typing against the latter, as you also said (and my algorithm will never report a false positive).

I’m not very familiar with the implications of lookaheads, but your example of "abcd" =~ /^ab(?=.*foo)cd/ seems rather unproblematic to me. The engine would go looking for “foo” and thereby bump into the end of string, which means that "abcd" cannot be ruled out as a potential prefix of some match of the given pattern (which is indeed correct, because it is a prefix of, e.g., "abcdfoo"). Can you think of a case in which the algorithm gives the wrong answer?

Your next example is more interesting. I agree that applying the algorithm to "ab" =~ /^abc(?<=d)/ would fail to establish that "ab" is not a prefix of any matching string. But this is an imaginary/academic problem, because the given regular expression would never occur in the real world except as an outright bug. I wonder if the problem can occur non-pathological cases (i.e., for regular expressions that can actually match things). Can you think of any example?

I find intriguing the idea of iterating through the Cartesian product of input string prefixes and pattern prefixes (the latter of which will be non-trivial to generate, as you point out), and attempting to match each string–pattern pair. Though obviously inefficient, I think the fact that this is something you could implement without touching any C code makes it the most attractive solution so far. :-)

Comment on Re^2: Checking whether a string is a prefix of any string matching a given regular expression Select or Download Code

Replies are listed 'Best First'.
Re^3: Checking whether a string is a prefix of any string matching a given regular expression by hv (Prior) on Jul 02, 2005 at 00:12 UTC
I’m not very familiar with the implications of lookaheads, but your example of `"abcd" =~ /^ab(?=.foo)cd/` seems rather unproblematic to me. The engine would go looking for “foo” and thereby bump into the end of string, which means that `"abcd"` cannot be ruled out as a potential prefix of some match of the given pattern (which is indeed correct, because it is a prefix of, e.g., `"abcdfoo"`). Can you think of a case in which the algorithm gives the wrong answer? Compare the results against `"abxy" =~ /^ab(?=.foo)cd/`. The Cartesian product approach will say for both cases that `"ab" =~ /^ab/` is the longest matching prefix, while checking what characters are looked at would claim the whole string is ok in both cases. Your next example is more interesting. I agree that applying the algorithm to `"ab" =~ /^abc(?<=d)/` would fail to establish that `"ab"` is not a prefix of any matching string. But this is an imaginary/academic problem, because the given regular expression would never occur in the real world except as an outright bug. I wonder if the problem can occur non-pathological cases (i.e., for regular expressions that can actually match things). Can you think of any example? Well unmatchable patterns could quite reasonably arise in some situations, particularly if they are themselves generated. But I think the likely real-world problems would occur with backreferences, of the `/^(something)other\1/` variety, but I can't think of a concrete example off the top of my head. Hugo	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: Checking whether a string is a prefix of any string matching a given regular expression
by hv (Prior) on Jul 02, 2005 at 00:12 UTC

Compare the results against "abxy" =~ /^ab(?=.*foo)cd/. The Cartesian product approach will say for both cases that "ab" =~ /^ab/ is the longest matching prefix, while checking what characters are looked at would claim the whole string is ok in both cases.

Well unmatchable patterns could quite reasonably arise in some situations, particularly if they are themselves generated. But I think the likely real-world problems would occur with backreferences, of the /^(something)other\1/ variety, but I can't think of a concrete example off the top of my head.

Hugo

[reply]
[d/l]
[select]