特定の正規表現の実装がDFAまたはNFAに基づいているかどうかという問題に直面しています。
これを理解するための出発点は何ですか。次のように尋ねることもできます。何を探していますか? 基本的なパターンおよび/または特性は何ですか? 適切で説明的なリンクまたは少しの比較 (正規表現に直接専念していなくても) はまったく問題ありません。
2 に答える
4
それがブラック ボックスである場合は、NFS とバックトラッキング正規表現の実装に関するこの説明のグラフを参照して、いくつかの入力を与え、病理学的ケースでその時間特性を測定します。(NFS グラフは秒ではなくマイクロ秒であることに注意してください)。
また、それが純粋な NFA である場合、バックトラッキングを必要とするいくつかの「正規表現」パーサーである非正規の機能はありません。
または、RxParser クラスのドキュメントを参照してください。ドキュメントはウェブ上で入手できないようで、参照するには squeak ランタイムが必要です。
于 2011-11-25T13:12:29.570 に答える
2
アルゴリズムではなく「正規表現の実装」を意味していると思います（通常の意味で）。
いずれかのアプローチで問題を引き起こすことが知られている既知の式でテストできます。また、どちらか一方に実装しやすい機能を探しています (これは信頼できるアプローチではありません。正規表現エンジンの開発者は、以前は困難だったことを実装する新しい方法を見つけています)。
通常、答えはドキュメントを読むか、既知の参考文献を調べることです ( 「Mastering Regular Expressions」では、多くの一般的なケースについて説明しています)。最後に著者に聞いてみませんか？
于 2011-11-25T11:03:55.857 に答える