正規表現を入力し、その正規表現を満たす文字列を出力するプログラムを作成します。

Question

タイトルは正確に私の質問を要約していると思いますが、ちょっとだけ詳しく説明します。

正規表現を使用して既存の文字列のプロパティを確認する代わりに、特定のプロパティを持つ文字列を生成する方法として正規表現を使用したいと思います。

注：関数はに正規表現（正規表現の多くのための文字列の数が無限になる原因）を満たすすべての文字列を生成する必要はありません。多くの有効な文字列のサンプリングだけで十分です。

これはどのように実行可能ですか？ソリューションが複雑すぎる/大きすぎる場合、私は一般的な議論/概要に満足しています。さらに、私はこれを行う既存のプログラムやライブラリ（.NET）に興味があります。

Answer 1

正規表現は、グラフと考えることができるDFAに変換可能です。このDFAグラフを指定して文字列を生成するには、開始状態から終了状態までのパスを見つけるだけです。サイクルをどのように処理したいのか考える必要があります（毎回少なくとも1回はサンプリングしてn回サンプリングします）が、なぜうまくいかないのか分かりません。

Answer 2

実装する最も簡単な方法は、間違いなくCPU時間の集中的なアプローチですが、単純にそれを強制的に強制することです。 文字列に含める文字を含む文字テーブルを設定し、文字列を順番に生成し、Regex.IsMatchを実行します。

Answer 3

私は個人的に、これがreg-exの聖杯であると信じています。あなたがこれを実装することができれば - たとえ3/4の作業であっても - 私はあなたが約5分で裕福になることは間違いありません。

私は冗談を言っていますが、あなたが本当に追いかけていることは実現可能かどうかはわかりません。 Reg-Exは非常にオープンでフレキシブルな言語であり、必要なものを真に正確に見つけるためにコンピュータに十分なサンプル入力を与え、おそらく実行可能ではありません。

私が間違っていることが判明した場合、私はその開発者に名誉を与えたいと思います。

これを別の観点から見ると、これは出力されたコンピュータを与え、それに基づいてプログラムを作成するようなものではありません。これは少し外に出ていますが、それは私の要点を示しています。

Answer 4

これは、直接正規表現の抽象構文木を歩いたりDoug McIlroyで説明したように、最初のNFAに変換することによってtraversing the DFA（擬似コードを含んでいる）か、他で行うことができますpaperとHaskell code。 （彼はより速く進むためにNFAのアプローチを見つけましたが、DFAと比較しませんでした）

これらはすべてバックリファレンスのない正規表現、すなわちPerl正規表現ではなく実際の正規表現で動作します表現。追加のPerl機能を処理するには、ポストフィルタに追加するのが最も簡単です。

追加：code for this、Python、Peter Norvigと私が作成しました。

Answer 5

このutility on UtilityMillは、いくつかの簡単な正規表現を置き換えます。それはthis example from the pyparsing wikiに基づいています。可能文字列に一致しない正規表現を書くことが自明できるので

[A-EA] 
[A-D]* 
[A-D]{3} 
X[A-C]{3}Y 
X[A-C]{3}\(
X\d 
foobar\d\d 
foobar{2} 
foobar{2,9} 
fooba[rz]{2} 
(foobar){2} 
([01]\d)|(2[0-5]) 
([01]\d\d)|(2[0-4]\d)|(25[0-5]) 
[A-C]{1,2} 
[A-C]{0,3} 
[A-C]\s[A-C]\s[A-C] 
[A-C]\s?[A-C][A-C] 
[A-C]\s([A-C][A-C]) 
[A-C]\s([A-C][A-C])? 
[A-C]{2}\d{2} 
@|TH[12] 
@(@|TH[12])? 
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9]))? 
@(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9])|OH(1[0-9]?|2[0-9]?|30?|[4-9]))? 
(([ECMP]|HA|AK)[SD]|HS)T 
[A-CV]{2} 
A[cglmrstu]|B[aehikr]?|C[adeflmorsu]?|D[bsy]|E[rsu]|F[emr]?|G[ade]|H[efgos]?|I[nr]?|Kr?|L[airu]|M[dgnot]|N[abdeiop]?|Os?|P[abdmortu]?|R[abefghnu]|S[bcegimnr]?|T[abcehilm]|Uu[bhopqst]|U|V|W|Xe|Yb?|Z[nr] 
(a|b)|(x|y) 
(a|b) (x|y) 

Answer 6

、と私は一致する文字列が必要とする計算のための正規表現を記述することも可能であると考えている。このプログラムのテストケースがありますすべての長さの文字列を網羅的に検索するには、おそらく答えを求める際に上限が必要です。