Regex: Determine if two regular expressions could match for the same input?

Tom_26155 0
Viewed 13533

I want to find out if there could ever be conflicts between two known regular expressions, in order to allow the user to construct a list of mutually exclusive regular expressions.

For example, we know that the regular expressions below are quite different but they both match xy50:

'^xy1\d'
'[^\d]\d2$'

Is it possible to determine, using a computer algorithm, if two regular expressions can have such a conflict? How?

regex
5 Answers

Another approach would be to leverage Dan Kogai's Perl Regexp::Optimizer instead.

  use Regexp::Optimizer;
  my $o  = Regexp::Optimizer->new->optimize(qr/foobar|fooxar|foozap/);
  # $re is now qr/foo(?:[bx]ar|zap)/

.. first, optimize and then discard all redundant patterns.

Maybe Ron Savage's Regexp::Assemble could be even more helpful. It allows assembling an arbitrary number of regular expressions into a single regular expression that matches all that the individual REs match.* Or a combination of both.

* However, you need to be aware of some differences between Perl and Java or other PCRE-flavors.

user_82919490

If you are looking for a lib in Java you can use Automaton using '&' operator:

RegExp re = new RegExp("(ABC_123.*56.txt)&(ABC_12.*456.*\\.txt)", RegExp.INTERSECTION); // Parse RegExp
    Automaton a = re.toAutomaton(); // convert RegExp to automaton

    if(a.isEmpty()) { // Test if intersection is empty
      System.out.println("Intersection is empty!");
    }
    else {
      // Print the shortest accepted string
      System.out.println("Intersection is non-empty, example: " + a.getShortestExample(true));
    }

Original Answer:

Detecting if two regexes could possibly match the same string

user_100903410
Related