Re: Analysis of Regular Expressions

[rubasov]

This post is a little late, but I've just came across Regexp::Compare and remembered your OP. Putting aside the theoretical complaints on complexity consider the following code:

use strict;
use warnings;
use IPC::Run3;
use Regexp::Compare qw( is_less_or_equal );

my @re = (
  qr/asdf/,
  qr/asd/,
  qr/as/,
  qr/a/,
  qr/./,
  qr/.*/,
);

my $stdin  = '';
my $stdout = '';
my $stderr = '';
for my $i ( 0 .. $#re ) {
  for my $j ( 0 .. $#re ) {
    $stdin .= "$i $j\n" if is_less_or_equal( $re[$i], $re[$j] );
  }
}

# tsort (GNU coreutils) 8.4
run3 [ 'tsort' ], \$stdin, \$stdout, \$stderr;
print $stderr;

my @idx = split /\s+/, $stdout;
print "$_\n" for @re[@idx];

In the output the most specific regex comes first and the most generic comes last. If you put more than one equivalent regexes into your input then you get a nice warning on loops:

my @re = (
  qw/./,
  qw/./,
  qw/.+/,
);

in $stderr:
tsort: -: input contains a loop:
tsort: 0
tsort: 2
tsort: 1
tsort: -: input contains a loop:
tsort: 0
tsort: 2
tsort: -: input contains a loop:
tsort: 1
tsort: 2

I've used topological ordering because the more-specific relation on regexes is not a total ordering (I hope I'm using the correct math terms), however this still guarantees that a more specific item comes earlier therefore you won't get the "false" (more generic) match first.

As a sidenote: while playing with this, I've realized that your sample regexes are a little "dirty". Let's take \AHi and \b(Hi(ya)?|Hello|Greetings)\b for instance. None of these two is more specific than the other, because none of the sets of every possible match is a subset of the other. (Consider the strings His and Foo Hi.)

Specifically GNU tsort is probably a better choice than Sort::Topological as it does not die on cyclic graphs.

Of course Regexp::Compare uses heuristics, I suppose something along like this:

hypothesis:
                  $re1 <= $re2
is_less_or_equal( $re1,   $re2 )
      specific -> $re1    $re2 <- generic

if exists $str that
$str =~ /$re1/ and $str =~ /$re2/ -> no consequence
$str =~ /$re1/ and $str !~ /$re2/ -> falsifies hypothesis
$str !~ /$re1/ and $str =~ /$re2/ -> corroborates hypothesis
$str !~ /$re1/ and $str !~ /$re2/ -> no consequence

But I cannot tell how well it performs for real regexes.

I hope this is useful for you.