アトミックグループ化、または一歩下がらない！

0.ふり

特定の王国、特定の状態では、プログラマーがいました。 予想通り、彼の名前はイヴァンでした。 彼は真の専門家であり、プログラマーの三大美徳すべてを所有していました。つまり、彼は怠け者で、rog慢で、焦りました。 その王国で大きな悲しみが起こりました：危機。 そして、彼らは退職金なしでVanyaを仕事から追い出した。 ヴァニャは長い間悲しみ、勇気を出し、世界中に履歴書を送りました。 どのくらいの時間、簡潔に、彼らはインタビューのためにVanyaに電話をかけました。 申請者には多くの要件がありましたが、主なことは、彼が正規表現の良いコマンドを持っている必要があるということでした。 インタビューの1か月近く前です。準備はしたくありません。 真面目な人であるため、Ivanは詳細に準備することにしました。 3週間と3日間、彼はストーブの上に横たわり、Habrを読み、必然的に徹底的に準備する方法を考えました。 インタビューの1日前。 Vanyushaは雇用主を精神的に呪いました。雇用主は面接をすぐに予定しているので、準備ができず、ストーブから降りてビール瓶を渡し、収益のためにレックスの本を買いました。 彼は彼が切断するまでそれを使い果たして読んだ。 朝、私たちはハブラカトの下のこの本に、枕の上にいるかのように、バニュシャの眠い人相が横たわっているのを見つけます。

1.再帰

インタビューで、イヴァンはそのような仕事を与えられました。 括弧（...）内の式と一致する正規表現を記述します。括弧内には、おそらく入れ子になった他の括弧内に多くの式がある場合があります。 例：チェーン内

sin(2*pi/tan(.7+b*tanh(b/2)))+8*cos(b/4)





正規表現は、ブラケットの最初のペアの内容と一致する（見つける）必要があります。

(2*pi/tan(.7+b*tanh(b/2)))





ただし、正規表現は、ブラケットのバランスが取れていないチェーンの部分と一致しないようにする必要があります（開いているブラケットは閉じず、逆にまったく開いていないブラケット）。 たとえば、チェーンの処理

(sin(b/2)





正規表現は(b/2)



見つける必要があります。1番目のブラケットは閉じないため、無視します。 そして次のチェーンで

2*pi)*(r*r





ここには「正しい」括弧のペアがないため、正規表現は何も見つける必要はありません。 もう1つの制限は、「空の」角かっこ()



に一致することを禁じていることです。つまり、角かっこ内に少なくとも一部のコンテンツが必要です。

つまり、括弧で囲まれた「正しい」式と一致する必要があります。これには、括弧付きの部分式が含まれる場合があり、空の括弧()



正しいとは見なされません。

イワンはおおよその表現を書き、口ひげを振る：

1）目的の表現は括弧で囲まれたものです。

2）角かっこ内には角かっこがないものがあり、すべてがシンプルです：

(3.14 * R * R)





...または括弧内の何か：

(2 * sin(pi/2))





やめて！ 後者の場合、括弧内には「括弧内の何か」ではなく、最初に「括弧なしの何か」 2 * sin



があり、それから「括弧内の何か」 (pi/2)



ます。

そして、括弧内に「括弧なしの何か」と「括弧内の何か」が何度も発生する可能性があることが明らかになります。

(2 * (a+8.5) * sin(pi/2) / (b - 1e-8))



。

正規表現言語で「角括弧なし」を設定するのは非常に簡単です： [^)(]+



。選択肢（角括弧なし、または角括弧内の何か）と「好きなだけ」を設定する方法も簡単です：メタキャラクター|および+ 「かっこ内の何か」と正規表現言語での記述方法

「カッコ内の何か」...「カッコ内の何か」...すでに出会った場所...ああ、ここ：ポイント

1）目的の表現は括弧内の何かです。 この「括弧内の何か」とは何ですか？ 探している式が括弧で囲まれている場合、括弧で囲まれているのは...探している式です！ ユーレカ！

そのような文法はイヴァンに起こります：

検索式:: = （ {式のない括弧|検索式} + ）

+は「1回以上」を意味します。{a | b}は「aまたはb」を意味し、太字の括弧は括弧自体の文字を意味し、

かっこなしの式:: =かっこ以外の任意の文字+

つまり、目的の式の定義は再帰的です。 しかし、正規表現の言語でそれを書く方法は？ 正規表現に自分自身を含めることはできますか？ イヴァンはそれは不可能だと思っていたでしょうが、あなたは忘れていました-彼は一ヶ月間一生懸命準備をしていました！ 彼は、現代の正規表現エンジンではこれが可能であることを想起しました：正規表現内のどこでも

(?R)





正規表現全体へのリンクを意味します。 Ivanは次の正規表現を記述します（/ xスイッチを使用すると、改行を含むすべての空白文字が考慮されず、＃文字の後のコメントも可能になります）。

/

\( #

(

[^)(]+ # --

| #

(?R) #

)+ # 1

\) #

/x







Ivanは、チェーンのいくつかの例を使用して正規表現をチェックします（良い、インタビューでテストプログラムを実行できます。オンラインでドキュメントを読むことはできません）。

there are no parentheses here





(a + b)





sin((pi/180)*deg + theta)





1+(1+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1))))))))))))





