正規表現の可能なすべての一致を生成する

正規表現を指定すると、正規表現が一致する文字列が生成されます。各文字列の最大長が存在するため、この集合は無限ではないことに注意することが重要です。これを実行するための既知のアルゴリズムはありますか？この問題の洞察を得るために読むことができる研究論文はありますか？正規表現の可能なすべての一致を生成する

ありがとうございました。

P.S.この種の問題は、理論的なcsスタック交換においてより適切であろうか？

私たちはまさにそれを行うCPANのモジュール持つPerlの世界では

出典

2011-07-10 Sam

まあ、我々はあなたが旗あなたの質問をすることができますし、MODを尋ねるので、理論CSに移動し、投票することはできませんが。 – BoltClock

すべての可能な文字列は、マッチで終わるステートマシンを通るすべての可能なパスに対応しています。しかし、これは私のプログラムの成果に合った限られた長さのプログラムをすべて私にお願いするようなものです。 – gtrak

各文字列の "最大長"と言うとき、正規表現に+演算子や*演算子が含まれていないことを意味しますか？ –

- >Regexp::Genex

出典

2011-07-10 21:38:47 average

ありがとうございます。私は先に進み、そのモジュールを使用するかもしれません。あなたはそのようなモジュールを実装する方法を議論するリソースを知っていますか？どのようにエレガントに/効率的に実装できるのか不思議でした。 – Sam

そのソースコードを確認してください。直感的に言えば、正規表現はオートマトンなので、グラフです。文字列に一致するすべての文字列を生成することは、「開始」ノードを開始し、オートマトンの「受け入れ」ノードで終了するすべてのパスを見つけることを意味するので、グラフ内のパスの列挙を意味するだけです。 – average

正規表現の可能なすべての一致を生成する

答えて

関連する問題