RegExp: "wontmatch"-function

william tanksley wtanksleyjr at
Tue Oct 14 00:37:56 CEST 2008

On Oct 13, 9:40 am, pjacobi... at wrote:
> 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


More information about the Python-list mailing list