正規表現

正規表現︵せいきひょうげん、英: regular expression︶は、文字列の集合を一つの文字列で表現する方法の一つである。正則表現︵せいそくひょうげん︶とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正則式︵せいそくしき︶あるいは正規式︵せいきしき︶と呼ばれることもある。

もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が﹁正規言語であること﹂と﹁正規表現によって表せること﹂は同値である。

その後正規表現は単機能の文字列探索ツールやテキストエディタ、ワードプロセッサなどのアプリケーションで、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。

この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。

ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。﹁正規表現によるマッチ﹂を意味する︵専用の︶演算子がある言語なども一部ある。具体例として、grep, AWK, sed, Perl, Tcl, lex などがある。

それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが︵古い実装では実際にそのようなことも多い︶、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。

基本的な概念

理論的に明解であり扱いも容易であるため、形式的な説明を先に述べる。

形式的な説明

詳細は「正規言語」を参照

記号︵アルファベット︶$A=\{a_{1},\dots ,a_{n}\}$$A=\{a_{1},\dots ,a_{n}\}$ 上の正規表現は次のようなものから成る。正規表現があらわす記号列︵アルファベット列︶の集合によって形式言語が定義される。

●$\varnothing$$\varnothing$ は正規表現である。これは記号列を何も含まない空集合 $\varnothing$$\varnothing$を表す。

●$a_{i}$$a_{i}$︵$A$$A$ の任意の要素︶は正規表現である。これは $a_{i}$$a_{i}$という記号列のみからなる集合 $\{a_{i}\}$$\{a_{i}\}$を表す。

●$X$$X$ と $Y$$Y$が正規表現ならば、
●$X\mid Y$$X\mid Y$ も正規表現である。これは $X$$X$に含まれる記号列の集合と $Y$$Y$に含まれる記号列の集合の和集合を表す。

●$XY$$XY$ も正規表現である。これは $X$$X$に含まれる記号列に $Y$$Y$に含まれる記号列をつなげてできる記号列の集合 $\{ab\mid a\in X,b\in Y\}$$\{ab\mid a\in X,b\in Y\}$を表す。

●$X*$$X*$ も正規表現である。これは $X$$X$に含まれる記号列を 0 個以上つなげてできる文字列の集合 $\bigcup _{n}\{X^{n}\mid n\geq 0\}$$\bigcup _{n}\{X^{n}\mid n\geq 0\}$を表す︵クリーネ閉包︶。

●上記の帰納的導出によって構成される記号列のみが正規表現である。

正規表現の定義に、次の項目を含めることもある:

●$\varepsilon$$\varepsilon$ は正規表現である。これは空記号列 $\varepsilon$$\varepsilon$のみからなる集合 $\{\varepsilon \}$$\{\varepsilon \}$を表す。

正規表現 $\varepsilon$$\varepsilon$の表す集合は正規表現 $\varnothing *$$\varnothing *$の表す集合に等しいので、$\varepsilon$$\varepsilon$ を正規表現の定義に含めなくても $\varnothing *$$\varnothing *$で代用できる。

$X\mid Y$$X\mid Y$ の代わりに $X+Y$$X+Y$と書くことや、$XY$$XY$ の代わりに $X\cdot Y$$X\cdot Y$と書くこともある。また、﹁$\mid$$\mid$﹂や﹁$*$$*$﹂の優先順位を明確にするために、補助的なカッコも︵上述の定義には含めていないが︶必要である。

実用的説明

以下ではもっぱらよく使われているライブラリやツールなどの実用的な観点から説明する。

例えば、﹁Handel﹂﹁Hendel﹂﹁Haendel﹂という3つの文字列を含む集合は﹁H(e|ae?)ndel﹂というパターンで表現できる︵あるいは、パターンは個々の3つの文字列にマッチすると言われる︶。ほとんどの形式では、もし特定の集合にマッチする何らかの正規表現が存在すれば、無限の数のそのような表現がある。ほとんどの形式では正規表現を構築するために次の演算子を提供している。

