30
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

何にもマッチしない正規表現いろいろ

Last updated at Posted at 2018-10-27

使い道は後回しにして、表題の正規表現の例を以下に示す。環境によって使えなかったり文法が異なるものもあるので注意。(記事中ではRubyを念頭に置いている)

(?!)
(*FAIL) ※Perl/PCRE
(?~)    ※鬼雲
a*+a
(?>a*)a
\P{Any}
[\d&&\D]
\b\B
0^
# カレントディレクトリ以下のファイルを検索し、マッチしたファイル名を表示する
grep -rl '\b\B' .   #=> 0件

各例の説明

(?!) :否定先読み

否定先読みの一般的な文法は (?!exp) 。現在の文字列位置から見て先(右方向)の文字列が正規表現 exp にマッチしないときに、現在位置(→空文字列)にマッチする。

(?!)exp に空文字列を指定したものである。すると、この先の文字列は必ず空文字列にマッチする関係上、否定先読みは必ず失敗してしまう。

Rubyでは Regexp.union とやればこれが出てくる。(0個の数の総和が0になるのと同じ理屈)

引数をひとつも与えなかった場合、決してマッチしない Regexp を返します。

p Regexp.union() # => /(?!)/

(*FAIL) :バックトラック制御

バックトラック制御は Perl 5.10 で導入された機能で、記法は (*VERB:ARG) 。定義された VERB が色々あるが、この中に「常に失敗」を表すピッタリのものが含まれている。

ドキュメントから引用する。

(*FAIL) (*F)
このパターンは何にもマッチングせず常に失敗します。これはエンジンを強制的にバックトラックさせるために使えます。これは (?!) と等価ですが、より読みやすくなっています。実際、(?!) は内部的には (*FAIL) に最適化されます。

Perl Compatible Regular Expressions (PCRE) でも使えるため、例えば grep -P などで試せる。

(?~) :非包含オペレータ

新しめの鬼雲で使える文法。Rubyでは2.4.1から。

一般的な説明を実装者の記事から引用する。

(?~subexp) は、 subexp にマッチする文字列を含まない任意の文字列にマッチします。
例えば (?~abc) は、 "", "ab", "aab", "ccdd" 等にマッチしますが、 "abc", "aabc", "ccabcdd" 等にはマッチしません。

文法は否定先読みと似ているが、これは位置でなくなるべく長い文字列にマッチするもので、最大量指定子 * に近い。

(?~)subexp に空文字列を指定したものである。すると、この先の文字列は必ず空文字列にマッチする関係上、非包含オペレータは必ず失敗してしまう。

a*+a :絶対最大量指定子

絶対最大量指定子(強欲、独占的なマッチ)の説明でよくある例。

普通の最大量指定子 * は直前のパターンをなるべく長く繰り返すが、それが原因で後続のパターンがマッチ失敗するときは繰り返しを短くする。
一方で絶対最大量指定子 *+ は、同じく直前のパターンをなるべく長く繰り返すが、後続が失敗したらすぐに自分も失敗とする。

今回の例は、 a*+ が連続する全ての a を独占して手放さず、後続の a がマッチする分が無くなってしまうため、常に失敗となる。

(ところで、 a*+ は空文字列にマッチできるので、 a の登場しない部分文字列で無駄な探索が発生してしまう。1文字以上にマッチする a++ に変えたほうが高速だと思う。)

(?>a*)a :アトミックグループ

この例は前節と全く同じ。アトミックグループという汎用的な機能で絶対最大量指定子を書き直している。

(?>exp) と書くと、 exp が最初にマッチした文字列で確定する。後続のパターンが失敗しても exp で違うマッチ方法(繰り返しの長さを変えたり、他の選択を選んだり)を試すことは無く、グループ自体がマッチ失敗となる。

\P{Any} :空の文字クラス(全否定)

例えば [a-z] という正規表現は電話番号の文字列にマッチしない。なぜなら電話番号に使われる文字を含んでいないから。
この考えでいくと、「あらゆる文字列に使われていない文字(の集合)」で正規表現を作れば絶対にマッチしなくなる。しかしそんな文字は存在し得ないので、空の文字クラスを作るしかない。

本当に空の文字クラス [] は文法エラーになるので別の方法を考える。文字クラスは否定が使えるので、「この世の全ての文字」の否定ならいい。

任意の1文字を表す . は否定をとれない。別の方法を探したら、鬼雲のUnicodeプロパティ指定に \p{Any} というのがあった1。これの否定をとればいい(pを大文字にするか、プロパティ名の前に^を置く)。

[\d&&\D] :空の文字クラス(共通部分)

空の文字クラスを作る別の方法。複数の文字クラスの共通部分を演算できるなら、それが空になるようにすればいい。バックスラッシュ+英語1文字で用意されている文字クラスは大文字小文字で真逆になるので、それらの共通部分をとるのが簡単。

\b\B :アンカーの排中律

アンカーは文字列の中で指定の条件を満たす位置にマッチする(先読みと同じ)。

\b は単語境界にマッチし、 \B はそれ以外の境界にマッチする。なので両方を同時に満たす境界は存在しない。

※ grep のバージョンによって \b の動作が異なることがあるが、2種類のアンカーが真逆の振る舞いである限りは問題ない。

0^ :アンカーに矛盾

^ は行頭にマッチする。つまり直前の文字は無いか改行コードであり、普通の文字がくることはあり得ない。

