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

詳説正規表現第四章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」は、ドットにマッチ。

...以下同じような動作。

マトリョーシカのようにカッコがカッコを内包しているときの正規表現の動きは、上記の形であっているのでしょうか。

ikedas

2017/03/08 12:50

すみませんが、もう少し引用の範囲を広げてもらえませんか。節の最初から3段落くらいを引用しないと、読んだ人にはなぜそういう正規表現を持ち出してきたのかがわからないです。

行動規範の内容に同意します

回答2件

ベストアンサー

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

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

たとえば「₁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?(…))))

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

投稿2017/03/12 06:42

ikedas

総合スコア4333

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

投稿2017/03/08 12:02

Zuishin

総合スコア28660

ikedas

2017/03/12 06:44

原著の該当箇所を見ると3つの正規表現の直後に脚注がついており、「DFAではこの3つは区別されない」という趣旨の断り書きがあります (訳書は持っていないのですが、同じ脚注があるはずです)。つまり、修正前の質問文のように断わりなく3つの正規表現を並べただけだと、Zuishinさんのように「実装によってはどれも同じである場合もある」という趣旨のご回答があっても不思議でないです。つまり、質問のほうに不備があったので、回答のほうにマイナス評価がつくのは不当です。質問者さんへ。ご自分がわかっていることなら他人にもわかっているとは限りません。質問を読む人の気持ちになって質問して下さい。「質問する」ボタンを押す前に、書いた質問文を読み返して、他人にわかってもらえる文章になっているか確認して下さい。