Q&A
実際にやってみた結果はどちらだったのでしょうか。
<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>▲
…正規表現の末尾まで来たので終了。
回答1件
0
ベストアンサー
(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つの方法を組み合わせることで、ある正規表現から新しい正規表現を作れます。
次に、貪欲な量指定子と非貪欲な量指定子の挙動について説明します。
量指定子が貪欲であることを、以前のご質問の回答では「できるだけ長くマッチしようとすること」、裏を返せば「できるだけ短くマッチしないようにすること」だと説明しました。
具体的には、表現AとBがあるとき、A*Bは次のような動作をすることになります。
- 最初は
Aがマッチする文字列のできるだけ多くの回数の繰り返しにマッチする。 - 次に、
Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の1回少ない繰り返しのマッチを再試行する。 - 次に、
Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の2回少ない繰り返しのマッチを再試行する。
……
…… - 最後に、
BがマッチすればA*B全体がマッチに成功。
これにより表現A*Bは、「Aがマッチする文字列の最大回数の繰り返しのあとにBがマッチするが続く」を意味することになります。
非貪欲であることはこの逆なので、「できるだけ短くマッチしようとすること」、裏を返せば「できるだけ長くマッチしないようにすること」であると考えることができます。
具体的には、表現AとBがあるとき、A*?Bは次のような動作をすることになります。
- 最初は
Aがマッチする文字列の0回の繰り返し (空文字列) にマッチする。 - 次に、
Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の1回の繰り返しのマッチを再試行する。 - 次に、
Bがマッチしなければバックトラックが起きる。Aがマッチする文字列の2回の繰り返しのマッチを再試行する。
……
…… - 最後に、
BがマッチすればA*?B全体がマッチに成功。
これにより表現A*?Bは、「Aがマッチする文字列の最小回数の繰り返しのあとにBがマッチする文字列が続く」を意味することになります。
次に、量指定子の適用のされかたについて説明します。
((?!</?b>).)*?はあくまでも、「(?!</?b>).に量指定子*?が適用されている」(量化されている) という表現です。
(…)*?の内部のマッチの結果によってバックトラックや再試行がとばされる、といったことはありません。
『詳説 正規表現 第3版』では、非貪欲な量指定子の挙動を??についてしか詳しく説明していないようです。この??の場合は、「最初はマッチをとばしておき、失敗したら1回のマッチを試す」という見かたもできます。
しかし上述の通り、一般に他の非貪欲な量指定子の*?、+?、{…,…}?には「とばす」という見かたは当てはまらないです。
投稿2017/02/20 09:19
編集2017/03/02 02:17総合スコア4315
ご回答有難うございます。
>>具体的には、表現AとBがあるとき、A*?Bは次のような動作をすることになります。
表現AとB…というのは、文字列「AB」を正規表現「A*?B」で処理をする、ということでしょうか。
>>次に、量指定子の適用のされかたについて
つまり、「「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗する…」というのは合っているということでしょうか。
>>『詳説 正規表現 第3版』では、非貪欲な量指定子の挙動を??についてしか詳しく説明していないようです。
非常に勉強になります。てっきり??以外も飛ばしてから失敗すれば保存ステートリストに保存していた保存ステートを実行するのだと思っておりました。
つまり、??以外の非貪欲な量指定子たちは、貪欲な量指定子と動作が同じ、ということですよね。
貪欲な量指定子の動きというのは、マッチするか確かめるが、失敗してもよいように正規表現の方を一つすすめ、文字列とマッチするかどうかというバックトラックを保存する、というものです。
回答に加筆しました。
> つまり、「「billions」を正規表現で処理してから、否定先読みの効果で正規表現が失敗する…」というのは合っているということでしょうか。
「とばされる」ということはありえないので、それが正しい解釈でしょう。
なお、もう少し簡単な例を工夫していただいたほうがいいと思います。ご提示の例を丹念に追って回答するのはかなり大変です。
> つまり、??以外の非貪欲な量指定子たちは、貪欲な量指定子と動作が同じ、ということですよね。
??も動作は同じです。
回答にも加筆しましたが、?や??は「0回以上1回以下続く」という意味です。*や*?は「0回以上続く」、+や+?は「1回以上続く」、{m,n}は「m回以上n回以下続く」です。回数の下限と上限に違いがあるだけです。
あなたの回答
tips
プレビュー
