14

私は奇妙な問題を抱えています。少なくとも、一度も遭遇したことがない問題です。顧客がラベルに関連付けられた単純な正規表現を持っているという前提条件があります。彼らが気にするのはラベルだけです。私がやりたいのは、これらの正規表現のそれぞれに一致する可能性のあるすべての数値のリストを作成することです。リストが特定のしきい値を超えたときに警告するロジックがあります。

正規表現の例を次に示します。34.25.14.(227|228|229|230|243|244|245|246)

これらの IP が ACME に関連付けられているとしましょう。ユーザーが (UI で) ACME を選択すると、舞台裏で、考えられるすべての数値を含むフィルター オブジェクトに入力し、高度に専門化された Vertica データベースに OR クエリとして送信します。

上記の正規表現から数値のリストを作成するエレガントな方法を判断できません。

これの他の側面は、製品の別の部分内の Java コードがこれらの正規表現を使用して、Java Pattern.compile() を使用して ACME を表示していることです。これは、顧客が複雑な正規表現を「作成できる」ことを意味します。これまでのところ、上記のように単純なものを使用しているだけです。

正規表現に基づいてリストを生成する方法はありますか?

御時間ありがとうございます。

4

5 に答える 5

6

関連している：

正規表現に一致するデータを生成するライブラリ (制限あり): http://code.google.com/p/xeger/

正規表現を文法に変換するなど、いくつかの解決策: 正規表現を 使用して文字列を照合するのではなく生成する

編集：実際には、それを機能させることができます!!! 対処すべき唯一のことは、ドメイン固有の制約を課して、a+ のような組み合わせの爆発を防ぐことです。

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 のバリアントが正しく生成されます。

これは本当に簡単で汚い実験ですが、うまくいくようです ;)。

于 2012-10-16T21:29:50.927 に答える
0

コメント: 正規表現は再帰的に列挙可能な言語であるため、すべての有効な文字列を列挙できるアルゴリズムが存在します。

Java のようなより複雑な言語の場合でも、すべての Java プログラムを列挙するアルゴリズムが存在する場合があります。特定の Java プログラムがどのように作成されたとしても、そのアルゴリズムは、限られた時間内に、正確に一致する Java プログラムを出力します。

しかし、すべての言語がこのように列挙できるわけではありません。そして、それらは私たちが存在することを知っているが、話すことができない言語です。それらは、チューリングマシンに過ぎない私たちのような原始的な知性を永遠に逃れます。

于 2012-10-16T22:02:08.913 に答える
0

文字（数字）が0回以上発生することを正規表現で指定できるため、技術的な答えはノーだと思います。その「以上」は、任意の桁数を意味する場合があります。実際には、文字列の長さを制限し、正規表現で見つけた文字に基づいて文字列のスーパーセットを再帰的に構築し、それらにテキストを入力してサブセット リストを作成できる場合があります。

于 2012-10-16T21:33:46.597 に答える
0

この問題はすごい！

単純な JavaCC 文法と 3 つのクラス (定数、変数、メイン) で解決しました。入力として使用した式は(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からダウンロードできます。

于 2012-10-17T20:45:49.607 に答える