5

私はこれに似た非常に単純な正規表現を持っています:

HOHO.*?_HO_

このテスト文字列で...

fiwgu_HOHO_HOHO_HOHOrgh_HOHO_feh_HOHO___HO_fbguyev

  • 私はそれがちょうど一致することを期待しています_HOHO___HO_（最短一致、貪欲ではない）
  • 代わりに一致し_HOHO_HOHO_HOHOrgh_HOHO_feh_HOHO___HO_ます (最長一致、貪欲に見えます)。

なんで？最短一致に一致させるにはどうすればよいですか?

を追加および削除しても?、同じ結果が得られます。

編集[^HOHO]-機能しない理由を示すより良いテスト文字列:fiwgu_HOHO_HOHO_HOHOrgh_HOHO_feh_HOHO_H_O_H_O_HO_fbguye

私が考えることができるのは、複数回一致している可能性があるということだけです-しかし、 の一致は1つしかないため、で終わる最短の一致を取得せず、残りを破棄する_HO_理由がわかりません。_HO_

「貪欲でない正規表現は貪欲に振る舞う」などのタイトルで見つけられるすべての質問を閲覧しましたが、それらにはすべて他の問題があるようです。

4

3 に答える 3

11

Regex lazy vs greedy compilationの助けを借りて解決策を見つけました。

Javascript で使用されているような正規表現エンジン (私が信じているNFA エンジン) では、貪欲ではない場合、左から右への最短の一致のみが得られます。最初の左手一致から、最も近い右手一致に適合します。

1 つの右側の一致に対して左側の一致が多数ある場合は、常に最初に到達したものから開始されます (これにより、実際には最長の一致が得られます)。

基本的に、一度に 1 文字ずつ文字列を調べて、「この文字に一致するものはありますか? 一致する場合は、最も短いものに一致して終了します。ない場合は、次の文字に移動して繰り返します」と尋ねます。「この文字列のどこかに一致するものはありますか? もしそうなら、それらすべての中で最も短いものに一致します」と予想しました。

.を「左側の一致ではない」という意味の否定に置き換えることで、両方向で貪欲でない正規表現を近似できます。このような文字列を否定するには、否定先読みと非キャプチャ グループが必要ですが、文字列を にドロップするのと同じくらい簡単(?:(?!).)です。例えば、(?:(?!HOHO).)

たとえばHOHO.*?_HO_、左と右で貪欲でないものは次のようになります。

HOHO(?:(?!HOHO).)*?_HO_

したがって、正規表現エンジンは基本的に次のように各文字を処理します。

  • HOHO- これは左側に一致しますか?
  • (?:(?!HOHO).)*- もしそうなら、左側を繰り返さずに右側に到達できますか?
  • _HO_- もしそうなら、右手の試合まですべてをつかむ
  • ?*またはの修飾子+- 複数の右側の一致がある場合は、最も近いものを選択します
于 2014-12-09T18:15:29.760 に答える
5

なぜ文字列全体に一致するのですか?

これは、一致可能な文字列内の最初の位置を見つけることによって、正規表現パターン マッチングが行われるためです。文字列の最初の文字から始まる一致が可能であるため、後続の文字から始まる短い一致は考慮されません。

例:正規表現とテスト文字列を
考えてみましょう。文字列に適用すると、文字列全体に一致します。最後の&だけではありません。これは、一致が可能な文字列内の最初の位置が最初にあるためです。/a+?b/"aaaaaaaaab"aba

abしたがって、 で一致させたい場合は、遅延ドットではなく、否定された文字クラスaaaaaaaaabベースの正規表現を使用します。

a[^ab]*b

正規表現のデモを参照してください。

出典: Javascript: The Definitive Guide、第 6 版、ページ番号: 255

于 2014-12-10T11:06:47.260 に答える
4

の最初の出現からに到達HOHOするまでの最短一致であるため、結果は貪欲ではありません。_HO_エンジンは文字列を左から右にトラバースします。バックトラックする必要がないため、何も短縮しようとしません。

ここで期待される方法で動作させるには、式に貪欲な接頭辞を付ける必要があります。

/.*(HOHO.*?_HO_)/

最初のメモリ キャプチャには、目的の文字列が含まれています。貪欲な接頭辞は、できるだけ多くの文字をスキップしようとするため、最後に出現したHOHO最初の文字と一致します。

于 2014-12-10T11:03:41.320 に答える