3

貪欲な正規表現がどのように実行されるかについて、2 つの異なる意見があることがわかりました。

  • 1つは、すべての入力文字列を読み取り、後ろからパターンを照合し、最初に入力全体に一致し、最初の試行は文字列全体です。この意見を支持するいくつかの記事は、Oracle の公式 Java チュートリアルです。

貪欲な量指定子は、最初の一致を試行する前に、マッチャーに入力文字列全体を読み込ませる、つまり食べることを強制するため、「貪欲」と見なされます。最初の一致試行 (入力文字列全体) が失敗した場合、マッチャーは入力文字列を 1 文字戻して再試行し、一致が見つかるか、元に戻す文字がなくなるまでプロセスを繰り返します。

この記事も参照してください:貪欲な正規表現と遅延正規表現の量指定子のパフォーマンス

  • もう 1 つは前方からのマッチングで、最初のマッチング試行は左側の 0 インデックスからです。一致が見つかった場合、エンジンは停止せず、失敗するまで残りを一致させ続け、その後バックトラックします。私が見つけたこの意見を支持する記事は次のとおりです。

スターとプラスの Looking Inside The Regex Engineセクションでの繰り返し<.+>:

正規表現の最初のトークンは < です。これはリテラルです。すでにわかっているように、一致する最初の場所は文字列の最初の < です。

知りたいのですが、どちらが正しいですか？これは、正規表現の効率に影響するため重要です。各言語で実装が異なるかどうかを知りたいので、さまざまな言語タグを追加しました。

4

4 に答える 4

3

それらが機能的に同等であると仮定すると（そして私のJava正規表現の使用に基づいて、それらは同等です）、エンジンの実装の違いにすぎません。正規表現は、すべての言語でまったく同じように実装されているわけではなく、使用する言語に基づいて多かれ少なかれ強力になる可能性があります。

2 番目のリンクは Perl について説明しているので、Java 側では Oracle を信頼します。

どちらも可能な最大の一致を取得しようとします。

キーを追加して量指定子を遅延させると、可能な限り最小の一致?が試みられます。

于 2012-06-14T15:18:31.440 に答える
0

異なるネット環境とプログラミング言語での正規表現の実装は同じである必要はないため、質問に対する正確な答えはありません。

Perlを使用する場合、正規表現の実装が非常に最適化されていることを知っておく必要があります。これは、このプログラミング言語の最も強力な機能の 1 つです。したがって、効率について心配する必要はありません:)

于 2012-06-14T15:25:26.123 に答える
0

違いはありません。「後ろから一致する」という意味もありません。最初の参照が「マッチャー」と言うとき、それは式全体ではなく、繰り返される正規表現アトムを意味します。つまり、/ab+/「abbot」と照合する場合、残りの文字列全体と一致しないことを先験的に知りません。Java チュートリアルでは、ストリームb+に対する正規表現マッチングの動作について説明している可能性があり、貪欲な繰り返しはストリームの残りを積極的に消費するのに対し、貪欲でない繰り返しは必要に応じてストリームを遅延的に消費することに注意してください。

于 2012-06-14T15:41:35.850 に答える
0

「マッチャーは入力文字列を 1 文字戻して再試行します」はバックトラッキングを説明しているだけなので、「その後バックトラックします」は同じことを言っています。貪欲に関するあなたの引用は両方とも同じことを言っているので、どちらも正しい. (あなたの 3 番目の引用は貪欲とは何の関係もありません。)

例を挙げましょう。

'xxabbbbbxxabbbbbbbbb' =~ /([ab]*)bb/;
  1. 位置0で試してください。
    1. [ab]*0 文字 "" に一致します。
      1. 位置 0 で、bb一致に失敗 ⇒ バックトラック。
    2. [ab]*これ以上一致することはありません ⇒ バックトラック。
  2. 位置 1 で試してください。
    1. [ab]*0 文字 "" に一致します。
      1. 位置 1 でbb一致に失敗 ⇒ バックトラック。
    2. [ab]*これ以上一致することはありません ⇒ バックトラック。
  3. pos 2 で試してください。
    1. [ab]*は 6 文字の " abbbbb" に一致します。
      1. 位置 8 でbb一致に失敗 ⇒ バックトラック。
    2. [ab]*5 文字の " abbbb" に一致します。(1つ後退)
      1. 位置 7 でbb一致に失敗 ⇒ バックトラック。
    3. [ab]*4 文字の " abbb" に一致します。(1つ後退)
      1. 位置 6 でbb一致します。
        1. 成功。

したがって、$1 は「abbb」です。（そうではありませんabbbbbbb。「貪欲」は「可能な限り長い一致」を意味するものではありません。）

では、"*" を非貪欲にするとどうなるか見てみましょう。

'xxabbbbbxxabbbbbbbbb' =~ /([ab]*?)bb/;
  1. 位置0で試してください。
    1. [ab]*?0 文字 "" に一致します。
      1. 位置 0 で、bb一致に失敗 ⇒ バックトラック。
    2. [ab]*これ以上一致できません ⇒ バックトラック。
  2. 位置 1 で試してください。
    1. [ab]*?0 文字 "" に一致します。
      1. 位置 1 でbb一致に失敗 ⇒ バックトラック。
    2. [ab]*これ以上一致できません ⇒ バックトラック。
  3. pos 2 で試してください。
    1. [ab]*?0 文字 "" に一致します。
      1. 位置 2 でbb一致に失敗 ⇒ バックトラック。
    2. [ab]*?1 文字 " a" に一致します。(1 つ追加)
      1. 位置 3 でbb一致します。
        1. 成功。

したがって、$1 は "a" です。

特定の実装では、ここに示したものと同じ結果が得られる限り、最適化として異なることを行う可能性があります。Perl の動作を次のように見ることができます。

perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*)bb/;'
perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*?)bb/;'
于 2012-06-14T17:23:46.660 に答える