0

だから私は正規表現パターンを持っており、そのパターンから許可されるすべてのテキスト順列を生成したいと考えています。

例：

var pattern = "^My (?:biological|real)? Name is Steve$";
var permutations = getStringPermutations(pattern);

これにより、以下の文字列のリストが返されます。

私の名前はスティーブです

私の本当の名前はスティーブです

私の生物学的名前はスティーブです

更新: 明らかに、正規表現には無限の数の一致があるため、(?:biological|real)? のようにオプションの文字列リテラルからのみ生成したいだけです。上記の私の例から。(.)* のようなものは一致が多すぎるため、そこから生成することはありません。

4

3 に答える 3

1

両端が固定され、リテラルテキスト、1文字のワイルドカード、および交互にのみ含まれる正規表現のサブセットに制限する場合、一致する文字列は非常に簡単に列挙できます。おそらく正規表現をBNF文法として書き直し、それを使用して一致する文字列の完全なリストを生成します。あなたの例のために：

<lang>   -> <begin> <middle> <end>
<begin>  -> "My "
<middle> -> "" | "real" | "biological"
<end>    -> " name is Steve"

RHSに終端記号しかないプロダクションから始めて、LHSの非終端記号がとることができるすべての可能な値を列挙します。次に、RHSの非終端記号を使用したプロダクションに進みます。非終端記号を連結するには、各RHS非終端記号で表されるセットのデカルト積を作成します。交互に、各オプションで表されるセットの和集合を取ります。まで作業を終えるまで続けてください<lang>。そうすれば完了です。

ただし、「*」または「+」演算子を含めると、一致する文字列の数が無限になるのを防ぐ必要があります。また、後方参照などの高度な機能も処理したい場合は、停止性問題と同型の何かに向かっている可能性があります。

于 2009-10-08T00:17:13.827 に答える
0

少し奇妙かもしれない 1 つの方法は、最初に可能な選択肢を配列に入れ、次に配列に基づいて正規表現を生成し、次に同じ配列を使用して順列を生成することです。

于 2009-10-08T00:08:49.833 に答える