はじめに

おはようございます。今朝、早起きして Laravel のルーティング処理を読んでいたら、見慣れない正規表現に出くわしました。

見慣れない正規表現というのは *? とか +? とかです↓ ソースコードの引用元はこちらです。

Illuminate\Routing\Routeクラス

/**
 * Get the parameter names for the route.
 *
 * @return array
 */
protected function compileParameterNames()
{
    preg_match_all('/\{(.*?)\}/', $this->getDomain().$this->uri, $matches);

    return array_map(function ($m) {
        return trim($m, '?');
    }, $matches[1]);
}

// ...中略...

/**
 * Get the optional parameter names for the route.
 *
 * @return array
 */
protected function getOptionalParameterNames()
{
    preg_match_all('/\{(\w+?)\?\}/', $this->uri(), $matches);

    return isset($matches[1]) ? array_fill_keys($matches[1], null) : [];
}

PHPのドキュメント（Repetition, 繰り返し）を見てみると、よく使う {m,n}, *, +, ? といった量指定子の他にも、 {m,n}?, *?, +?, ?? という量指定子があるようです。 {m,n}, *, +, ? それぞれに ? をくっつけた見た目をしていますね。

この記事では、 {m,n}, *, +, ? という量指定子をさらったあと、? がくっついた {m,n}?, *?, +?, ?? たちの挙動を ? がない量指定子と比較してまとめようと思います。

前提

この記事のPHPコードは paiza.IO で実験しています。PHPバージョンは 7.4.1 でした。
基本的にPCRE, もしくはPHPが使っているPCREの文脈で書いています。

準備

まず、 {m,n}, *, +, ? という量指定子を復習しておきます。 *, +, ? の3つは {m,n} の特別な場合に名前をつけたものなので、 {m,n} を理解すればこれらも大体わかります。

`{m,n}`

{m,n} は「直前のパターンの m 回以上 n 回以下の繰り返し」を意味する量指定子です。例えば a{2,3} は「a の 2 回以上 3 回以下の繰り返し」を意味します。これは aa|aaa と等価です。

// a{2,3} は

'italiaan'　// => マッチします。
// 'italiaan' は 'aa' を含んでいるからです。
// 世界にオランダ語がなかったら例を作れなかったかもしれません。

'italian' // => マッチしません。
// 'italian' は 'aa'　を（そして 'aaa' も）含んでいないからです。

なお、意味からも明らかですが m, n は整数かつ $0 \le m \le n$ である必要があります。

細かいことを言うと {m,n} にはさらに次の3パターンの使い方があります。

`{l}`

,n がない（n が , ごとなくなった, もしくは m が , ごといなくなった）パターンです。これは {l,l} を意味します。「直前のパターンの l 回以上 l 回以下の繰り返し」、つまり「直前のパターンのちょうど l 回の繰り返し」です。

例えば e{2} は「e のちょうど 2 回の繰り返し」を意味し、 ee と等価です。

// e{2} は

'ieee' // => マッチします。
// 'ieee' は 'ee' を含んでいるからです。

'hehehe' // => マッチしません。
// 'hehehe' は 'ee' を（連続した2つの `e` を）含んでいないからです。

`{m,}`

n がない（n が , を残していなくなった）パターンです。正しくない記法ですが {m,∞} を意味すると思えばわかりやすいです。「直前のパターンの m 回以上の繰り返し」を意味します。

今度は c{3,} を考えてみると、これは「c の 3 回以上の繰り返し」を意味します。 | だけを使って長さが有限で等価な正規表現を作ることはできませんが、だいたい ccc|cccc|ccccc|... なイメージです。

{m,n} にほぼほぼ還元できるのでマッチの具体例はいらないかなと思います。

`{,n}`

m がない（m が , を残していなくなった）パターンです。 {0,n} を意味します。これは正しい記法です。「直前のパターンの（0 回以上） n 回以下の繰り返し」という意味です。

d{,3} は「d の（0 回以上） 3 回以下の繰り返し」という意味で、 |d|dd|ddd と等価です。

具体例は省略します。

`*`, `+`, `?`

これらは {m,n} を使って書き直すことができます。すなわち、 *, +, ? は {m,n} の特別な場合へのエイリアスです。

* => {0,}. 正しくない記法だが {0,∞} と思える。「直前のパターンの 0 回以上の繰り返し」
+ => {1,}. これも正しくない記法だが {1,∞} と思える。「直前のパターンの 1 回以上の繰り返し」
? => {0,1}. 「直前のパターンの0回以上1回以下の繰り返し」すなわち「直前のパターンの 0 回か 1 回の繰り返し」

本題

{m,n}?, *?, +?, ?? たちの説明に移ります。準備が長くなってしまいましたが、そのぶん本題は短くまとめられそうです。

結論を言いますと、 ? がくっついた量指定子の意味（何にマッチして何にマッチしないか）は ? がくっついていない量指定子と全く同じです。 復習の復習も兼ねてちゃんと書くとこうなります↓ 「直前のパターンの〜の繰り返し」の「〜」だけ書きます。

`?` 有りの量指定子	意味	`?` 無しの量指定子
`{m,n}?`	`m` 回以上 `n` 回以下	`{m,n}`
`{l}?`	ちょうど `l` 回	`{l}`
`{m,}?`	`m` 回以上	`{m,}`
`{,n}?`	`n` 回以下	`{,n}`
`*?`	`0` 回以上	`*`
`+?`	`1` 回以上	`+`
`??`	`0` 回か `1` 回	`?`

何が違うのかと言いますと、それは 「複数箇所でマッチできる時にどのマッチがキャプチャされるのか」 です。

正規表現 a{0,2} を文字列 'italiaan' にマッチさせることを考えてみましょう。細かくステップを切って考えると次のようになるでしょう。

