http://swtch.com/~rsc/regexp/regexp1.htmlを読んだところ、著者は、正規表現で後方参照を行うには、照合時にバックトラッキングが必要であり、最悪の場合の複雑さが指数関数的になると述べています。しかし、後方参照によってバックトラッキングが必要になる理由が正確にはわかりません。誰かが理由を説明し、おそらく例 (正規表現と入力) を提供できますか?
質問する
3183 次
4 に答える
21
質問に直接答えるには、チョムスキー階層について簡単に学習する必要があります。これは、ますます複雑になる形式言語のセットを編成する古くて美しい方法です。階層の最下段は正規言語です。ご想像のとおり、RL はまさに「純粋な」正規表現で表すことができます。つまり、アルファベット、空の文字列、連結、代替 |、および Kleene star * (Ma を見てください) のみを持つものです。後方参照なし）。形式言語理論の古典的な定理 - クリーネの定理 - は、DFA、NFA (引用した記事で説明されているように)、および正規表現はすべて正確に言語を表現し認識する力と同じです。この記事で与えられた Thompson の構成は、定理の証明の一部です。
すべての RL は CFL でもあります。しかし、規則的でない CFL は無数にあります。複雑すぎて規則的ではない CFL に存在する可能性のある機能は、バランスのとれた一対のものです: 括弧、begin-end ブロックなどです。ほぼすべてのプログラミング言語が CFL です。CFL は、プッシュダウン オートマトンと呼ばれるものによって効率的に認識できます。これは基本的に、スタックが接着され た NFAです。スタックは必要に応じて大きくなるため、有限のオートマトンではなくなります。実際のプログラミング言語のパーサーは、ほぼすべてがプッシュダウン オートマトンのバリエーションです。
後方参照のある正規表現を検討してください
^(b*a)\1$
aつまり、これは n 番目と 2n 番目の文字の両方がであり、他のすべての文字がである n に対して長さ 2n の文字列を表しますb。これは、規則的でない aa CFL の完璧な例です。これは、ポンピング補題と呼ばれる別のクールな形式言語ツールを使用して厳密に証明できます。
これこそが、後方参照が問題を引き起こす理由です。それらは、正規ではない言語を表す「正規表現」を許可します。したがって、それらを認識できる NFA や DFA はありません。
しかし、待ってください、私がこれまでに作ったよりもさらに悪いです. 検討
^(b*a)\1\1$
これで、長さ 3n の文字列ができました。ここで、n 番目、2n 番目、および 3n 番目の要素はaであり、他のすべての要素はbです。この言語が複雑すぎて CFL ではないことの証明を可能にするポンピング補題の別のフレーバーがあります。これを認識できるプッシュダウン オートマトンはありません。
後方参照により、これらの強化された正規表現は、チョムスキー階層の 3 段上にある言語 (コンテキスト依存言語) を表すことができます。大まかに言えば、CSL を認識する唯一の方法は、同じ長さの言語のすべての文字列をチェックすることです (少なくとも P!=NP の場合ですが、これはすべての実用的な目的と別の話に当てはまります)。そのような文字列の数は、一致する文字列の長さで指数関数的です。
これが、検索正規表現マッチャーが必要な理由です。検索を設計する方法を非常に賢くすることができます。しかし、指数関数的な時間を要する何らかの入力が常に存在します。
したがって、あなたが引用した論文の著者に同意します。ほぼすべての入力に対して効率的に認識される後方参照なしの完全に無害な正規表現を作成することは可能ですが、Perl、Java、または Python の正規表現マッチャーを引き起こす入力が存在する場合は、バックトラッキング検索であるため、数百万を必要とします。試合を完了するまでの年数。狂ってる。正しく、何年も問題なく動作するスクリプトを作成した後、ある日、不適切な入力の 1 つに出くわしたという理由だけでロックすることがあります。あなたが乗っている飛行機のナビゲーションシステムのメッセージパーサーに正規表現が埋め込まれているとします...
編集
a^k b a^k b要求があれば、言語が正規でないことを証明するためにポンピング補題を使用する方法をスケッチします。これは繰り返しa^kの省略形です。PL は、正の整数 N が存在しなければならないので、少なくとも N の長さの正規言語のすべての文字列は、RS^k T がすべての自然な k の言語にもあるような RST の形式でなければならないと述べています。ここで、、は文字列であり、空にすることはできません。akRSTS
PL の証明は、すべての正規言語が何らかの DFA に対応するという事実に依存します。状態の数 (補題の L に等しい) よりも長いこの DFA への受け入れられた入力は、状態を繰り返すために「ループ:」を引き起こす必要があります。この状態を X と呼びます。マシンは文字列 R を消費して最初から X に到達し、次に S を消費して X にループバックし、次に T を消費して受け入れ状態に到達します。入力に S の余分なコピーを追加する (または S を削除する) ことは、X から X への異なる数の「ループ」にのみ対応します。したがって、S の追加の (または削除された) コピーを含む新しい文字列も受け入れられます。 .
すべての RL は PL を満たさなければならないため、言語が正則でないことの証明は、PL と矛盾することを示すことによって進められます。私たちの言語では、これは難しくありません。a^k b a^k b言語 L = PL を満たすことを私に納得させようとしているとします。そのため、N (上記を参照) の値、つまり L を認識する仮想 DFA 内の状態の数を指定できる必要があります。文字列 B= a^N b a^N b." L が通常の場合、B はこの DFA を (どのように見えても) 最初の N 文字内でループさせなければなりません。これはすべてas でなければなりません! したがって、ループ（上記の文字列 S）はすべてで構成されていますaも。これにより、L が正則であるというあなたの主張が誤りであることをすぐに示すことができます。もう一度ループを回ることを選択します。これにより、この架空の DFA が新しい文字列 を受け入れるようになります。ただし、前半に sa^M b a^N bを追加したため、M>Nです。a痛い！この新しい文字列は L にはないため、PL は結局真ではありません。あなたが提供したNに関係なく、私は毎回このトリックを実行できるため、PLはLに対して保持できず、Lは結局正規化できません.
それは規則的ではないため、クリーネの定理は、それを記述する DFA も FA も「純粋な」正規表現も存在しないことを示しています。
後方参照が文脈自由でさえない言語を許可するという証明には、非常に似たリングがありますが、ここでは説明しないプッシュダウン オートマトンの背景が必要です。Google が提供します。
注: これらは両方とも、後方参照が認識 NP を完全にするという証明には達していません。彼らは、後方参照が純粋な正規表現に真の複雑さを加えると非常に厳密な方法で言っているだけです。それらは、有限のメモリを持つマシンや、無限大の LIFO メモリしか持たないマシンでは認識できない言語を許可します。NP完全性証明は他の方にお任せします。
于 2012-06-29T02:05:51.320 に答える
10
NFA と DFA は有限オートマトン、別名有限状態マシンであり、「有限数の状態の 1 つになることができる抽象マシン」[1]です。有限数の状態に注意してください。
リンクされた記事、Regular Expression Matching Can Be Simple And Fastで説明されている高速な NFA/DFA アルゴリズムは、この記事で説明されているように (入力の長さに関係なく)有限数の状態で動作できるため、高速です。
後方参照を導入すると、状態の数が (ほぼ) 「無限」になります (最悪の場合、約 256 n ( nは入力の長さ))。すべての後方参照のすべての可能な値がオートマトンの状態になるため、状態の数が増えます。
したがって、有限状態マシンを使用することはもはや適切ではなく、不可能であり、代わりにバックトラッキング アルゴリズムを使用する必要があります。
于 2012-06-19T23:32:23.310 に答える
4
このチュートリアルにはいくつかの優れた例があります:
http://www.regular-expressions.info/brackets.html
興味のある特定のケースは、「キャプチャ グループへのバックトラック」に示されています。正規表現全体に一致する最終的な一致が見つかる前に、一致全体が数回放棄される方法が説明されています。また、これにより予期しない一致が発生する可能性があることに注意してください。
于 2012-06-19T15:03:02.973 に答える
2
非常に興味深いドキュメント: Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions、後方参照をサポートし、変更された NFA を使用して効率的に出現回数を数えます。
于 2012-08-01T21:00:20.963 に答える