入力に正規表現または文字列があり、それを NFA に変換してから DFA に変換し、対応する最終 DFA の遷移表を実際に出力するアルゴリズムを探していました。
したがって、それを行うアルゴリズムまたは C または Python ライブラリが既に存在するかどうか、または使用するアルゴリズムの提案があれば、それを実装できるかどうか疑問に思っています。
ありがとうございました。
質問する
2956 次
1 に答える
2
これらのリンクのいずれかが役立つかどうかはわかりません。
1 つ目は、Python での非常に単純な NFA/DFA 実装を提供し、NFA から DFA への変換を行います。ただし、正規表現から NFA を生成するわけではありませんが、それほど難しくありません。2 番目のサイトでは、NFA と DFA に関する長い議論が提供されており、多数のコード例 (ほとんどが C) と、私がほとんど知らない外部ライブラリへのリンクが含まれています。3 番目と 4 番目のリンクは、正規表現から NFA への解析、NFA から DFA への変換を含む、2 番目の記事の著者によって開発された 2 つの正規表現エンジン実装のソース コードを提供します。ただし、これらのプロジェクトのいずれも見ていないことに注意してください。
- https://gist.github.com/Arachnid/491973
- http://swtch.com/~rsc/regexp/
- https://code.google.com/p/re1/source/browse/
- https://code.google.com/p/re2/source/browse/
そうでなければ、ほとんどの現実世界の正規表現エンジンは、DFA では実行できない拡張機能があるため、DFA ではなく NFA を使用していることに言及します。したがって、上記のリンクがどれも役に立たない場合は、実際に DFA を使用するコンパイラー コンパイラーを調べてみてください。
于 2013-10-24T21:47:17.050 に答える