内包されているときのバックトラックの動きが分からない

Question

詳説正規表現第四章157pにて```*```と```+```のバックトラックの仕組みについて解説している箇所の一節に分からないとこがありました。

> 「```x*```」が「```x?x?x?x?x?x?```…」(より正確には「```(x(x(x(x…?)?)?)?)?```」のようなものだと考えれば、これまでに見てきたものと大きな違いはない。
エンジンは、スターの対象となっている要素をチェックする前に、チェックが不成功になったら(あるいは最終的に不成功だとわかったら)、スターの後ろの物をチェックするためのステートを保存する。このステートの保存は、スターによるくりかえしマッチが不成功になるまで続く。

上記の```(x(x(x(x…?)?)?)?)?```の動作についての疑問です。xの部分に対し任意の文字を意味する```.```に変更したうえで、文字列「**123456789**」を置換したとすると

```
(.(.(.(.?)?)?)?)?
↓
「$1」と「$2」と「$3」と「$4」と「$5」(←のように置換したとすると…)
↓
「1234」と「234」と「34」と「4」
```
となります。$1の場合は、最も外側のカッコが1234をキャプチャし、最も外側のカッコに内包されている子カッコが234、その子括弧に内包されているカッコが34、最深部のカッコが「4」です。

文字列123456789に```(.(.(.(.?)?)?)?)?```をマッチさせるとき、マッチが開始した現在の状態(カレントステート▲)は、下記になります。

▲123456789 ```▲(.(.(.(.?)?)?)?)?```…「1」が任意の文字にマッチするか調べるが、マッチに失敗したときのために、「▲123456789」は、「```(.▲(.(.(.?)?)?)?)?```」にマッチするか？を保存。数字の「1」は、ドットにマッチ。

1▲23456789 ```(.▲(.(.(.?)?)?)?)?```…「2」が任意の文字にマッチするか調べるが、マッチに失敗したときのために、「1▲23456789」は、「```(.(.▲(.(.?)?)?)?)?```」にマッチするか？を保存。数字の「2」は、ドットにマッチ。

...以下同じような動作。

マトリョーシカのようにカッコがカッコを内包しているときの正規表現の動きは、上記の形であっているのでしょうか。

Accepted Answer

正規表現の括弧はキャプチャの働きも持ちますが、それ以前に、部分表現をまとめる働きがあります。ご質問の引用箇所では、後者の働きが重要です。

状態の保存がされる場所が複数ある場合のバックトラックの動作について考えます。正規表現でのそのような場所を、以下では₁、₂、₃、…で示します。

たとえば「`₁A?₂B?C`」では、次のように動作します。

- **「`A?B?C`」によるマッチ**は次のように動作する。
  ₁で状態を保存し、**「`A?`」によるマッチ**を試行。次に\*\*「`B?C`」によるマッチ\*\*を試行して、失敗したらバックトラックして₁の状態に戻り再試行。
  最終的に「`A?`」によるマッチですべての再試行が失敗した場合は、「`A?B?C`」によるマッチは失敗。

- **「`B?C`」によるマッチ**は次のように動作する。
  ₂で状態を保存し、**「`B?`」によるマッチ**を試行。次に\*\*「`C`」によるマッチ\*\*を試行して、失敗したらバックトラックして₂の状態に戻り再試行。
  最終的に「`B?`」によるマッチですべての再試行が失敗した場合は、「`B?C`」によるマッチは失敗。

- **「`C`」によるマッチ**は次のように動作する。
  状態保存はしない。マッチが失敗したら失敗。

「`A?`」がマッチした後でバックトラックが起きる (状態₁に戻って再試行する) のは、後続する表現によるマッチが失敗したときです。**バックトラックの条件は、後続する表現が失敗することだけ**で、後続する表現がどんなものなのかは考慮されません。つまりこの正規表現は「`A?`によるマッチが成功した後に、残りのマッチが成功する。失敗したらバックトラックする」という意味です。

よって、「`A?B?C`」は、バックトラックを考慮すると「`A?(B?C)`」と書けます。両者は同じものを表しています。

同様に、「`₁x?₂x?₃x?₄x?…`」は、次のように書きかえることができます。

- `x?(x?x?x?…)`
- `x?(x?(x?x?…))`
- `x?(x?(x?(x?…)))`
- `x?(x?(x?(x?(…))))`

下のものほど、バックトラックを考慮した「より正確」な表現だという言いかたもできるでしょう。

Answer

仕様としては 0 回以上の繰り返しであり、実装としてはその処理系の自由です。