5

DFA ベースの正規表現マッチャー内で「単語境界」マッチを実装したいと考えています。誰かがこれがどのように行われるか教えてもらえますか?

背景を説明すると、現在「dk.brics.automaton」ライブラリを使用していますが、アサーション (\b単語境界など) をサポートしていません。私の主な目標は実際に正規表現の同等性を判断することであり、実際のマッチングを行うことではないため、DFA ベースのエンジンを使用する必要があります。

さらに、次の質問に対する回答は、これが可能であることを示しているようです: DFA ベースの正規表現マッチング - すべての一致を取得する方法は? 言うことによって

「ここでも、特別な命令を含むイプシロン遷移をシミュレーターに追加することでこれを管理します。アサーションがパスした場合、状態ポインターは続行されます。それ以外の場合は破棄されます。」

しかし、これが何を意味するのか、私にはよくわかりません。エンドポイントを見て、そのエンドポイントがアサーションを満たす場合にのみトラバースできる特別なタイプのイプシロン遷移でのみ実行できることを示唆していますか、または何らかの方法で構成された「通常の」イプシロン遷移で実行できますか? これらの「特別な」タイプのイプシロン遷移が必要な場合、これらをどのように決定できますか (つまり、標準の DFA に変換できますか)?

これを実際に実装する方法の説明へのポインタは大歓迎です。

4

1 に答える 1

1

純粋な DFA 実装を使用してルックアラウンド型の正規表現エンジンを実行することはできません。以前に見たものを追跡する必要があるため、パターン マッチングを行うためにメモリ内にコンテキストを保持する別の獣にエンジンを作成します。

正規表現エンジンがこれを処理するには、すでに解析されたもののコンテキストを調べる特別な遷移が必要になることを意味します。このコンテキストは破棄されるため、通常の DFA ではこれを行うことができません。ちなみに、これはキャプチャ グループが遅い理由でもあり、(.*)something(.*)一部のエンジンではマッチングが非常に遅い理由でもあります。これは、このコンテキストを保持するために大量の文字をバッファにコピーするためです。

問題を解決するために、結果として得られる 2 つの DFA を最小化し、それらが等しいかどうかを確認しようとしていると思います。状態最小化アルゴリズムを実行するときに、各「特別な」遷移を一意であり、それ自体と等しい遷移とのみマージ可能として処理する場合、これは依然として達成可能です。

于 2012-04-19T10:52:01.940 に答える