質問: billionszillionsという文字列に対して`((?!?b>).)*?`という正規表現を使うと、 以下のような動作で合っておりますか。 また※1は、前者が合っているのでしょうか。それとも「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗する後者が成功するのでしょうか。 カレントステート(▲)...正規表現を今まさに試みている位置。 △...正規表現を試みる開始位置。マッチしたところから始まる。 保存ステートリスト... > > 試されていない選択肢を再開するための正規表現内での位置と文字列内での位置の両方を反映したもの(詳説正規表現第三版154p) > > > * △▲billionszillions ▲((?!?b>).)*? ...まず「<、b、>」にマッチする。 * △▲billionszillions ▲((?!?b>).)*? ...が、非貪欲的な`*?`があるので「b」が`((?!?b>).)*?`にマッチするかどうか調べないので飛ばすが、何かあったときのために、保存ステートリストに「△▲billionszillions ▲((?!?b>).)*?」を保存。保存後、正規表現のカレントステートが一個先にずれる。 * △▲billionszillions ((?!?b>).)*?▲ ...「b」と「<」は、マッチしない。正規表現が失敗したので保存ステートリストに保存しておいたやつのなかで、最も末尾にあたるものを使う。 * △▲billionszillions ▲((?!?b>).)*? ※1...「b」とまだ読んでいない先に或いはが無くてかつ、任意の一文字が0文字以上、という正規表現は、マッチする。 * △b▲illionszillions ((?!?b>).)*?▲ ...非貪欲的な`*?`があるので、「i」が`((?!?b>).)*?`にマッチするかどうか調べないで飛ばす。しかし「i」と「<」は、マッチしないので予め保存しておいた「△b▲illionszillions ▲((?!?b>).)*?」を実行する。もちろんマッチする。残りの「l、l、i、o、n、s」までは、「b、i」と同じように処理が行われマッチする。 ※1...否定先読みの効果で一気に二個目のまで飛ばされるのか、任意の一文字を意味する`.`にマッチする「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗するのかがわからない。一応下記では、後者を採る。 * △billions▲zillions ▲((?!?b>).)*? ...「l、l、i、o、n、s」のときと同じく非貪欲なので飛ばす。「△billions▲zillions ▲((?!?b>).)*?」を保存。 * △billions▲zillions ((?!?b>).)*?▲ ...「<」と「<」は、マッチするが、「b」と「/」がマッチしないので失敗。 保存していたものを実行する。 * △billions▲zillions ▲((?!?b>).)*? まだ読んでいない先に「<、b、>」があるのでマッチ不成立となる。保存しているものもないので、正規表現を試みる開始位置△の位置でのマッチは、失敗。 * <△▲b>billionszillions ▲((?!?b>).)*? ...「b」と「<」はマッチしないのでこの位置でも失敗。以降、「>、b、i、l、l、i、o、n、s」も失敗し、正規表現を試みる開始位置△、カレントステートとともに2個目のの前の位置までくる。 * billions△▲zillions ▲((?!?b>).)*? ...「<、b、>」は、「」にマッチする。 * billions△▲zillions ▲((?!?b>).)*? ...先述の通り、非貪欲なので「z」が`((?!?b>).)*?`にマッチするかどうかを調べないで飛ばす。 「billions△▲zillions ▲((?!?b>).)*?」を保存。もちろん「z」と「<」はマッチしないので保存していたものを処理する。 * billions△▲zillions ▲((?!?b>).)*? ...「z」と`((?!?b>).)*?`は、マッチする。 * billions△z▲illions ▲((?!?b>).)*? ...「z」のときと同じく非貪欲なので「i」と「<」を比べるがマッチしない。保存していた「billions△z▲illions ▲((?!?b>).)*?」 を使う。マッチする。以後、「l、l、i、o、n、s」まで同じことを繰り返す。 * billions△zillions▲ ▲((?!?b>).)*? ...「<、b、>」がマッチするかどうか調べるが、非貪欲なので飛ばす。失敗してもよいように、「billions△zillions▲ ▲((?!?b>).)*?」を保存。 * billions△zillions▲ ((?!?b>).)*?▲ ...マッチ。 * billions△zillions▲ ((?!?b>).)*?▲ ...正規表現の末尾まで来たので終了。
回答: (3/2加筆) > > ※1...否定先読みの効果で一気に二個目のまで飛ばされるのか、任意の一文字を意味する.にマッチする「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つの方法を組み合わせることで、ある正規表現から新しい正規表現を作れます。 次に、貪欲な量指定子と非貪欲な量指定子の挙動について説明します。 量指定子が**貪欲**であることを、以前のご質問の回答では「できるだけ長くマッチしようとすること」、裏を返せば「できるだけ短くマッチしないようにすること」だと説明しました。 具体的には、表現`A`と`B`があるとき、`A*B`は次のような動作をすることになります。 1. 最初は`A`がマッチする文字列のできるだけ多くの回数の繰り返しにマッチする。 2. 次に、`B`がマッチしなければバックトラックが起きる。`A`がマッチする文字列の1回少ない繰り返しのマッチを再試行する。 3. 次に、`B`がマッチしなければバックトラックが起きる。`A`がマッチする文字列の2回少ない繰り返しのマッチを再試行する。 ...... ...... 4. 最後に、`B`がマッチすれば`A*B`全体がマッチに成功。 これにより表現`A*B`は、「`A`がマッチする文字列の最大回数の繰り返しのあとに`B`がマッチするが続く」を意味することになります。 **非貪欲**であることはこの逆なので、「できるだけ短くマッチしようとすること」、裏を返せば「できるだけ長くマッチしないようにすること」であると考えることができます。 具体的には、表現`A`と`B`があるとき、`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回のマッチを試す」という見かたもできます。 しかし上述の通り、一般に他の非貪欲な量指定子の`*?`、`+?`、`{...,...}?`には「とばす」という見かたは当てはまらないです。