質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.80%

正規表現の位置と否定先読み

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 957

aaaaaaaa

score 481

<b>billions<b>zillions</b>という文字列に対して<b>((?!</?b>).)*?</b>という正規表現を使うと、
以下のような動作で合っておりますか。

また※1は、前者が合っているのでしょうか。それとも「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗する後者が成功するのでしょうか。

カレントステート(▲)…正規表現を今まさに試みている位置。
△…正規表現を試みる開始位置。マッチしたところから始まる。
保存ステートリスト…

試されていない選択肢を再開するための正規表現内での位置と文字列内での位置の両方を反映したもの(詳説正規表現第三版154p)

  • △▲<b>billions<b>zillions</b> ▲<b>((?!</?b>).)*?</b>
    …まず「<、b、>」にマッチする。
  • △<b>▲billions<b>zillions</b> <b>▲((?!</?b>).)*?</b>
    …が、非貪欲的な*?があるので「b」が((?!</?b>).)*?にマッチするかどうか調べないので飛ばすが、何かあったときのために、保存ステートリストに「△<b>▲billions<b>zillions</b> <b>▲((?!</?b>).)*?</b>」を保存。保存後、正規表現のカレントステートが一個先にずれる。
  • △<b>▲billions<b>zillions</b> <b>((?!</?b>).)*?▲</b>
    …「b」と「<」は、マッチしない。正規表現が失敗したので保存ステートリストに保存しておいたやつのなかで、最も末尾にあたるものを使う。
  • △<b>▲billions<b>zillions</b> <b>▲((?!</?b>).)*?</b>
    ※1…「b」とまだ読んでいない先に</b>或いは<b>が無くてかつ、任意の一文字が0文字以上、という正規表現は、マッチする。
  • △<b>b▲illions<b>zillions</b> <b>((?!</?b>).)*?▲</b>
    …非貪欲的な*?があるので、「i」が((?!</?b>).)*?にマッチするかどうか調べないで飛ばす。しかし「i」と「<」は、マッチしないので予め保存しておいた「△<b>b▲illions<b>zillions</b> <b>▲((?!</?b>).)*?</b>」を実行する。もちろんマッチする。残りの「l、l、i、o、n、s」までは、「b、i」と同じように処理が行われマッチする。
    ※1…否定先読みの効果で一気に二個目の<b>まで飛ばされるのか、任意の一文字を意味する.にマッチする「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗するのかがわからない。一応下記では、後者を採る。
  • △<b>billions▲<b>zillions</b> <b>▲((?!</?b>).)*?</b>
    …「l、l、i、o、n、s」のときと同じく非貪欲なので飛ばす。「△<b>billions▲<b>zillions</b> <b>▲((?!</?b>).)*?</b>」を保存。
  • △<b>billions▲<b>zillions</b> <b>((?!</?b>).)*?▲</b>
    …「<」と「<」は、マッチするが、「b」と「/」がマッチしないので失敗。
    保存していたものを実行する。
  • △<b>billions▲<b>zillions</b> <b>▲((?!</?b>).)*?</b>
    まだ読んでいない先に「<、b、>」があるのでマッチ不成立となる。保存しているものもないので、正規表現を試みる開始位置△の位置でのマッチは、失敗。
  • <△▲b>billions<b>zillions</b> ▲<b>((?!</?b>).)*?</b>
    …「b」と「<」はマッチしないのでこの位置でも失敗。以降、「>、b、i、l、l、i、o、n、s」も失敗し、正規表現を試みる開始位置△、カレントステートとともに2個目の<b>の前の位置までくる。
  • <b>billions△▲<b>zillions</b> ▲<b>((?!</?b>).)*?</b>
    …「<、b、>」は、「<b>」にマッチする。
  • <b>billions△<b>▲zillions</b> <b>▲((?!</?b>).)*?</b>
    …先述の通り、非貪欲なので「z」が((?!</?b>).)*?にマッチするかどうかを調べないで飛ばす。
    「<b>billions△<b>▲zillions</b> <b>▲((?!</?b>).)*?</b>」を保存。もちろん「z」と「<」はマッチしないので保存していたものを処理する。
  • <b>billions△<b>▲zillions</b> <b>▲((?!</?b>).)*?</b>
    …「z」と((?!</?b>).)*?は、マッチする。
  • <b>billions△<b>z▲illions</b> <b>▲((?!</?b>).)*?</b>
    …「z」のときと同じく非貪欲なので「i」と「<」を比べるがマッチしない。保存していた「<b>billions△<b>z▲illions</b> <b>▲((?!</?b>).)*?</b>」
    を使う。マッチする。以後、「l、l、i、o、n、s」まで同じことを繰り返す。
  • <b>billions△<b>zillions▲</b> <b>▲((?!</?b>).)*?</b>
    …「<、b、>」がマッチするかどうか調べるが、非貪欲なので飛ばす。失敗してもよいように、「<b>billions△<b>zillions▲</b> <b>▲((?!</?b>).)*?</b>」を保存。
  • <b>billions△<b>zillions▲</b> <b>((?!</?b>).)*?▲</b>
    …マッチ。
  • <b>billions△<b>zillions</b>▲ <b>((?!</?b>).)*?</b>▲
    …正規表現の末尾まで来たので終了。
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • ikedas

    2017/02/15 21:32

    実際にやってみた結果はどちらだったのでしょうか。

    キャンセル

