RegExp: "wontmatch"-function

[pjacobi.de]

Dear All,

I'm looking for a function which, given a regexp re and and a string
str, returns
whether re won't match any string starting with str. (so it would
always
return False if str is "" or if str itself matches re -- but that are
only the
easy cases).

I have the vague feeling that the internal workings of the regexp
matcher
can answer the question, but that there's no way to get this result
from Python code.

Any ideas or prior art on how to get this function?

Regards,
Peter

 

[william tanksley]

I'm looking for a function which, given a regexp re and  and a string
str, returns whether re won't match any string starting with str. (so
it would always return False if str is "" or if str itself matches re
-- but that are only the easy cases).

Wow, that's a pretty problem.

Any ideas or prior art on how to get this function?

An idea, which I haven't explored well enough:

Parse the regexp, and recursively descend the parse tree; for each
node on the recursive descent, generate the regexp that follows the
descent to end at that node and ask if it matches the string. If it
matches, return 'False'. If the recursion ends without ever matching,
return 'True'.

There are a few questions on how to do that. I don't know how to parse
the regexp (but I know how to start and am confident that it'd be
easy); I don't know how to generate the regexp given a descent path
(but I think I could do it). I'm also not sure this is correct, but
it's not a homework assignment for me, so I'm not worried.

Peter

-Wm