正規表現で「厳密なAND演算」を実現する方法（※非実用的）

ひとつの正規表現でAND条件を実現する際、「先読み」（lookahead）を用いる方法がよく紹介されている。

ただ、状況によってはこれは期待する結果とならない。

本記事では、単純な先読みではうまくいかない例を挙げ、何とか思いついた代替方法を紹介する。 PCRE2 の機能を使っている上にあまり効率的ではないため、残念ながら実際の場面で使えるような方法ではない。

問題

任意の文字列に対し、先頭から「文字数が2の倍数」かつ「文字数が3の倍数」である部分文字列にマッチする正規表現を書け。

入力文字列の例

0123456789abcdef

マッチを期待する部分文字列（どれでも可）

0123456789ab
012345
（空文字列）

AND演算があれば…

OR を実現する | （ふつうの選言）からの類推で、 AND は & で表すとする。そうすると、単に regex1 & regex2 という表記で済む。

「文字数が2の倍数」は (..)* 、「文字数が3の倍数」は (...)* という正規表現で表せるので、あとは先頭を表すアンカー \A を組み合わせて以下のようになる。

\A((..)*&(...)*)

例に挙げた入力文字列に対してだと、 \A を考慮して、

• (..)* は "", "01", "0123", "012345", "01234567", "0123456789", "0123456789ab", "0123456789abcd", "0123456789abcdef" にマッチしうる
• (...)* は "", "012", "012345", "012345678", "0123456789ab", "0123456789abcde" にマッチしうる
• したがってANDでは "", "012345", "0123456789ab" にマッチしうる

普通の解法

よくある先読みだと…

AND演算が先読みでできると聞いていれば、 (..)* と (...)* を組み合わせて以下のように書きたくなるかもしれない。

\A(?=(..)*)(...)*

しかしこれは問題の条件を満たさない。（例に対しては15文字がマッチする）

条件を翻訳

要するに「文字数が6の倍数」ならいいので、以下のように書ける。

\A(.{6})*

これは確かに正しいのだが、元の各条件を表す正規表現が跡形も無い。他の正規表現のAND演算をしたい状況に応用することはできない。

思いついた方法

PCRE2 の機能を使うことになるが、先読みの方法に細工を加える。

\A(?*(..)*(?<suffix>.*+)\z)(...)*(?=\k<suffix>\z)

読みやすく空白文字を入れて整形すると次の通り。¹

\A
(?* (..)*      (?<suffix>.*+) \z)
    (...)* (?= \k<suffix>     \z)

• 最初の先読みでは、バックトラッキングがきく（アトミックグループにしない）よう (?*…) を使う
  https://www.pcre.org/current/doc/html/pcre2pattern.html#SEC21
• 最初の先読みの際に、「マッチした先にある残りの文字列」を取得しておく（ suffix という名前でキャプチャしたところ）
• AND条件の2回目以降は、マッチした先にキャプチャと同じ文字列が続くことを確認する

---

3項以上のAND演算 regex1 & regex2 & … & regex8 & regex9 に対する一般化した書き方は以下のようになる。

(?* regex1     (?<suffix>.*+) \z)
(?= regex2     \k<suffix>     \z)
…
(?= regex8     \k<suffix>     \z)
    regex9 (?= \k<suffix>     \z)

※ 改行文字が含まれる可能性を考慮すると、 . より \p{Any} などのほうが良いかもしれない。

考え方

普通の先読みの方法でできていなかったのは、「2つ以上の正規表現について、マッチする部分文字列の終端を合わせる」ということ。よく見るAND演算の例では文字列末尾（ $ や \z ）で合わせることを前提としていて、部分一致とは相性が悪い。

今回は「終端を合わせる」というのを「後に続く文字列が一致する」というふうに読み換えた。以前に出てきた文字列との一致判定には後方参照を使えばいいので、最初の条件を処理する際にキャプチャさせる。

最初の条件を処理する際、終端を文字列のどこに設定すればいいのか一発で当てることはできないため、バックトラッキングによる探索が必要になる。しかし通常の先読み (?=…) は一度マッチしたら他のパターンを試さないため、探索させることができない（と今回初めて知った）。機能の豊富な PCRE のドキュメントを見ていたらバックトラッキング可能な先読み (?*…) があったため、ようやく実現できた。

その他のメモ

ド・モルガンの法則に基づきAND演算をORとNOTの組み合わせで処理するという考え方があった。上記の回答は理論的な変換方法についてだが、代わりに正規表現の機能で表せれば目的を達成できる。

ただ、今度は「厳密なNOT演算」を実現する方法が必要になる。一般的なNOT機能には否定先読み (?!…) や非包含オペレータ (?~…) （鬼車・鬼雲）があるが、これらは「あるパターンを含む文字列にマッチしない」ようにはできても、「あるパターンに完全一致する文字列にだけマッチしない」というふうにはできない。具体的に言うと、 (?~(..)*) などと書いても長さが奇数の文字列を表すわけではない。

とはいえ前節のAND演算と同じ考え方から、NOT演算 !regex を以下のように書く方法は思いついた。

(?* (?<matched>.*) (?<suffix>.*+) \z)
(?! regex          \k<suffix>     \z)
    \k<matched>

これで \A((..)*&(...)*) == \A!(!(..)*|!(...)*) を書くと以下のようになる。読みにくいが、 https://regex101.com/ で試したらきちんと動作した。

\A
(?* (?<matched>.*) (?<suffix>.*+) \z)
(?! (
    (?* (?<matched1>.*) (?<suffix1>.*+) \z)
    (?! (..)*           \k<suffix1>     \z)
        \k<matched1>
    |
    (?* (?<matched2>.*) (?<suffix2>.*+) \z)
    (?! (...)*          \k<suffix2>     \z)
        \k<matched2>
                 ) \k<suffix>     \z)
    \k<matched>

---

今回無理やり実現したAND演算やNOT演算は、純粋な正規表現と等価な決定性有限オートマトン（DFA）では簡単に実現できる。これらの演算を追加した正規表現エンジンを作っている人もいた。

1. 正規表現の空白文字を無視するフラグ x を指定すればこのまま動作する。 ↩