用意されているアンカーは、その位置を挟む前後の文字の条件を指定しているため、色々なバリエーションが作れる。その中で 0^ を選んだのは、理論で表記する際の に近い気がしたからという遊び心。

※grepの基本正規表現では、この書き方をすると ^ がアンカーと認識されなかった。拡張正規表現やPCREでは問題ない。

# grep (GNU grep) 2.25
echo '0^' | grep    '0^'   #=> 0^
echo '0^' | grep -E '0^'   # マッチしない
echo '0^' | grep -P '0^'   # マッチしない

注意:間違った例

検索してみると $^ を紹介している例がいくつかあった。これはとある文字列にマッチしてしまう。 → 答えは別記事で

正規表現に組み込むと

単独では何にもマッチしないが、長い正規表現の一部として組み込むとマッチすることがある。基本的なパターンを見てみる。

連接

何にもマッチしなくなる。

# マッチした部分文字列を<>で括る置換
"abc".gsub(/b/    , "<\\0>")   #=> "a<b>c"
"abc".gsub(/b(?!)/, "<\\0>")   #=> "abc"

選択

他の選択肢にマッチする。

"abc".gsub(/b/     , "<\\0>")   #=> "a<b>c"
"abc".gsub(/b|(?!)/, "<\\0>")   #=> "a<b>c"

繰り返し

ふつうのパターンに対する繰り返しは無数の文字列にマッチするようになるが、何にもマッチしないパターンの繰り返しは空文字列にだけマッチする。

"abc".gsub(/.*/   , "<\\0>")   #=> "<abc><>"
"abc".gsub(/(?!)*/, "<\\0>")   #=> "<>a<>b<>c<>"

これは、どんなパターンでも0回の繰り返しは空文字列を表すことによる。

有用性

「何にもマッチしない」というのは、バリデーションでいえば「どんな入力も通さない」ということで、存在意義が無いように見える。実際ふつうの状況では使わないが、特殊な要件では力を発揮する。

正規表現の理論

理論では「何にもマッチしない正規表現」は最初に定義されるパターンで、専用のメタ文字 が与えられている2。ちなみに「空文字列にのみマッチする正規表現」( ε で表すことがある3)は ∅* の糖衣構文に過ぎないので、定義から省いても構わない。

何にもマッチしない正規表現を認めることで理論が色々ときれいになっている。例えば理論上は「2つの正規表現の両方にマッチする文字列の集合」を表す1つの正規表現を(先読みなどは使わずに)必ず書ける。すると困ったことに、それぞれの集合の共通部分が無いときは、何にもマッチしないという状況が発生してしまうが、これは正規表現の最初の定義パターンなのでやはり成り立つ。

キャプチャの確認

正規表現の拡張機能のひとつに、キャプチャを利用した条件分岐を書ける。文法は (?(cond)exp1) または (?(cond)exp1|exp2) で、条件 cond にはキャプチャグループの名前を指定し、真なら exp1 、偽なら exp2 が適用される。(区切りの | は通常の選択ではない)

分岐先の正規表現を何にもマッチしないように指定すれば、キャプチャの成否をマッチの成否に変換できる(?!) で失敗、 ε で成功を表す。

(?('name')(?!))    # グループ name がキャプチャしていたら失敗
(?('name')(?!)|)   # グループ name がキャプチャしていたら失敗
(?('name')|(?!))   # グループ name がキャプチャしていなかったら失敗

.NET Framework の「グループ定義の均等化」では、スタックの役割を持つキャプチャが空になったことを確認するためにこの機能を併用することが多い。詳細は以前の記事を参照。

再帰を使ってBNFを模倣

正規表現が再帰(部分式呼び出し)に対応していれば、バッカス・ナウア記法(BNF)を模倣できる。再帰はもちろんだが、同じパターンの使い回しを正規表現内にわかりやすく書ける。

このとき何パターンか書き方があるが、正規表現の本文の後に |(?!) を挟んで他の規則を並べていくことで見やすく書ける。他の方法は以前の記事を参照。

文法を制限したJSON文字列にマッチする正規表現を書いてみる。元の定義はこちらのページで、簡略化のため数値・true・false・null・整形用の空白は省いた。

regexp = %r@
	\A\g<json>\z
	|(?!)
	(?<json>         \g<element> )
	(?<value>        \g<object> | \g<array> | \g<string> )
	(?<object>       \{ \} | \{ \g<members> \} )
	(?<members>      \g<member> (?: , \g<member> )* )
	(?<member>       \g<string> : \g<element> )
	(?<array>        \[ \] | \[ \g<elements> \] )
	(?<elements>     \g<element> (?: , \g<element> )* )
	(?<element>      \g<value> )
	(?<string>       " \g<characters> " )
	(?<characters>   \g<character>* )
	(?<character>    [^"\\] | \\ \g<escape> )
	(?<escape>       ["\\/bfnrt] | u [0-9A-Fa-f]{4} )
@x

%@{"tags":[{"name":"正規表現"},{"name":"Onigmo","versions":["6.1.0"]},{"name":"Ruby","versions":["2.4.1"]}]}@.match(regexp)
  1. ソースコードから推測すると [\u0000-\u10ffff] という意味だと思う。Unicodeの範囲が伸びたら変更される?

  2. 元々は空集合を表す記号。

  3. プログラミング言語では空文字列やその正規表現を ""// などと表すが、理論の記述ではこういう囲み文字を使わないのでメタ文字が必要になる。

30
14
9

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
30
14

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?