最新の正規表現エンジンには、その機能なしでは照合できなかった言語を照合できる機能がいくつかあります。たとえば、後方参照を使用する次の正規表現は、繰り返される単語で構成されるすべての文字列の言語に一致します: (.+)\1. この言語は正規表現ではないため、後方参照を使用しない正規表現とは一致しません。
ルックアラウンドは、正規表現で照合できる言語にも影響しますか? つまり、ルックアラウンドを使用して一致させることができ、他の方法では一致できなかった言語はありますか? もしそうなら、これはルックアラウンドのすべてのフレーバー (否定的または肯定的な先読みまたは後読み) に当てはまりますか、それともそれらの一部だけに当てはまりますか?
通常の言語よりも大きなクラスの言語が、ルックアラウンドによって拡張された正規表現で認識できるかどうかという質問に対する答えは、いいえです。
証明は比較的簡単ですが、ルックアラウンドを含む正規表現をルックアラウンドを含まない正規表現に変換するアルゴリズムは面倒です。
まず、正規表現はいつでも否定できることに注意してください (有限のアルファベットに対して)。式によって生成された言語を認識する有限状態オートマトンが与えられた場合、すべての受け入れ状態を非受け入れ状態と交換するだけで、その言語の否定を正確に認識する FSA を取得できます。これには、同等の正規表現のファミリがあります。 .
2 番目: 正規言語 (したがって正規表現) は否定の下で閉じているため、de Morgan の法則によって A が B = neg ( neg(A) union neg(B)) と交差するため、交差の下でも閉じられます。つまり、2 つの正規表現が与えられた場合、両方に一致する別の正規表現を見つけることができます。
これにより、ルックアラウンド式をシミュレートできます。たとえば、u(?=v)w は、uv と uw に一致する式のみに一致します。
否定先読みの場合、集合論的 A\B に相当する正規表現が必要です。これは、A の交差 (neg B) または同等の neg (neg(A) union B) です。したがって、任意の正規表現 r および s について、s に一致しない r に一致する式に一致する正規表現 rs を見つけることができます。否定的な先読み用語: u(?!v)w は、uw - uv に一致する式のみに一致します。
ルックアラウンドが役立つ理由は 2 つあります。
1 つ目は、正規表現を否定すると、整頓されていない結果になる可能性があるためです。たとえばq(?!u)=q($|[^u])。
第二に、正規表現はマッチ表現以上のことを行い、文字列から文字を消費します - または少なくともそれが私たちがそれらについて考えるのが好きな方法です. たとえば、python では、もちろん .start() と .end() を気にします。
>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4
第三に、これはかなり重要な理由だと思いますが、正規表現の否定は連結よりもうまくいきません。neg(a)neg(b) は neg(ab) と同じではありません。つまり、ルックアラウンドを見つけたコンテキストから翻訳することはできません。つまり、文字列全体を処理する必要があります。それは、人々が正規表現を扱うのを不快にし、人々の正規表現に対する直感を壊すことになると思います。
私はあなたの理論的な質問に答えたことを願っています（夜遅くなので、不明な場合はご容赦ください）。これには実用的なアプリケーションがあると述べたコメンテーターに同意します。非常に複雑な Web ページをスクレイピングしようとしたときに、まったく同じ問題に遭遇しました。
編集
明確になっていないことをお詫びします。正規表現の規則性と構造帰納法によるルックアラウンドの証明を提供できるとは思いません。私の u(?!v)w の例は、まさにその例であり、簡単なものでしたその時。構造誘導が機能しない理由は、ルックアラウンドが非構成的な方法で動作するためです。これは、上記の否定について私が言おうとしていた点です。直接的な正式な証明には、多くの厄介な詳細が含まれると思います。私はそれを示す簡単な方法を考えようとしましたが、私の頭の上からそれを思いつくことができません.
Josh の最初の例を使用して説明する^([^a]|(?=..b))*$と、すべての状態が受け入れられる 7 つの状態の DFSA と同等です。
A - (a) -> B - (a) -> C --- (a) --------> D
Λ | \ |
| (not a) \ (b)
| | \ |
| v \ v
(b) E - (a) -> F \-(not(a)--> G
| <- (b) - / |
| | |
| (not a) |
| | |
| v |
\--------- H <-------------------(b)-----/
状態 A のみの正規表現は次のようになります。
^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$
言い換えれば、ルックアラウンドを排除することによって取得しようとしている正規表現は、一般に、はるかに長く、はるかに厄介になります。
Josh のコメントへの回答 - はい、同等性を証明する最も直接的な方法は FSA を使用することだと思います。これをより複雑にしているのは、FSA を構築する通常の方法が非決定論的マシンを使用することです。u|v を、u と v のマシンから構築されたマシンとして、それらの 2 つへのイプシロン遷移を使用して単純に表現する方がはるかに簡単です。もちろん、これは決定論的なマシンと同等ですが、状態が指数関数的に爆発するリスクがあります。一方、否定は決定論的マシンを介して行う方がはるかに簡単です。
一般的な証明では、2 つのマシンのデカルト積を取得し、ルックアラウンドを挿入する各ポイントで保持する状態を選択します。上記の例は、私が言いたいことをある程度示しています。
構造を提供していないことをお詫び申し上げます。
さらに編集: ルックアラウンドで拡張された正規表現から DFA を生成するアルゴリズムを説明するブログ投稿を 見つけました。著者が「タグ付きイプシロン遷移」を使用して NFA-e のアイデアを明白な方法で拡張し、そのようなオートマトンを DFA に変換する方法を説明しているため、それは素晴らしいことです。
そのような方法があると思いましたが、誰かがそれを書いてくれてうれしいです. こんなにきちんとしたものを思いつくのは私を超えていました。
他の回答が主張するように、ルックアラウンドは正規表現に特別な力を追加しません。
これは、次のように示すことができると思います。
1 つの小石 2-NFA (それを参照する論文の概要セクションを参照してください)。
1-pebble 2NFA はネストされた先読みを処理しませんが、複数の Pebble 2NFA の変形を使用できます (以下のセクションを参照)。
序章
2-NFA は非決定論的な有限オートマトンであり、入力に対して左または右に移動することができます。
ワン ペブル マシンは、マシンが入力テープにペブルを配置し (つまり、特定の入力記号をペブルでマークする)、現在の入力位置にペブルがあるかどうかに基づいて異なる遷移を行うことができる場所です。
One Pebble 2-NFA は、通常の DFA と同じパワーを持つことが知られています。
ネストされていない先読み
基本的な考え方は次のとおりです。
2NFA を使用すると、入力テープを前後に移動してバックトラック (または「フロント トラック」) することができます。したがって、先読みのために、先読み正規表現の照合を行い、先読み表現の照合で、消費したものをバックトラックできます。バックトラックを停止するタイミングを正確に知るために、小石を使用します。バックトラッキングを停止する必要がある場所をマークするために、先読みのために dfa に入る前に小石を落とします。
したがって、小石の 2NFA を介して文字列を実行する最後に、先読み式と一致したかどうかがわかり、残りの入力 (つまり、消費されるために残っているもの) は、残りのものと一致するために必要なものです。
したがって、形式 u(?=v)w の先読みについては
u、v、w の DFA があります。
u の DFA の受け入れ状態 (はい、1 つしかないと仮定できます) から、v の開始状態に e-transition を作成し、入力を小石でマークします。
v の受け入れ状態から、小石が見つかるまで入力を左に移動し続ける状態に e-transtion し、その後 w の開始状態に遷移します。
v の拒否状態から、小石を見つけるまで左に移動し続ける状態に e-遷移し、u の受け入れ状態 (つまり、中断した場所) に遷移します。
通常の NFA で r1 | を示すために使用される証明。r2、または r* などは、これら 1 つの小石 2nfas に対して繰り越されます。コンポーネント マシンを組み合わせてより大きなマシンにする方法の詳細については、http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsaを参照してください。 r* 式など
上記の r* などの証明が機能する理由は、繰り返しのためにコンポーネント nfas を入力したときに、バックトラッキングによって入力ポインターが常に正しい場所にあることが保証されるためです。また、pebble が使用されている場合は、先読みコンポーネント マシンの 1 つによって処理されています。先読みマシンから先読みマシンへの移行は、完全にバックトラックして小石を取り戻さなければならないため、1 台の小石マシンで十分です。
たとえば、 ([^a] | a(?=...b))* を考えてみましょう
および文字列abbb。
a(?=...b) の peb2nfa を通過する abbb があり、その最後に次の状態になります: (bbb、一致) (つまり、入力 bbb が残っており、「a」と一致しています) '..b' が続きます)。* があるので、最初に戻り (上のリンクの構造を参照)、[^a] の dfa を入力します。b に一致し、最初に戻り、[^a] を 2 回入力して受け入れます。
ネストされた先読みの処理
入れ子になった先読みを処理するために、ここで定義されているように k-pebble 2NFA の制限付きバージョンを使用できます:双方向オートマトンとマルチペブル オートマトンの複雑さの結果とそのロジック(定義 4.1 と定理 4.2 を参照)。
一般に、2 pebble オートマトンは非正則集合を受け入れることができますが、次の制限により、k-pebble オートマトンは正則であることを示すことができます (上の論文の定理 4.2)。
小石が P_1、P_2、...、P_K の場合
P_i が既にテープ上にない限り、P_{i+1} を配置することはできず、P_{i+1} がテープ上にない場合を除き、P_{i} をピックアップすることはできません。基本的に小石は LIFO 方式で使用する必要があります。
P_{i+1} が配置されてから、P_{i} がピックアップされるか P_{i+2} が配置されるまでの間に、オートマトンは P_{i} の現在の位置の間にあるサブワードのみをトラバースできます。 P_{i+1} の方向にある入力単語の末尾。さらに、このサブワードでは、オートマトンは Pebble P_{i+1} を持つ 1-pebble オートマトンとしてのみ機能します。特に、別の小石を持ち上げたり、配置したり、その存在を感知したりすることは許可されていません。
したがって、v が深さ k のネストされた先読み式である場合、(?=v) は深さ k+1 のネストされた先読み式です。先読みマシンに入ると、これまでに置かれた小石の数が正確にわかっているため、どの小石を配置するかを正確に決定でき、そのマシンを出るときに、どの小石を持ち上げるかがわかります。深さ t のすべての機械は、小石 t を置くことによって入り、小石 t を取り除くことによって出ます (つまり、深さ t-1 の機械の処理に戻ります)。完全なマシンの実行は、ツリーの再帰的な dfs 呼び出しのように見え、マルチ ペブル マシンの上記の 2 つの制限に対応できます。
式を組み合わせると、rr1 について、連結するため、r1 の小石の数は r の深さだけインクリメントする必要があります。r* と r|r1 の小石の番号付けは同じままです。
したがって、先読みを使用した任意の式は、小石の配置に上記の制限がある同等の複数小石マシンに変換できるため、規則的です。
結論
これは基本的に、フランシスの元の証明の欠点に対処します: 先読み式が将来の一致に必要なものを消費するのを防ぐことができます。
後読みは単なる有限文字列 (実際には正規表現ではない) であるため、最初にそれらを処理し、次に先読みを処理できます。
不完全な記述で申し訳ありませんが、完全な証明には多くの図を描く必要があります.
私には正しいように見えますが、間違いがあれば喜んでお知らせします（私はそれが好きなようです:-)）。
ルックアラウンドが規則的であるという他の投稿には同意します (つまり、正規表現に基本的な機能を追加しないことを意味します)。
DFA 構造を提供することで、ルックアラウンドが規則的であることを示します。言語を認識する DFA がある場合にのみ、その言語は規則的です。Perl は実際には内部で DFA を使用しないことに注意してください (詳細については、このペーパーを参照してください: http://swtch.com/~rsc/regexp/regexp1.html ) が、証明の目的で DFA を構築します。
正規表現の DFA を構築する従来の方法は、最初に Thompson のアルゴリズムを使用して NFA を構築することです。2 つの正規表現フラグメントr1およびが与えられるとr2、トンプソンのアルゴリズムは、正規表現の連結 ( r1r2)、代替 ( r1|r2)、および反復 ( r1*) の構造を提供します。これにより、元の正規表現を認識する NFA を少しずつ構築できます。詳細については、上記の論文を参照してください。
正および負の先読みが規則的であることを示すために、正規表現uと正または負の先読みを連結する構造を提供します: (?=v)or (?!v). 連結のみが特別な処理を必要とします。通常の交互および反復構造は正常に機能します。
u(?=v) と u(?!v) の両方の構成は次のとおりです。
言い換えると、既存の NFA for のすべての最終状態をu受け入れ状態とNFA for の両方に接続vしますが、次のように変更します。関数f(v)は次のように定義されます。
aa(v)する NFA の関数とします。v反受け入れ状態は、NFA を通過するいずれかのパスが特定の string に対してこの状態で終了したs場合vに一致が失敗する原因となる状態であると定義されますs。loop(v)する NFA の関数とします。vつまり、パスが受け入れ状態につながると、そのパスはその後の入力に関係なく、受け入れ状態を永久に維持できます。f(v) = aa(loop(v)).f(v) = aa(neg(v)).これが機能する理由を直感的に説明するために(b|a(?:.b))+、フランシスの証明のコメントで私が提案した正規表現を少し簡略化した regex を使用します。従来の Thompson 構造と一緒に私の構造を使用すると、次のようになります。
はeイプシロン遷移 (入力を消費せずに取得できる遷移) であり、反受け入れ状態にはX. グラフの左半分には、(a|b)+: anyの表現が表示されているaかb、グラフを受け入れ状態にしますが、開始状態に戻る遷移も可能にするため、もう一度行うことができます。ただし、 a に一致するたびaに、グラフの右半分にも入ることに注意してください。ここでは、「any」の後にb.
従来の NFA には反受け入れ状態がないため、これは従来の NFA ではありません。ただし、従来の NFA->DFA アルゴリズムを使用して、これを従来の DFA に変換できます。アルゴリズムは通常のように機能し、DFA 状態を NFA 状態のサブセットに対応させることで NFA の複数回の実行をシミュレートします。1 つのひねりは、DFA 状態が（最終）状態を受け入れるかどうか。従来のアルゴリズムでは、NFA 状態のいずれかが受け入れ状態であった場合、DFA 状態は受け入れ状態になります。これを変更して、次の場合にのみ、DFA 状態が受け入れ状態であると言います。
= 1 NFA 状態は受け入れ状態であり、
このアルゴリズムは、先読みで正規表現を認識する DFA を提供します。したがって、先読みは定期的です。後読みには別の証明が必要であることに注意してください。
ここでは、2 つの明確な質問がされているように感じます。
実際的な意味での最初の質問に対する答えはイエスです。ルックアラウンドは、この機能を使用する正規表現エンジンに、そうでないエンジンよりも基本的に強力な機能を提供します。これは、マッチング プロセスのためのより豊富な「アンカー」セットを提供するためです。ルックアラウンドを使用すると、正規表現全体を可能なアンカー ポイント (ゼロ幅アサーション) として定義できます。ここで、この機能の威力のかなり良い概要を得ることができます。
ルックアラウンドは強力ですが、Type 3 Grammar によって設定された理論上の制限を超えて正規表現エンジンを持ち上げることはありません。たとえば、ルックアラウンドを備えた正規表現エンジンを使用して、コンテキスト フリー - タイプ 2 文法 に基づいて言語を確実に解析することはできません。正規表現エンジンは、Finite State Automationの能力に制限 されており、これにより、解析できる言語の表現力が Type 3 Grammar のレベルに制限されます。正規表現エンジンにいくつの「トリック」が追加されても、文脈自由文法によって生成される言語 常にその能力を超えたままになります。Parsing Context Free - タイプ 2 文法では、プッシュダウン オートメーションが再帰的な言語構造のどこにあるかを「記憶」する必要があります。文法規則の再帰的な評価を必要とするものは、正規表現エンジンを使用して解析できません。
要約すると、ルックアラウンドは正規表現エンジンにいくつかの実用的な利点を提供しますが、理論的なレベルで「ゲームを変更」することはありません。
編集
Type 3 (Regular) と Type 2 (Context Free) の間のどこかに複雑な文法がありますか?
答えはノーだと思います。その理由は、Regular 言語を記述するために必要な NFA/DFA のサイズに理論的な制限がないためです。任意に大きくなる可能性があるため、使用（または指定）するのは非現実的です。これは、「ルックアラウンド」などの回避が役立つ場所です。それらは、そうでなければ非常に大規模で複雑な NFA/DFA 仕様につながるものを指定する簡単なメカニズムを提供します。それらは正規言語の表現力を向上させるのではなく、それらを指定することをより実用的にするだけです。この点を理解すると、実用的な意味でより便利にするために正規表現エンジンに追加できる多くの「機能」があることが明らかになりますが、正規言語の限界を超えることができるようにするものは何もありません.
通常言語と文脈自由言語の基本的な違いは、通常言語には再帰要素が含まれていないことです。再帰言語を評価するには、再帰のどこにいるかを「記憶」するためのプッシュ ダウン オートメーションが必要です。NFA/DFA は状態情報をスタックしないため、再帰を処理できません。したがって、非再帰的な言語定義が与えられた場合、それを記述する NFA/DFA (ただし、必ずしも実用的な正規表現であるとは限りません) があります。