7

通常、私たちの作業では、キャプチャまたは一致操作で正規表現を使用します。

ただし、正規表現は、正規表現に一致する正当な文を生成するために (少なくとも手動で) 使用できます。もちろん、一部の正規表現は無限に長い文に一致する場合があります (例: 式 ) .+。

正規表現文生成アルゴリズムを使えば解決できる問題があります。

擬似コードでは、次のように動作します。

re = generate("foo(bar|baz)?", max_match = 100);  #Don't give me more than 100 results
assert re == ("foobar", "foobaz", "foo");

私のためにこれを実行するアルゴリズムは何ですか?

4

2 に答える 2

2

Microsoftには、このためのSMTベースの無償（MSRLライセンス）「Rex」ツールがあります：http ：//research.microsoft.com/en-us/downloads/7f1d87be-f6d9-495d-a699-f12599cea030/

「Rex：Symbolic Regular Expression Explorer」ペーパーの「はじめに」セクションから：

（拡張された）正規表現または正規表現[5]を、SFAと呼ばれる有限オートマトンのシンボリック表現に変換します。SFAでは、動きは個々の文字ではなく文字のセットを表す数式でラベル付けされます。SFA Aは、Aによって受け入れられた文字列の受け入れ条件を記述し、リストとしての文字列の表現に基づいて構築された一連の（再帰的な）公理に変換されます。

SMTソルバーは、あるサイズの範囲内ですべての可能なソリューションを出力できるため、これは探しているものに近い可能性があります。

より統計的で形式的ではない面では、CPANのRegexp :: Genexモジュールも同様に機能します：http ：//search.cpan.org/dist/Regexp-Genex/

次のようなもので使用できます。

#!/usr/bin/env perl
use Regexp::Genex ':all';
my $hits = 100;
my $re = qr/[a-z](123|456)/;
local $Regexp::Genex::DEFAULT_LEN = length $re;
my %seen;
while ((time - $^T) < 2) {
    @seen{strings($re)} = ();
    $Regexp::Genex::DEFAULT_LEN++;
}
print "$_\n" for (sort %seen)[0..$hits-1];

必要に応じて時間とサンプルサイズを調整します。お役に立てれば！

于 2011-05-21T19:30:34.070 に答える
1

Xeger (Google Code)を見てください。

Visual Studio Team System にも逆正規表現ジェネレーターがあるようですが、アルゴリズムがオープン ソースのようには見えません。

于 2010-11-17T20:21:48.410 に答える