与えられた正規表現に一致するランダムシーケンスを生成する

Question

任意の正規表現を持つ任意の正規表現と一致する（または一致しない）ランダムなテキストシーケンスを生成するにはどうすればよいですか？私は理論と実用両方に興味があります（.NETの文脈でテストを改善するためにこれが必要です）ので、記事や既存の図書館へのリンクが評価されます。

Answer 1

純粋に理論的な観点から、正規表現は次のように基づいて構築されている合理的な言語、と同等です：

• {}（無言葉で言語）が合理的です。
• {a}（1つの単語が1文字の言語）は合理的です。
• LおよびMが2つの合理的な言語である場合、それらの和集合（LまたはMのいずれかの単語）が合理的です。
• LとMは、二つの合理的な言語である場合、その連結LMは（言葉はMからLから単語にワードを付加することによって構築された）にも合理的です。
• Lが合理的な言語である場合、L*（言語Lの任意の数の単語を連結して構成される単語）も合理的です。

この建設的なアプローチは、正規表現の認識/照合アプローチを補完し、再帰的表現に一致する単語構築することができます：

• make({}) = ""
• make({a}) = "a"
• make(A|B) = flip-coin ? make(A) : make(B)
• make(AB) = make(A) + make(B)
• をmake(A*) = flip-coin ? "" : make(A) + make(A*)

Answer 2

すべての正規表現は、状態間の各遷移が1つ以上の文字を消費する有限状態機械で表現できると思います（または、ゼロ文字も有効ですか？Long私はこれを勉強して以来）。

これについては、正規表現を有限状態マシンに変換して変換し、状態から状態に移動して、有効な終了状態になるまでランダムに遷移を選択する方法があります。

もちろん、このメソッドが実際にどのように実行可能であるか、またはそのようなライブラリが存在するかどうかはわかりません。

http://lara.epfl.ch/dokuwiki/equivalence_of_finite_state_machine_and_regular_expression_languages

Answer 3

.NETではなく面白いかもしれませんが。見つけたthis implementation in Haskell。著者はCPAN Genexより強力であると主張しています。

Answer 4

.NETでは、プロジェクトFareを参照することもできます。それはまさにあなたが描いていることです。ここで

は、それを使用する方法である：

var xeger = new Xeger(pattern); 
var match = xeger.Generate(); 

Regex.IsMatch(match, pattern); 
// Prints -> true 

あなたはユニットテストを言及しているので、あなたも、あなたがプロパティ（またはフィールド）を飾るどの一度AutoFixtureを使用して検討すること[RegularExpression]と、それが割り当てられます属性正規表現に一致する値。

Answer 5

rxrdg - Regular Expression Random Data Generator。 C＃で書かれています。