From within Java, how can I create a list of all possible numbers from a specific regular expression?

Question

I have a strange problem, at least one I've never come across. I have a precondition where customers have simple regular expressions associated with labels. The labels are all they care about. What I would like to do is create a list of all possible numbers that would match each of these regular expressions. I would have logic that would warn me when the list is beyond a certain threshold.

Here is an example of the regular expression: 34.25.14.(227|228|229|230|243|244|245|246)

Lets say that these ip(s) are associated with ACME. Behind the scenes when the user selects ACME (in our UI), I'm filling out a filter object that contains all of those possible numbers and submitting them as an OR query to a highly specialized Vertica database.

I just can't determine an elegant way of creating a list of numbers from said regular expressions.

The others aspect of this, is that the java code within another portion of the product is using those regular expressions to show ACME by using a java Pattern.compile(), which means the customer 'could' create a complex regular expression. I've only seen them, so far, use something simple as shown above.

Is there a method that will generate a list based on regular expression?

Thanks for your time.

Answer 1

Related:

A library that generates data matching a regular expression (with limitations): http://code.google.com/p/xeger/

Several solutions, such as conversing a regex into a grammar: Using Regex to generate Strings rather than match them

---

EDIT: Actually, you can make it work!!! The only thing to address is to impose some domain-specific constraints to preclude combinatorial explosion like a+.

If you add to the Xeger class something like this:

public void enumerate() {
    System.out.println("enumerate: \"" + regex + "\"");
    int level = 0;
    String accumulated = "";
    enumerate(level, accumulated, automaton.getInitialState());
}

private void enumerate(int level, String accumulated, State state) {
    List<Transition> transitions = state.getSortedTransitions(true);
    if (state.isAccept()) {
        System.out.println(accumulated);
        return;
    }
    if (transitions.size() == 0) {
        assert state.isAccept();
        return;
    }
    int nroptions = state.isAccept() ? transitions.size() : transitions.size() - 1;
    for (int option = 0; option <= nroptions; option++) {
        // Moving on to next transition
        Transition transition = transitions.get(option - (state.isAccept() ? 1 : 0));
        for (char choice = transition.getMin(); choice <= transition.getMax(); choice++) {
            enumerate(level + 1, accumulated + choice, transition.getDest());
        }
    }
}

... and something like this to XegerTest:

@Test
public void enumerateAllVariants() {
    //String regex = "[ab]{4,6}c";
    String regex = "34\\.25\\.14\\.(227|228|229|230|243|244|245|246)";
    Xeger generator = new Xeger(regex);
    generator.enumerate();
}

... you will get this:

-------------------------------------------------------
 T E S T S
-------------------------------------------------------
Running nl.flotsam.xeger.XegerTest
enumerate: "34\.25\.14\.(227|228|229|230|243|244|245|246)"
34.25.14.227
34.25.14.228
34.25.14.229
34.25.14.243
34.25.14.244
34.25.14.245
34.25.14.246
34.25.14.230
Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.114 sec

... and, guess what. For "[ab]{4,6}c" it correctly produces 112 variants.

It's really a quick and dirty experiment, but it seems to work ;).

Answer 2

I'd say the technical answer is no, since you can specify in a regex that a character (digit) occurs zero or more times. That "or more" can mean an arbitrarily large number of digits. In practice you might be able to limit the length of the strings and recursively build out a superset of Strings based on the chars you find in the regex and then text them to create your subset list.

Answer 3

Comment: regular expression is a recursively enumerable language, therefore there exists an algorithm than can enumerate all valid strings.

Even for a more complex language like Java, there can be an algorithm that enumerates all Java programs; no matter how your particular Java program is written, that algorithm will, in finite time, output a Java program that exactly matches yours.

But not all languages are enumerable like this; then they are the languages that we know exist but we cannot speak in. They forever elude any primitive intelligence like ours that's but a turing machine.

Answer 4

Brute force, Multithreaded, CPU load 100%:

import java.util.regex.Pattern;

public class AllIP
{
   public static void main( String[] args )
   {
      final Pattern p = Pattern.compile( "34.25.14.(227|228|229|230|243|244|245|246)" );

      int step = 256 / Runtime.getRuntime().availableProcessors();
      for( int range = 0; range < 256; range += step )
      {
         final int from = range;
         final int to   = range + step;
         new Thread(){
            public @Override void run(){
               long atStart = System.currentTimeMillis();
               for( int i = from; i < to ; ++i )
                  for( int j = 1; j < 255; ++j )
                     for( int k = 1; k < 255; ++k )
                        for( int l = 1; l < 255; ++l )
                        {
                           String ip = String.format( "%d.%d.%d.%d", i,j,k,l );
                           if( p.matcher( ip ).matches())
                           {
                              System.out.println( ip );
                           }
                        }
               System.out.println( System.currentTimeMillis() - atStart );
            }
         }.start();
      }
   }
}