正規表現 a{0,2} は |a|aa と等価である。すなわち、空文字列 or 'a' or 'aa' にマッチする。
空文字列が 'italiaan' にマッチするかどうか考えると、9箇所でマッチする。マッチした部分文字列はいずれも '' である。
'a' が 'italiaan' にマッチするかどうかを考えると、3箇所でマッチする。マッチした部分文字列はいずれも 'a' である。
'aa' が 'italiaan' にマッチするかどうかを考えると、1箇所でマッチする。マッチした部分文字列は 'aa' である。
結論として、正規表現 a{0,2} は文字列 'italiaan' にマッチする。が...

ところで、PHPの関数 preg_match(string $pattern, string $subject): int は、 $pattern が $subject にマッチしたら 1 を返し、そうでなかったら 0 を返します。

preg_match('/a{0,2}/', 'italiaan') を評価することを考えると、 a{0,2} が 'italiaan' の9箇所どっかの '' にマッチしていようが3箇所どっかの 'a' にマッチしていようが1箇所の 'aa' にマッチしていようが評価値（返り値）は 1 であり、 '' にも 'a' にも 'aa' にもマッチしなかったら 0 です。ここだけ見ると違いはありません。

しかし、正規表現は（そして preg_match() も）ただ「マッチしたかどうか」を判定するためだけのものではありません。 マッチした場合には、マッチした（部分）文字列を取得することができます。 バリデーションなどにおいては「マッチしたかどうか」だけが重要な場合が多々ありますが、例えば「HTMLからURLを抽出する」とか「エディターで関数呼び出しの最後に引数を1つ一斉に追加する」などといったときには、「マッチしたものが手に入る」と便利です。

preg_match() 関数は第3引数にリファレンスを渡すとマッチした（部分）文字列を代入してくれます。試しに

preg_match('/italia{0,2}/', 'italiaan', $matches);

var_dump($matches[0]);

を実行してみると

// string(7) "italiaa"

と出力されます。なお、正規表現が a{0,2} ではなくて italia{0,2} になっているのには理由があるのですが、この記事で説明したいと思っている 「複数箇所でマッチできる時にどのマッチがキャプチャされるのか」 には本質的でないと考え省略します。

italia{0,2} は 'itali' にも 'italia' にも 'italiaa' にもマッチできますが、マッチした部分文字列としては3番目の 'italiaa' が得られています。

次は

preg_match('/italia{0,2}?/', 'italiaan', $matches);

var_dump($matches[0]);

を実行してみると

// string(5) "itali"

と出力されます。

{0,2} に ? がついた italia{0,2}? は 'itali' にも 'italia' にも 'italiaa' にもマッチできますが、今度はマッチした部分文字列としては1番目の 'itali' が得られています。

これは環境依存（処理系とかタイミングとか次第）ではなく、 （安心して使用してよい）仕様 です。 ? が無い量指定を使うと、正規表現エンジンは 「（量指定子で指定したサブパターンが）マッチした部分が最も長いもの」 をキャプチャします。反対に ? が有る量指定子を使うと 「（量指定子で指定したサブパターンが）マッチした部分が最も短いもの」 がキャプチャされます。例に戻って確認してみましょう。

'itali' => a{0,2} or a{0,2}? にマッチした部分の長さは 0 => a{0,2}? を使うとこれがキャプチャされる。
'italia' => 長さは 1 => a{0,2}, a{0,2}? のいずれを使ってもキャプチャされない。
'italiaa' => 長さは 2 => a{0,2} を使うとこれがキャプチャされる。

なお、正規表現パターン内に量指定子が2つ以上ある場合を意図的に省略しています。量指定子が1つの場合を理解することを目標としたいためです。

「（量指定子で指定したサブパターンが）マッチした部分が最も長いもの」がキャプチャされるような量指定子を Greedy（貪欲） であると言います。一方、「（量指定子で指定したサブパターンが）マッチした部分が最も短いもの」がキャプチャされるような量指定子は Ungreedy（非貪欲） であると言われます。

? が無い量指定子、 {m,n}, {l}, {m,}, {,n}, *, +, ? たちは デフォルトで貪欲 であり、 ? が有る量指定子、 {m,n}?, {l}?, {m,}?, {,n}?, *?, +?, ?? たちは デフォルトで非貪欲 です。

本題の最後に、量指定子の意味早見表と、問題を1問おいておきます。量指定子の個別の説明や問題の解答は不要だと思われます。

非貪欲な量指定子	意味	貪欲な量指定子
`{m,n}?`	`m` 回以上 `n` 回以下	`{m,n}`
`{l}?`	ちょうど `l` 回	`{l}`
`{m,}?`	`m` 回以上	`{m,}`
`{,n}?`	`n` 回以下	`{,n}`
`*?`	`0` 回以上	`*`
`+?`	`1` 回以上	`+`
`??`	`0` 回か `1` 回	`?`

問題

正規表現 ita? と ita?? をそれぞれ文字列 'italiaan' に対してマッチさせたとき、キャプチャされる文字列はなんでしょうか？

おわりに

どうやらこの記事でまとめた内容は、正規表現の中ではまだまだ序の口のようです。ちょっと気になっていろいろ読んでみたら、正規表現エンジンの実装が NFA（非決定性有限オートマトン）なら {m,n}?, *?, +?, ?? を処理することができるが DFA（決定性有限オートマトン）だとそれができないとか、 Possessive な量指定子 {m,n}+, *+, ++, ?+ があるとか、面白そうな話題がいろいろ見つかりました。 U（修飾子, Modifier）の説明も省略しています。また正規表現に戻ってきたときにここら辺の理解がちょっと進むといいなあと思っております。

最後まで目を通していただき、ありがとうございました。