回答 1

checkベストアンサー

+1

(3/2加筆)

※1…否定先読みの効果で一気に二個目の<b>まで飛ばされるのか、任意の一文字を意味する.にマッチする「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗するのかがわからない。

まず、正規表現の構成方法について説明します。

ある表現を元に新しい表現を作る方法は、3つあります。

  • 連接
    表現Aと表現Bがあるとき、表現ABは「Aがマッチする文字列の後にBがマッチする文字列が続く」ということを意味します。
  • 選択
    表現Aと表現Bがあるとき、表現A|Bは「Aがマッチする文字列か、Bがマッチする文字列」を意味します。
  • 量化
    表現Aがあるとき、表現A*A+はそれぞれ「Aがマッチする文字列が0回以上続く」「Aがマッチする文字列が1回以上続く」ということを意味します。
    またA?A{m,n}はそれぞれ「Aがマッチする文字列が0回以上1回以下続く」「Aがマッチする文字列がm回以上n回以下続く」ということを意味します。
    他の量指定子*?+???{m,n}?なども同様です。

部分表現をまとめるために括弧を使ったりもしますが、原理的には上の3つの方法を組み合わせることで、ある正規表現から新しい正規表現を作れます。

次に、貪欲な量指定子と非貪欲な量指定子の挙動について説明します。

量指定子が貪欲であることを、以前のご質問の回答では「できるだけ長くマッチしようとすること」、裏を返せば「できるだけ短くマッチしないようにすること」だと説明しました。

具体的には、表現ABがあるとき、A*Bは次のような動作をすることになります。

  1. 最初はAがマッチする文字列のできるだけ多くの回数の繰り返しにマッチする。
  2. 次に、Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の1回少ない繰り返しのマッチを再試行する。
  3. 次に、Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の2回少ない繰り返しのマッチを再試行する。
    ……
    ……
  4. 最後に、BがマッチすればA*B全体がマッチに成功。

これにより表現A*Bは、「Aがマッチする文字列の最大回数の繰り返しのあとにBがマッチするが続く」を意味することになります。

非貪欲であることはこの逆なので、「できるだけ短くマッチしようとすること」、裏を返せば「できるだけ長くマッチしないようにすること」であると考えることができます。

具体的には、表現ABがあるとき、A*?Bは次のような動作をすることになります。

  1. 最初はAがマッチする文字列の0回の繰り返し (空文字列) にマッチする。
  2. 次に、Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の1回の繰り返しのマッチを再試行する。
  3. 次に、Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の2回の繰り返しのマッチを再試行する。
    ……
    ……
  4. 最後に、BがマッチすればA*?B全体がマッチに成功。

これにより表現A*?Bは、「Aがマッチする文字列の最小回数の繰り返しのあとにBがマッチする文字列が続く」を意味することになります。

次に、量指定子の適用のされかたについて説明します。

((?!</?b>).)*?はあくまでも、「(?!</?b>).に量指定子*?が適用されている」(量化されている) という表現です。

()*?の内部のマッチの結果によってバックトラックや再試行がとばされる、といったことはありません。


『詳説 正規表現 第3版』では、非貪欲な量指定子の挙動を??についてしか詳しく説明していないようです。この??の場合は、「最初はマッチをとばしておき、失敗したら1回のマッチを試す」という見かたもできます。

しかし上述の通り、一般に他の非貪欲な量指定子の*?+?{…,…}?には「とばす」という見かたは当てはまらないです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/02/28 19:52

    ご回答有難うございます。

    >>具体的には、表現AとBがあるとき、A*?Bは次のような動作をすることになります。
    表現AとB…というのは、文字列「AB」を正規表現「A*?B」で処理をする、ということでしょうか。

    >>次に、量指定子の適用のされかたについて
    つまり、「「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗する…」というのは合っているということでしょうか。

    >>『詳説 正規表現 第3版』では、非貪欲な量指定子の挙動を??についてしか詳しく説明していないようです。
    非常に勉強になります。てっきり??以外も飛ばしてから失敗すれば保存ステートリストに保存していた保存ステートを実行するのだと思っておりました。
    つまり、??以外の非貪欲な量指定子たちは、貪欲な量指定子と動作が同じ、ということですよね。
    貪欲な量指定子の動きというのは、マッチするか確かめるが、失敗してもよいように正規表現の方を一つすすめ、文字列とマッチするかどうかというバックトラックを保存する、というものです。

    キャンセル

  • 2017/03/02 12:30

    回答に加筆しました。
    > つまり、「「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗する…」というのは合っているということでしょうか。

    「とばされる」ということはありえないので、それが正しい解釈でしょう。

    なお、もう少し簡単な例を工夫していただいたほうがいいと思います。ご提示の例を丹念に追って回答するのはかなり大変です。

    > つまり、??以外の非貪欲な量指定子たちは、貪欲な量指定子と動作が同じ、ということですよね。

    ??も動作は同じです。

    回答にも加筆しましたが、?や??は「0回以上1回以下続く」という意味です。*や*?は「0回以上続く」、+や+?は「1回以上続く」、{m,n}は「m回以上n回以下続く」です。回数の下限と上限に違いがあるだけです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.80%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る