Just for fun...

• 34.25.14.227
• 34.25.14.228
• 34.25.14.229
• 34.25.14.230
• 34.25.14.243
• 34.25.14.244
• 34.25.14.245
• 34.25.14.246

elapsed time: 01:18:59

Operating System

• Microsoft Windows XP Professionnel 32-bit SP3

CPU

• Intel Xeon W3565 @ 3.20GHz 39 °C

• Bloomfield 45nm Technology

RAM

• 4,00 Go Dual-Channel DDR3 @ 532MHz (7-7-7-20)

Motherboard

• LENOVO Lenovo (1366-pin LGA)

Answer 5

This problem is amazing!

I solved it with a simple JavaCC grammar and 3 classes : Constant, Variable and a Main. The expression I used as input is (34|45).2\d.14.(227|228|229|230|243|244|245|246), note the \d to specify variable part.

Here is the JavaCC grammar:

options
{
    static         = false;
    FORCE_LA_CHECK = true;
    LOOKAHEAD      = 5;
}

PARSER_BEGIN( IPGeneratorFromRegExp )
package hpms.study.jj;

public class IPGeneratorFromRegExp
{
    public final java.util.SortedSet< hpms.study.IPPart > _a = new java.util.TreeSet< hpms.study.IPPart >();
    public final java.util.SortedSet< hpms.study.IPPart > _b = new java.util.TreeSet< hpms.study.IPPart >();
    public final java.util.SortedSet< hpms.study.IPPart > _c = new java.util.TreeSet< hpms.study.IPPart >();
    public final java.util.SortedSet< hpms.study.IPPart > _d = new java.util.TreeSet< hpms.study.IPPart >();

}// class IPGeneratorFromRegExp

PARSER_END( IPGeneratorFromRegExp )

SKIP :
{
  " "
| "\r"
| "\t"
| "\n"
}

TOKEN :
{
    < IPPARTX   :                          (["1"-"9"] | "\\d" ) > 
|   < IPPARTXX  :     (["1"-"9"] | "\\d" ) (["0"-"9"] | "\\d" ) > 
|   < IPPART1XX : "1" (["0"-"9"] | "\\d" ) (["0"-"9"] | "\\d" ) >
|   < IPPART2XX : "2" (["0"-"4"] | "\\d" ) (["0"-"9"] | "\\d" ) >
|   < IPPART25X : "2" "5"                  (["0"-"5"] | "\\d" ) >
}

void part( java.util.SortedSet< hpms.study.IPPart > parts ):{ Token token = null; }
{
    (
        token=<IPPART25X>
    |   token=<IPPART2XX>
    |   token=<IPPART1XX>
    |   token=<IPPARTXX>
    |   token=<IPPARTX>
    ){
        parts.add(
            token.image.contains( "\\d" )
                ? new hpms.study.Variable( token.image )
                : new hpms.study.Constant( token.image ));
    }
}

void expr( java.util.SortedSet< hpms.study.IPPart > parts ):{}
{
    "(" part( parts ) ( "|" part( parts ))+ ")"
}

void analyze() :{}
{
    ( part( _a ) | expr( _a )) "."
    ( part( _b ) | expr( _b )) "."
    ( part( _c ) | expr( _c )) "."
    ( part( _d ) | expr( _d ))
}

And a fragment of Main.java:

     Reader                source      = new StringReader( _regExp.getText());
     IPGeneratorFromRegExp ipGenerator = new IPGeneratorFromRegExp( source );
     ipGenerator.analyze();

     SortedSet< String > a = new TreeSet<>();
     SortedSet< String > b = new TreeSet<>();
     SortedSet< String > c = new TreeSet<>();
     SortedSet< String > d = new TreeSet<>();
     for( IPPart<?> part : ipGenerator._a ) part.expandTo( a );
     for( IPPart<?> part : ipGenerator._b ) part.expandTo( b );
     for( IPPart<?> part : ipGenerator._c ) part.expandTo( c );
     for( IPPart<?> part : ipGenerator._d ) part.expandTo( d );

     _result.clear();
     for( String ac : a )
     {
        for( String bc : b )
        {
           for( String cc : c )
           {
              for( String dc : d )
              {
                 _result.add( ac + '.' + bc + '.' + cc + '.'  + dc );
              }// for
           }// for
        }// for
     }// for

And a snapshot of the resulting Swing application (very responsive):

The whole Eclipse project may download from lfinance.fr.