Изнутри Java, как я могу создать список всех возможных чисел из определенного регулярного выражения?

У меня странная проблема, по крайней мере одна, с которой я никогда не сталкивался. У меня есть предварительное условие, когда у клиентов есть простые регулярные выражения, связанные с ярлыками. Этикетки - все, о чем они заботятся. Я хотел бы сделать список всех возможных чисел, которые соответствовали бы каждому из этих регулярных выражений. У меня была бы логика, которая предупреждала бы меня, когда список выходит за определенный порог.

Вот пример регулярного выражения: 34.25.14.(227|228|229|230|243|244|245|246)

Предположим, что эти ip (s) связаны с ACME. За кулисами, когда пользователь выбирает ACME (в нашем пользовательском интерфейсе), я заполняю объект фильтра, который содержит все эти возможные числа, и отправляет их в качестве запроса OR в узкоспециализированную базу данных Vertica.

Я просто не могу определить элегантный способ создания списка чисел из указанных регулярных выражений.

Другим аспектом этого является то, что код java в другой части продукта использует эти регулярные выражения для отображения ACME с помощью java Pattern.compile(), что означает, что клиент "может" создать сложное регулярное выражение, Я видел их только до сих пор, используя что-то простое, как показано выше.

Есть ли метод, который будет генерировать список на основе регулярного выражения?

Спасибо за ваше время.

Ответы

Ответ 1

по теме:

Библиотека, которая генерирует данные, соответствующие регулярному выражению (с ограничениями): http://code.google.com/p/xeger/

Несколько решений, например, обращение к регулярному выражению в грамматику: Использование Regex для генерации строк, а не их соответствия

РЕДАКТИРОВАТЬ: На самом деле, вы можете заставить его работать!!!. Единственное, на что нужно обратить внимание, - наложить некоторые ограничения для домена, чтобы исключить комбинаторный взрыв, такой как +.

Если вы добавите в класс Xeger что-то вроде этого:

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());
        }
    }
}

... и что-то вроде этого для 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();
}

... вы получите следующее:

-------------------------------------------------------
 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

... и, угадайте, что. Для "[ab] {4,6} c" он правильно производит 112 вариантов.

Это действительно быстрый и грязный эксперимент, но, похоже, он работает;).

Ответ 2

Я бы сказал, что технический ответ - нет, так как вы можете указать в регулярном выражении, что символ (цифра) встречается ноль или более раз. Это "или больше" может означать произвольно большое количество цифр. На практике вы можете ограничить длину строк и рекурсивно построить надстрочный ряд строк на основе символов, которые вы найдете в регулярном выражении, а затем направить их для создания списка подмножеств.

Ответ 3

Комментарий: регулярное выражение является рекурсивно перечислимым языком, поэтому существует алгоритм, который может перечислять все допустимые строки.

Даже для более сложного языка, такого как Java, может быть алгоритм, который перечисляет все Java-программы; независимо от того, как написана ваша конкретная Java-программа, этот алгоритм за конечное время выведет Java-программу, которая точно соответствует вашим.

Но не все языки перечислены так: то они - языки, которые мы знаем, но мы не можем говорить. Они навсегда избегают любого примитивного интеллекта, подобного нашему, но это машина для обучения.

Ответ 4

Грубая сила, многопоточность, загрузка процессора 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();
      }
   }
}

Просто для удовольствия...

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

прошедшее время: 01:18:59

Операционная система

Microsoft Windows XP Professionnel 32-разрядный SP3

CPU

Intel Xeon W3565 @3.20GHz 39 ° C
Технология Bloomfield 45 нм

ОЗУ

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

Материнские платы

LENOVO Lenovo (1366-контактный LGA)

Ответ 5

Эта проблема потрясающая!

Я решил его с помощью простой грамматики JavaCC и трех классов: Constant, Variable и Main. Выражение, которое я использовал как вход, (34|45).2\d.14.(227|228|229|230|243|244|245|246), обратите внимание на \d, чтобы указать переменную часть.

Вот грамматика JavaCC:

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 ))
}

И фрагмент 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

И снимок полученного приложения Swing (очень отзывчивый):

Весь проект Eclipse можно загрузить с lfinance.fr.