DFA正規表現マッチャーを使用して正規表現アサーション/ルックアサイン（\ bスタイルの単語境界）を実装する方法

Question

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

私は現在、「dk.brics.automaton」ライブラリを使用していますが、アサーションをサポートしていません（例：\b、単語境界）。私はDFAベースのエンジンを使用する必要があります。なぜなら、私の主な目標は実際に正規表現の等価性を判断することであり、実際のマッチングを行わないからです。

さらに、次の質問への答えはこれが可能であることを示しているようだ： DFA based regular expression matching - how to get all matches?

を言っては「ここでも、シミュレータに特別な指示をイプシロン遷移を追加することで、これを管理する場合。アサーションが成功すると、状態ポインタは継続し、それ以外の場合は破棄されます。

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

実際にこれを実装する方法の説明へのポインタは、大いに感謝しています。

Answer 1

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

これを処理する正規表現エンジンでは、既に解析済みのコンテキストを見る特別な遷移が必要であることを意味します。このコンテキストが破棄されるため、通常のDFAではこれを実行できません。ちなみに、キャプチャグループが遅く、この文脈を維持するために多くの文字をバッファにコピーするので、一部のエンジンでは(.*)something(.*)が致命的に遅くなります。

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