regex - *+ 量指定子は正確には何をしますか?

Question

怠惰と貪欲の考え方は理解しやすいですが、怠惰な修飾子がStackOverflowエラーを引き起こしたときに機能したという理由だけで、（ *+Javaの）正規表現（[A]|[^B]*+(?!C)A、B、Cは任意の値）で一度だけ見たり使用したりしました。

ほとんどの検索エンジンはシンボルを検索できないため、これに関するドキュメントは見つかりません。では、*+ は正確に何をし、どのように行うのでしょうか?

Answer 1

貪欲な量指定子は可能な限りすべてに一致し、パターンは一致が成功するまでバックトラックします。

遅延量指定子は、一致が成功するまで追跡します。

所有量指定子は、可能なすべてのものに一致し、バックトラックすることはありません。

は+所有量指定子を表します。たとえば、++またはとして使用できます*+。

バックトラッキングを防止するこの機能は、壊滅的なバックトラッキングを阻止できることを意味します。

Answer 2

他の回答が指摘しているように*+、「所有量指定子」です。貪欲な量指定子のように、前の要素にできるだけ多く一致しますが、バックトラックすることはありません。

なぜこれが役立つのですか？パフォーマンスの最適化としてのみ。さらに、正規表現が一致しない場合のパフォーマンスの最適化としてのみ。これは、正規表現を理解する上で重要な点です。正規表現の最悪の場合のパフォーマンスは、一致しない場合に常に発生します。

使用している正規表現エンジンと正規表現自体の詳細によっては、最悪の場合のパフォーマンスが驚くほど悪い場合があります。簡単な例として、この正規表現を取り上げます:a*a*a*bは、この文字列: と照合されますaaaaac。

この状況に直面すると、標準の「NFA」タイプの正規表現エンジンは次のようになります。

1. a1回目の5回、2回目のa0回、3回目の0回を合わせてみてくださいa。
2. と を照合してみてくださいb--c失敗します。
3. 「バックトラック」して、1回目aは4回、2回目は1回、3回目は0回マッチ。
4. もう一度照合してみてくださいb-- 失敗します。
5. もう一度バックトラックして、1 回目aを 4 回、2 回目を 0 回、3 回目を 1 回試行します。
6. ...
7. バックトラックして、最初のa3 回、2 回目の 2 回、3 回目の 0 回を試してください...

(次の数百ステップは自分で記入できると思います。)

正規表現が の場合a*+a*a*b、それは決して起こりません。それはもっと似ています：

1. a1回目の5回、2回目の0回、3回目の0回を合わせてみてください。
2. -- を一致させてみてくださいb。失敗します。
3. 1つ目aは「憑依」なので、一度5回マッチすると、それ以下の回数でマッチングを試みることはできません。またa、他の s が一致する文字列には s が残っていないため、 a*0 回しか一致できません。試行するものが残っていないため、一致全体が失敗します。
4. ステップ 4 はありません。友達が正規表現の実行が完了するのを待っている間、あなたはかかとを蹴って、お好みの冷たい飲み物を割って開けることができます。

Answer 3

X*+ は X を意味し、0 回以上 (所有格)

所有量指定子は常に入力文字列全体を消費し、1 回 (1 回だけ) 一致を試みます。貪欲な量指定子とは異なり、所有量指定子は、たとえそうすることで全体的な一致が成功したとしても、決して後退しません。