グループ化した要素のバックトラック

Question

▲…マッチのカレントステート(現在の状態)
△…最初にマッチをしたところ

ABC AB?C
という文字列「ABC」と正規表現AB?Cがあったとします。
Aがマッチし、▲を一つずらして下記のようになる。

△A▲BC A▲B?C

「B」がB?にマッチするか調べるが、失敗してもよいように、文字列「B」が正規表現AB?▲Cにマッチするか？という保存ステートを保存。

<あとは質問と関係がないので省略>

ここまでの動作は、理解できます。ここで疑問が一つあります。別の正規表現になりますが、下記のようにバックトラックが発生する要素、つまり()内にある否定先読みとがグループ化されている場合、

<p>のマッチ後、あめんぼの**あ**の前まで進める… ```△<p>▲あめんぼ </p>あおいな</p> あいうえお <p>▲((?!</?p>).)*</p>```

最初の例の場合は、

「B」がB?にマッチするか調べるが、失敗してもよいように、文字列Bが正規表現AB?▲Cにマッチするか？という保存ステートを保存。

ですが、2番目の例の処理の場合は、
文字列「あ」が((?!</?p>).)にマッチするか調べるが、失敗しても良いように、「あ」が<p>((?!</?p>)▲.)*</p>にまっちするか？という保存ステートを保存。
あるいは、
文字列「あ」が((?!</?p>).)にマッチするか調べるが、失敗しても良いように、「あ」が<p>((?!</?p>).)*▲</p>にまっちするか？という保存ステートを保存。
なのか、いったいどちらなのでしょうか。

Answer 1

ご質問の例は複雑で見づらいので、<p>をP、</p>をQに置き換えたもので説明します。次のようになります。

• 文字列:
  Pあめんぼ QあおいなQ あいうえお
• 正規表現:
  P((?!P|Q).)*Q

次のことに注意して下さい。
(1) 量指定子は、自身が量化している部分表現がどんなものかは知らない。ただ、その部分表現によるマッチを指定の回数だけ成功させようとするだけである。
(2) 正規表現エンジンは、連接する部分表現がマッチするかどうかを順番に試していくが、次にどんな部分表現が後続するかは知らないし、マッチさせている文字列に次にどんな文字が出現するかも知らない。
(次の部分表現が先読み表現だった場合も、その部分表現によるマッチを実際に試行するときにはじめて、次に出現する文字を調べます。)

ご質問の「2番目の例の処理の場合」は、前者がおおむね正しいです。以下、説明します。

まず注意の (1) により、量指定子は自身が量化している部分表現の詳細を知りませんから、(?!P|Q).という部分表現を仮にRで表せば
P₁R*Q
と表すことができます (「₁」は状態の保存がされ得る場所を示します)。

ですから、次のように動作するはずです (先日の回答も参照)。

1. 「PR*Q」によるマッチは次のように動作する。
   「P」によるマッチを試行。成功すれば「R*Q」によるマッチを試行して、失敗したら失敗。
2. 「R*Q」によるマッチは次のように動作する。
   ₁で状態を保存し、「R*」によるマッチを試行。次に「Q」によるマッチを試行して、失敗したらバックトラックして₁の状態に戻り再試行。
3. 「Q」によるマッチは次のように動作する。
   マッチが失敗したら失敗。

ここで注意の (2) を確認していただきたいのですが、状態の保存はマッチさせられる文字列の中に次にどんな文字が現れるかに依存していません。

---

結果として、この正規表現はPあめんぼ Qにマッチします。

Answer 2

「文字列」と「正規表現」の境界が分かりづらいので、区別できるように書く配慮があると助かります。
次の場合と仮定します。

var string = '<p>▲あめんぼ </p>あおいな</p>';
/<p>((?!</?p>).)*<\/p>/.exec(string);

((?!</?p>).) では </p> を消費できないので、後続の あおいな はテストする事すらしません。

Re: aaaaaaaa さん