sin)a - b(





sin(a - b(





sin(a * (b+1)





そして、正規表現はそれらすべてを期待通りに処理します。 満足し、イヴァンは面接官に決定を示します。 ハッピーエンド、カーテン？ しかし、なぜ記事の名前はそのままですか??

インタビュアーは、次のチェーンで正規表現を検索する必要がある場合（必要な場合）を尋ねます。

(you're gonna fail sonny unless you correct it (your regex)





読んで青ざめたバニュシャは、瞬きすることなく、最初のブラケットがどこでも閉じていないので、正規表現はブラケットの2番目のペアを見つける必要があると答えます：（ (your regex)



。 彼は確認するように求められます。 Ivanはこのチェーンを検証スクリプト（Perl）に組み込みます。

#!/usr/bin/perl -wl

use strict;



my $string = "(you're gonna fail sonny unless you correct it (your regex)";

print $string;



if ( $string =~ / \( ( [^)(]+ | (?R) )+ \) /x ) {

print "Match: $&";

} else {

print "Not matched!"

}









構文を確認した後、Ivanはスクリプトを実行します...そして何も起こりません。スクリプトは「フリーズ」しているようです。 彼はイエスでもノーでもないと言っています。 イヴァンとインタビュアーは約10秒間静かに見ますが、この間、イヴァンは淡いピンクから淡いピンクに変わります。 しかし、彼は何を間違えたのですか?? この時点で、スクリプトが起動された（そして何らかの理由でまだ完了していない）ラップトップは、それまで静かに動作していましたが、はっきりと騒ぎ始めます。 面倒な長時間の一時停止を中断するために、インタビュアーはイヴァンにお茶またはコーヒーを提供します。 「その間、あなたはただ何が間違っているのかを考えます」と彼は付け加えます。 さらに30分が経過すると、Ivanはコーヒー2杯とレモン入り紅茶1杯を飲みますが、スクリプトがなぜ神秘的に振る舞うのかはわかりません。 インタビュアーはイヴァンと別れ、皇帝司祭の人事部の従業員は「候補者はインタビューの結果に応じて却下された」と記している。 そして、ポイントに行きます

2.壊滅的なロールバック

正規表現Ivanはどうなりましたか？ 正規表現の仕組みを理解してみましょう

/ \( ( [^)(]+ | (?R) )+ \) /x





「運命のない」チェーン

(you're gonna fail sonny unless you correct it (your regex)

1. 正規表現の中括弧は、チェーン内のブラケットと一致します
2. [^)(]+
   
   
   
   一致you're gonna fail sonny unless you correct it
   
   
   
   、 you're gonna fail sonny unless you correct it
   
   
   
   、「食べる」ことができない開始ブラケットに「静止」しyou're gonna fail sonny unless you correct it
   
   
   
   なります
3. 代替（... | ...）は、貪欲な量指定子+とともに使用されるため、正規表現エンジンは（... | ...）を再度検索しようとします。 最初の分岐[^)(]+
   
   
   
   開始ブラケットを見た直後の選択肢（「一致できません」と言う
4. エンジンは2番目の選択肢(?R)
   
   
   
   ます。 これは最初は正規表現全体です。 そして、チェーン内に残ってい(your regex)
   
   
   
   。 すべてが単純です：ブラケット（正規表現内はブラケットと一致（チェーン内、 [^)(]+



your regex
   
   
   
   と一致[^)(]+
   
   
   
   代替のその他の出現（... | ...）エンジンはチェーンの残りの部分では検出しません。かっこなし」、開き括弧）、エンジンは正規表現の閉じ括弧）に移動します。チェーン内の括弧）と一致します。
5. さて、エンジンは何とか元のチェーン(your regex)
   
   
   
   部分(?R)
   
   
   
   
6. チェーンでは、文字が残っていませんでした。 （... | ...）+の量指定子は貪欲で、正規表現エンジンは別の代替（... | ...）を見つけようとしますが、成功しません：チェーンの残りの空の部分では、何も見つかりませんブラケット、ブランチ(?R)
   
   
   
   を開始できる開始ブラケットなし
7. したがって、もう1つの選択肢は見つかりません。 まあ、すべての欲は境界を持たなければなりません。 エンジンは「コンテンツ」であり、チェーン内ですでに2つの選択肢が見つかっており、正規表現の次の部分に進みます。 これは右大括弧です）。 ただし、チェーンにはブラケットはありません。チェーンでは、現時点ではまったく空です。正規表現の以前の部分は既にマウント解除されています。 開き括弧を正規表現と一致させるものは何もありません。
8. 正規表現エンジンをさらに進化させるものは何ですか？ 降伏し、一致がないと言いますか？ まさか。 彼は、数量詞[^)(]+
   
   
   
   を使用した最後の表現が貪欲であり、正規表現の次の部分に何も残さずに「食べ過ぎ」た可能性があることを覚えています。正規表現エンジンはロールバックします。
9. エンジンは、前回[^)(]+



your regex
   
   
   
   チェーンを「食べた」ことを思い出しました。 [^)(]+
   
   
   
   強制的に1文字xを正規表現の次の部分[^)(]+
   
   
   
   「与え」ます。つまり、チェーンは残ります： x)
   
   
   
   正規表現では、代替（... | ...）+
10. K. +は貪欲であるため、エンジンは別の1つの代替（... | ...）を見つけようとします。代替の最初のブランチ[^)(]+
    
    
    
    、 x
    
    
    
    記号は素晴らしく一致します。チェーンに残っています。

これは非常に長い間続けることができますが、実際には、問題がすでに表面化しています。これは悪の根源であり、正規表現の欠陥です。 チェーン内で、人間の観点から括弧なしの1つの不可分なトークンである正規表現エンジンで、正規表現エンジンは2つのトークンを検出しました：正規表現[^)(]+



の「異なるコピー」に分散されたyour rege



およびx



ソース正規表現：

/ \( ( [^)(]+ | (?R) )+ \) /x





すべてが「余分」で、チェーン内の記号「）」または「（」の存在を必要とするものすべて（そして、正規表現チェーンには明らかにこれらの記号がありません）、残っているものはすべて：

/ ( [^)(]+ )+ /x





そして、ここで問題はさらに明白になります。 結局、 your regex



はyour regex



1トークンとして、正規表現とx



2トークンとして、そして、 you



とr regex



として、3、4、...、または10個の個別トークンとしてプレイできます。 your regex



チェーンをトークンに分割your regex



オプションの数は膨大です。 正規表現/ ( [^)(]+ )+ /x



は、必要に応じて、これらのオプションをすべて列挙することを意味します。 テストチェーンをチェックするときにすぐにIvanがこの問題に気付かなかったのはなぜですか？ その場合、通常の運がありました：チェーンを壊すためのオプションの数は膨大でしたが、破壊の最初のバリエーション（[^）（] +、貪欲で、全体として括弧なしでテキスト全体をキャプチャするとき）が成功したことが判明したため、正規表現エンジンはロールバックする必要がありませんでした 。 インタビュアーによって与えられたチェーンの場合、長い文字列をトークンに分割する1番目、2番目、100,000,000番目のオプションのいずれも一致しなかったため、すべてが悪化しました。そうではありませんでした。 そのため、後者の場合、正規表現エンジンはロールバックし、ますます多くの分割オプションを試行しますが、妥当な時間内に一致を見つけることはありません。 これは壊滅的なプルバックと呼ばれます。

3.原子のグループ化

この問題を防ぐことはできますか？ はい、非常に簡単です。 問題は、「愚かな」正規表現エンジンがギリシャ語のカレンダーにロールバックされるのに対し、人が理解するのは一見しかないことです。ロールバックは役に立たないことです。 your regex



（およびチェーンの前の部分）を部分に分割することは、不足している閉じ括弧を見つけるのに役立ちません。 正規表現エンジンに伝える方法があります：「これが完全一致の欠如につながる場合でも、この場所でロールバックを試みないでください。」

(?> .....)





これは「アトミックグループ化」と呼ばれ、おおよそ「 (?>



と)



間の正規表現の部分では、ロールバックは禁止されています」という意味(?>



。 または、より正確には、別の方法で。 (?>X)



Xは正規表現A(?>X)B



より大きい正規表現A(?>X)B



一部とします（AとBも何らかの正規表現です）。 文字列ab



をこの大きな正規表現の入力に送信します。ここで、aとbは単一の文字ではなく、文字のチェーンです。 大きい正規表現の最初の部分Aが、チェーンaの対応（「otmatchil」）をすでに見つけたとします。 正規表現エンジンは正規表現（？> X）に進み、処理されたチェーンでは、文字ポインターはチェーンaの直後（およびbの直前）に続きます。 この場合、アトミックグループ化（？> X）は、チェーンbが絶対に独立した独立した正規表現Xに適用されたかのように機能します。 Xは「知らない」ので、彼の後に他の正規表現Bがあるかどうか、Bが何かをプレイできるかどうかは気にしません。 Xは、彼以外にrexeが存在しないかのように動作します。 特に、Xに貪欲な量指定子が含まれている場合：

(?> [^)(]+ )





アトミックグループは、この「貪欲な」部分のロールバックを許可しません。 your regex



チェーン全体をすぐにキャプチャした場合は、1つ前のステップではなく、そうしてyour regex



！

括弧内のテキストを見つけるために正規表現を変更すると、問題が解決します。

/ \( (?> [^)(]+ | (?R) )+ \) /x







記事Super-greedy quantifiersで 、数量詞++、* +などを調べました。super-greedy数量詞はアトミックグループの特殊なケースであることがわかります。 また、元の正規表現の量指定子を超欲張りにすることで、同じ効果を得ることができます（壊滅的なロールバックを取り除きます）。

/ \( ( [^)(]++ | (?R) )+ \) /x





またはそれ以上

/ \( ( [^)(]++ | (?R) )++ \) /x







それが物語の終わりであり、誰が聞いたのか...著者に悲しませてください。著者は、記事を書く前に、説明が非常に長く不完全であることさえ考えられませんでした。 しかし、誰かが何かを理解し、バニャの経験を繰り返さなかった場合、それはすでに何か価値があります。