選言

縦棒は選択肢を区切る。例えば﹁gray|grey﹂は﹁gray﹂または﹁grey﹂にマッチし、これは通常﹁gr(a|e)y﹂に短縮される。

グループ分け

丸括弧はスコープと演算子の優先順位を定義するために用いられる。例えば、﹁gr(a|e)y﹂では﹁(a|e)﹂の部分で﹁a﹂または﹁e﹂を示し、全体で﹁gray﹂または﹁grey﹂にマッチする。

量化

文字やグループの後ろの量化子は、直前の表現が何回現れることが許されるかを指定する。非常によく使われる量化子として﹁?﹂﹁*﹂﹁+﹂がある。
?

疑問符は直前の表現が0個か1個あることを示す。例えば、﹁colou?r﹂は﹁color﹂と﹁colour﹂にマッチする。

*

アスタリスクは直前の表現が0個以上あることを示す。例えば、﹁go*gle﹂は﹁google﹂﹁gogle﹂﹁ggle﹂などにマッチする。

+

プラス符号は直前の表現が1個以上あることを示す。例えば、﹁go+gle﹂は﹁google﹂﹁gogle﹂などにマッチするが、﹁ggle﹂にはマッチしない。

これらの構文は任意の複雑な表現を形成するために組み合わされて使用される。

歴史

正規表現の起源は、言語学と、理論計算機科学の一分野であるオートマトン理論や形式言語理論にみることができる。20世紀の言語学では数理的に言語を扱う数理言語学が発展しその過程の一部として、また後者は計算のモデル化︵オートマトン︶や形式言語の分類方法などを扱う学術分野である。数学者のスティーヴン・クリーネは1950年代に正規集合と呼ばれる独自の数学的表記法を用い、これらの分野のモデルを記述した。

Unix系のツールに広まったのは、ケン・トンプソンがテキストファイル中のパターンにマッチさせる手段として、この表記法をエディタQEDに導入したことなどに始まる。彼はこの機能をUNIXのエディタedにも追加し、後に一般的な検索ツールであるgrepの正規表現へと受け継がれていった。これ以降、トンプソンの正規表現の適用にならい、多くのUnix系のツールがこの方法を採用した︵例えば expr, awk, Emacs, vi, lex, Perl など︶。

PerlとTclの正規表現はヘンリー・スペンサー^(英)によって書かれたものから派生している︵Perlは後にスペンサーの正規表現を拡張し、多くの機能を追加した︶。フィリップ・ヘーゼルはPerlの正規表現とほぼ互換のものを実装する試みとしてPerl Compatible Regular Expressions (PCRE) を開発した。これはPHPやApacheなどといった新しいツールで使用されている。

Rakuでは、正規表現の機能を改善してその適用範囲や能力を高め、Parsing Expression Grammarを定義できるようにする努力がなされた。この結果として、Raku文法の定義だけでなくプログラマのツールとしても使用できる、Perl 6 rulesと呼ばれる小言語が生み出された。

︵本来の︶正規表現からの拡張は各種あり便利であるがその多くは、︵本来の︶正規言語から逸脱するものであり、キャプチャなどが代表例である。なお、正規言語から逸脱しないことによって理論的な扱いが可能になるという利点があるため、例えば﹁非包含オペレータ﹂の提案ではそういった観点からの理由も挙げられている。

Rakuに限らずいくつかの実装では、︵Perlではsubpatternと呼んでいる︶部分パターンの定義とその再帰的な呼出しにより、例えばカッコの対応などといった︵本来の︶正規表現では不可能なパターンも表現できる。これは、対象部分にマッチした文字列が捕獲され、後から利用できるキャプチャとは異なり、パターンそのものの定義と利用である。PHP, Perl, Python︵regexライブラリ︶, Ruby などで利用できる。

