正規表現をNFAに変換するための優れたライブラリはありますか？私はこの主題に関する多くの学術論文を目にします。それらは役に立ちますが、コードの動作にはあまり影響しません。
私の質問は、部分的には好奇心によるものであり、部分的には、私が取り組んでいる本番システムでの正規表現マッチングを高速化する実際の必要性によるものです。学習のためにこの主題を探求するのは楽しいかもしれませんが、それがパターンマッチングを高速化するための「実用的な」解決策であるかどうかはわかりません。私たちはJavaショップですが、どの言語の優れたコードへのポインターも喜んで受け取ります。
編集：
興味深いことに、Javaの正規表現がすでにNFAであることを知りませんでした。この論文のタイトルは、私がそうではないと信じるように導きました。ちなみに、現在Postgresで正規表現のマッチングを行っています。単純な解決策がマッチングをJavaコードに移動することである場合、それは素晴らしいことです。
正規表現を高速化する必要性に対処する:
Java の正規表現エンジンの実装は、NFA ベースです。そのため、正規表現を調整するには、エンジンがどのように実装されているかをより深く理解することが有益であると言えます。
正規表現をマスターするこの本では、NFA エンジンに固有の正規表現を調整する方法など、NFA エンジンとそれがどのように一致を実行するかについて実質的に説明しています。
さらに、正規表現を調整するためにAtomic Groupingを調べてください。
免責事項: 私は Java+regexes の専門家ではありません。でも、正しく理解すれば…
Java の正規表現マッチャーが他のほとんどの正規表現マッチャーと似ている場合、NFA を使用しますが、期待する方法とは異なります。聞いたことがあるかもしれない前方のみの実装の代わりに、部分式の一致を簡素化するバックトラッキング ソリューションを使用しており、おそらく Backreference の使用に必要です。ただし、交替性能は悪い。
あなたが見たい：http ://swtch.com/~rsc/regexp/regexp1.html （この変更されたアーキテクチャでうまく機能しないエッジケースに関して）。
私はまた、同じことに帰着すると思われる質問を書きました：
機械生成の正規表現を処理できる正規表現の実装: *非バックトラッキング*, O(n)?
しかし、基本的には、すべての一般的な主要ベンダーの正規表現の実装は、特定の正規表現で使用すると、不要であるにもかかわらず、非常に奇妙な理由でパフォーマンスが低下するようです。