正規表現に一致するすべての文字列を生成するストリームまたは反復子？

Question

これはmy previous questionのフォローアップです。

すべての正規表現と一致する文字列を生成したいとします。

これは単なるコーディング練習であり、追加の要件はありません（たとえば、生成される文字列の数は実際には）。だから、主な要件は、いい、クリーンでシンプルなコードを生成することです。

私はStreamを使用することを考えましたが、this questionを読んだ後、私はIteratorと考えています。何を使用しますか？

Answer 1

この質問に対する解決策は、ここで答えが現実的であるためにはあまりにも多くのコードを要求しますが、概要は次のようになります。

まず、正規表現を解析する必要があります。たとえば、これについてパーサーコンビネータを調べることができます。むしろマッチャーとして、この式ツリーを実行するよりも、例えば、

List(
    Constant("abc"), 
    ZeroOrOne(Constant("d")), 
    Constant("efg"), 
    OneOf(Constant("h"),List(Constant("ij"),ZeroOrOne(Constant("klmnop")))), 
    Constant("qrs"), 
    AnyChar() 
) 

をのように見える評価ツリーを持っているあなたは、その後、あなたはそれぞれの上に生成する方法を定義することにより、発電として、それを実行することができます期間。一部の用語（例：ZeroOrOne(Constant("d"))）には複数のオプションがあるため、イテレータを定義できます。これを行う1つの方法は、各用語に内部状態を格納し、「前進」フラグまたは「リセット」フラグを渡すことです。 「リセット」で、ジェネレータは最初の可能なマッチ（たとえば""）を返します。事前にそれは次のものに進み、その前のフラグを消費しながら（例えば、"d"）、残りのフラグはフラグなしで評価されます。それ以上のアイテムがない場合は、内部のすべてのアイテムに対してリセットを生成し、次のアイテムのために進行フラグをそのまま残します。あなたはリセットで走って起動します。それぞれの反復で、あなたは進歩を入れて、それをもう一度出すときに止める。

もちろん、"d+"のようないくつかの正規表現構文は、無限に多くの値を生成する可能性がありますので、何らかの方法で制限することをお勧めします（または、ある時点では "lots"を意味するd...dを返します）。他のものには非常に多くの値があります（例えば、.は任意のcharにマッチしますが、本当にすべての64k文字が必要ですか？また、多くのUnicodeコードポイントがありますか？）。

とにかく、これは時間がかかりますが、発電機が動作します。また、解析されたツリーの各部分に対してマッチルーチンを書く場合は、あたかも作業正規表現マッチャーを持つことになります。