正規表現のバックトラックについて

正規表現のバックトラックについて記載する。NFD型の正規表現エンジンは特定文字列の一致のために、文字列の読み戻しを行う。実例を元に解説します。

実例

match(r"\s+$", "     長ネギラーメンを食べたい")

空白文字５文字＋長ネギを末尾が１文字以上の空白かどうか？で一致を試みる。挙動は、次の通りになります。

1. \s+が「空白文字5文字」に一致するが$の末尾に当たらないので、バックトラックする。
2. \s+が「空白文字4文字」に一致するが$の末尾に当たらないので、バックトラックする。
3. \s+が「空白文字3文字」に一致するが$の末尾に当たらないので、バックトラックする。
4. \s+が「空白文字2文字」に一致するが$の末尾に当たらないので、バックトラックする。

次に先頭１文字の空白文字を飛ばして「スペース４文字」で一致するか判定する。を、繰り返します。先頭に空白文字を追加するごとに、バックトラックの回数が１回増えます。

感想

オートマトンと正規表現の関連がいまいち腑に落ちていません。次の行動は「正規表現技術入門 ――最新エンジン実装と理論的背景」を読もうかと考えています。