構文

標準

UNIXの標準であるPOSIXでは、単純正規表現、基本正規表現、拡張正規表現の3種類の記法が示されている。このうち、単純正規表現は﹁歴史的﹂また﹁レガシー﹂と書かれており、後方互換性を提供するものとされ、標準の将来の版では廃止され得ると注意されている。

単純正規表現

単純正規表現はSREとも呼ばれる。その仕様は﹁regexp.h﹂のマニュアルページとして示されている。

基本正規表現

基本正規表現はBREとも呼ばれる。ほとんどの正規表現を利用する UNIXのユーティリティ︵grepやsed︶のデフォルトはこれである。

この文法では、ほとんどの文字はリテラル︵機能を意味せず書かれたそのまま︶に扱われる。つまり、ある文字はその文字にのみマッチする。例えば、正規表現﹁a﹂は文字﹁a﹂にマッチし、正規表現﹁(bc﹂は文字列﹁(bc﹂にマッチするなど。例外はメタ文字と呼ばれる。

正規表現	マッチする対象
.	任意の1文字にマッチする。
[…]	括弧内に含まれる1文字にマッチする。例えば、正規表現「[abc]」は1文字「a」「b」「c」にマッチする。正規表現「[a-z]」は全ての英小文字の1文字にマッチする。これらは混ぜることができる。「[abcq-z]」は1文字「a」「b」「c」「q」「r」「s」「t」「u」「v」「w」「x」「y」「z」にマッチし、正規表現「[a-cq-z]」も同様である。正規表現中の「-」は括弧内の最初か最後にあるときのみ、リテラルとして扱われる。例えば正規表現「[abc-]」や正規表現「[-abc]」は1文字「a」「b」「c」「-」にマッチする。1文字「]」自身にマッチさせる最も手っ取り早い方法は、囲んでいる括弧内で、括弧が最初になるようにすることである。例えば正規表現「[][ab]」は1文字「]」「[」「a」「b」にマッチする。
[^…]	括弧内に含まれない1文字にマッチする。例えば正規表現「[^abc]」は「a」「b」「c」以外の任意の文字にマッチする。正規表現「[^a-z]」は英小文字以外の任意の1文字にマッチする。上と同様にこれらは混ぜることができる。
^	行の最初にマッチする。
$	行の最後にマッチする。
\(…\)	これに囲まれた表現は、後方で呼び出すことができる。次の \1, …, \9 の項を参照のこと。
\1 \2 \3 \4 \5 \6 \7 \8 \9	それぞれ「\(」と「\)」で囲まれた部分に先行してマッチした1 - 9 番目の文字列と同じ文字列パターンにマッチする。この機能は理論的には、言うならば非正規で（正規言語の記述力を超える）、POSIX拡張正規表現では採用されていない。
*	1文字に続く「*」は0回以上の表現の繰り返しにマッチする。例えば「[xyz]*」は空文字列や文字列「x」「y」「zx」「zyx」などにマッチする。 n を1から9までの数字としたとき、基本正規表現「\n*」は「\(」と「\)」で囲まれた部分の0回以上の繰り返しにマッチする。例えば、基本正規表現「\(a.\)c\1*」 は文字列「abcab」 「abcabab」「abcababab」などにマッチするが、文字列「abcac」にはマッチしない。 「\(」と「\)」で囲まれた表現に続く「*」は無効とされる。しかし、一部の環境ではそうならない。
\{m,n\}	直前のブロックの m 回以上 n 回以下の繰り返しにマッチする。例えば、正規表現「a\{3,5\}」は文字列「aaa」「aaaa」「aaaaa」にマッチする。

古いバージョンのgrepは選言演算子﹁\|﹂をサポートしていない。

例

正規表現﹁.at﹂は文字列﹁hat﹂﹁cat﹂﹁5at﹂のような3文字の文字列にマッチする

正規表現﹁[hc]at﹂は文字列﹁hat﹂と﹁cat﹂にマッチする

正規表現﹁[^b]at﹂は文字列﹁bat﹂以外の﹁.at﹂でマッチする全ての文字列にマッチする

正規表現﹁^[hc]at﹂は行の最初にあるときだけ、文字列﹁hat﹂と﹁cat﹂にマッチする

正規表現﹁[hc]at$﹂は行の最後にあるときだけ、文字列﹁hat﹂と﹁cat﹂にマッチする

符号点の範囲によってたとえば﹁アルファベット大文字﹂などを表現しようとすることは、時に問題をひきおこす。たとえばロケールに依存する例として、エストニア語のアルファベット順では、文字﹁s﹂の後に﹁z﹂があり、その後は﹁t﹂﹁u﹂﹁v﹂﹁w﹂﹁x﹂﹁y﹂と続くので、正規表現﹁[a-z]﹂ではすべての言語のすべてのアルファベット小文字にマッチするわけではない。そのため、POSIX 標準では次の表に示されているクラス、つまり文字の区分を定義している。

POSIX クラスを用いた正規表現	対応する表現	意味
[[:upper:]]	[A-Z]	英語の大文字
[[:lower:]]	[a-z]	英語の小文字
[[:alpha:]]	[A-Za-z]	英語のアルファベット
[[:alnum:]]	[A-Za-z0-9]	アラビア数字と英語のアルファベット
[[:digit:]]	[0-9]	アラビア数字
[[:xdigit:]]	[0-9A-Fa-f]	16進数字
[[:punct:]]	[.,!?:...]	英語の句読点
[[:blank:]]	[ \t]	（半角の）スペースとタブ
[[:space:]]	[ \t\n\r\f\v]	（半角の）空白
[[:cntrl:]]		制御文字
[[:graph:]]	[^ \t\n\r\f\v[:cntrl:]]	印字文字
[[:print:]]	[^\t\n\r\f\v[:cntrl:]]	印字文字とスペース

例:正規表現﹁[[:upper:]ab]﹂は英語の大文字﹁A﹂〜﹁Z﹂と﹁a﹂と﹁b﹂のうち1文字のみにマッチする。

いくつかのツールで使用できる、POSIX にないクラスとして﹁[:word:]﹂がある。﹁[:word:]﹂は通常﹁[:alnum:]﹂とアンダースコアからなる。これらが多くのプログラミング言語で識別子として使用できる文字であることを反映している。

拡張正規表現

拡張正規表現はEREとも呼ばれる。より現代的な拡張正規表現は多くの場合、現在の UNIXのユーティリティでコマンドラインオプションに﹁-E﹂を含めることで使用できる。

POSIXの拡張正規表現は伝統的な UNIX の正規表現に似ているが、いくつかの点で異なっている。

基本正規表現	拡張正規表現
(対応なし)	+
(対応なし)	?
(対応なし)	|
\{…\}	{…}
\(…\)	(…)
(	\(
)	\)
[	\[
]	\]
.	\.
*	\*
?	\?
+	\+
^	\^
$	\$

例えば、拡張正規表現﹁a\.(\(|\))﹂は文字列﹁a.)﹂や文字列﹁a.(﹂にマッチする。

GNU Emacsの正規表現

GNU findコマンドにおけるデフォルトの正規表現文法としても用いられる。︵findutils-4.2.28︶

GNU Emacs Manual - Regexps

Perlの正規表現

PerlはPOSIXの拡張正規表現さえも上回る豊富な文法を持っている。その例として、POSIXとは異なり、Perlの正規表現には﹁非欲張り量指定子﹂がある。標準の﹁*﹂は、例えば、正規表現﹁a.*b﹂の﹁.*﹂はできるだけ長い文字列にマッチしようとする。このふるまいを﹁貪欲﹂という。たとえば文字列﹁a bad dab﹂にマッチさせると、全体にマッチする。これに対し、Perlでは使うことができる正規表現﹁a.*?b﹂の﹁.*?﹂は、マッチするのであれば、できるだけ短い文字列にマッチする。たとえば文字列﹁a bad dab﹂に対して﹁a b﹂にだけマッチする。これを﹁非欲張り量指定子﹂と言う。

また、Perlには以下の定義済み文字クラスがある。

メタ文字	マッチする対象
\d	アラビア数字、つまり「[0-9]」
\D	アラビア数字以外の文字、つまり「[^\d]」
\w	アルファベット、アラビア数字またはアンダーバー、つまり「[a-zA-Z_0-9]」（ロケールに依存し、例えばウムラウト付き文字などの扱いが変わる）
\W	アルファベット、数字やアンダーバー以外の文字、つまり「[^\w]」
\s	空白文字、つまり「[ \t\n\r\f]」（ASCII文字集合の場合）
\S	空白文字以外の文字、つまり、[^\s]

すぐれた機能をもつPerlの拡張正規表現は、多くのプログラミング言語やソフトウェアで採りいれられている。例えば、JavaのPatternクラス、Python、Rubyなどがそうである。しかし、これらがPerlの正規表現と完全に互換である訳ではない。また、Perl Compatible Regular Expressions (PCRE) と呼ばれる汎用の正規表現ライブラリはアプリケーションに組み込まれ、Perlの正規表現とほぼ互換の機能を提供する。

正規表現ライブラリ

言語処理系やアプリケーションが正規表現をサポートしていない場合であっても、正規表現に必要な処理を提供する外部ライブラリを導入することで正規表現を使うことができる。以下にその一例を挙げておく。

PCRE

Perl互換のライブラリ。Eximのために開発され、ApacheやPostfixをはじめ、さまざまなソフトウェアに組み込まれている。

鬼車

正規表現オブジェクトごとに異なる文字エンコーディングを指定できる特徴をもつ。Rubyの1.9系列やPHPの5系列に採用されている。macOS用に検索ウィンドウを追加して移植したOgreKit︵Oniguruma Regular Expression Framework for Cocoa︶が存在する。

鬼雲

鬼車から派生した正規表現ライブラリで、Perl 5.10以降で導入された機能をサポートする。Ruby 2.0以降の標準ライブラリとして利用されている。

re2

PCREなどのバックトラック式ではなくオートマトンを用いることで、省メモリでマッチングを行うことができる。Googleが内部で利用している。

GNU Regex

GNU Cライブラリに含まれているため、Unix系では標準で利用できる。

Boost.Regex

Boost C++ライブラリによる実装。デフォルトでPerl互換の文法が使われるが、POSIXやECMAScriptなどの文法プロファイルを任意に選択することもできる。C++11規格にてBoost.Regexのサブセットが標準化された。

脚注

参考文献

●Jeffrey E.F. Friedl﹃詳説正規表現﹄歌代和正監訳、春遍雀來・鈴木武生共訳︵第1版︶、オライリー・ジャパン、1999年4月。ISBN 4-900900-45-1。 
●Jeffrey E.F. Friedl﹃詳説正規表現﹄田和勝訳︵第2版︶、オライリー・ジャパン、2003年5月。ISBN 4-87311-130-7。 

●Jeffrey E.F. Friedl﹃詳説正規表現﹄株式会社ロングテール・長尾高弘訳︵第3版︶、オライリー・ジャパン、2008年4月。ISBN 978-4-87311-359-3。https://www.oreilly.co.jp/books/9784873113593/。 

●Jan Goyvaerts、Steven Levithan﹃正規表現クックブック﹄長尾高弘訳、オライリー・ジャパン、2010年4月。ISBN 978-4-87311-450-7。https://www.oreilly.co.jp/books/9784873114507/。 

外部リンク

• 正規表現メモ - sed, grep, perl など様々なソフトの正規表現がまとめられている。