2

正規表現のようなものを使用して文字列内のパターンを見つけるツールを構築しようとしています (テキスト文字列ではありませんが、現時点では重要ではありません)。私はオートマトン理論に精通しています。つまり、基本的な正規表現マッチングを実装する方法を知っており、文字列が正規表現と一致する場合は、教科書の方法でオートマトンをシミュレートすることにより、true または false を出力します。

as の前に来るすべての s に興味があるとします。sの前にbs はもうありません。しかし、文字列にそのような部分が含まれているかどうかを確認したいだけではなく、出力として を取得して、それを検査できるようにしたい (実際にテキストを扱っているわけではないことを思い出してください)。aba[^a]*ba

a要約すると、次のように括弧でマークを付け(a)[^a]*bて、入力文字列で実行するとbcadacb、2番目の文字列が出力として必要になるとしましょうa。

または、より一般的には、入力文字列のどの文字が正規表現のどの部分に一致するかを見つけることができますか? テキストエディタではどのように行われますか? 一致を強調表示できるため、少なくとも一致が開始された場所がわかります。バックトラッキング アプローチを使用する必要がありますか? それとも、よりスマートで計算コストの低い方法がありますか?

編集: 適切な後方参照、つまり、括弧でキャプチャして \1 で参照するなどは必要ない場合があります。私は、後方参照がバックトラッキング (または同様のもの) の必要性を導入し、問題 (IIRC) を NP 困難にすることを知っています。私の質問は、本質的には次のとおりです。後方参照なしのキャプチャ部分は、適切な後方参照よりも計算コストが低くなりますか?

4

2 に答える 2

4

ほとんどのテキスト エディターは、バックトラッキング アルゴリズムを使用してこれを行います。この場合、一致する場所を記録するのは簡単です。

状態リストに括弧の位置情報を追加することで、直接的な NFA シミュレーションも実行できます。これは、線形時間保証を維持する方法で行うことができます。http://swtch.com/~rsc/regexp/regexp2.html#submatchを参照してください。

ティモスの答えは正しい軌道に乗っていますが、DFA 状態は可能な NFA 状態のコレクションに対応しているため、DFA 状態にタグを付けることはできません。そうでないことが判明した場合、それを事実として記録するのは正しくありません。代わりに、NFA シミュレーションに取り組む必要があります。

于 2012-07-19T11:39:01.367 に答える
1

照合用の DFA を作成したら、正規表現の左括弧の後の最初の州に対応するすべての州をマークします。そのような状態にアクセスすると、現在の入力文字のインデックスが保存されます。閉じ括弧に対応する状態にアクセスすると、インデックスも保存されます。受け入れ状態に達したら、2 つのインデックスを出力します。これがテキスト エディタで使用されるアルゴリズムかどうかはわかりませんが、それが私のやり方です。

于 2012-07-19T01:20:42.027 に答える