正規表現

テンプレート:Redirect 正規表現（せいきひょうげん、テンプレート:Lang-en-short）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。

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

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

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

ほとんどのプログラミング言語では、構文またはライブラリによって正規表現を使うことができるようになっている。構文やライブラリに正規表現を備えたプログラミング言語やユーティリティとして、grep、AWK、sed、Perl、Tcl などがある。

また、プログラミング言語の開発などに用いる lex も正規表現を使う。

それぞれの言語やアプリケーションで細部の仕様が異なっているが、POSIX により標準規格も定められそれに準拠するものも増えてきてはいる。

基本的な概念

しばしばパターンと呼ばれる正規表現は、文字列群を表現する表現法である。通常、全ての要素を列挙することなく文字列群を簡潔に表現するのに用いられる。例えば、「Handel」、「Hendel」、「Haendel」 という三つの文字列を含む集合は 「H(e|ae?)ndel」 というパターンで表現できる（あるいは、パターンは個々の三つの文字列にマッチすると言われる）。ほとんどの形式では、もし特定の集合にマッチする何らかの正規表現が存在すれば、無限の数のそのような表現がある。ほとんどの形式では正規表現を構築するのに次の演算子を提供している。

選言

縦棒は選択肢を区切る。例えば「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」 は 「ggle」、「gogle」、「google」 などにマッチする。

+

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

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

歴史

正規表現の起源は、いずれも理論計算機科学の一分野であるオートマトン理論や形式言語理論にみることができる。これらは計算のモデル化（オートマトン）や形式言語の分類方法などを扱う学術分野である。数学者のスティーヴン・クリーネは1950年代に正規集合と呼ばれる独自の数学的表記法を用い、これらの分野のモデルを記述した。ケン・トンプソンはテキストファイル中のパターンにマッチさせる手段として、この表記法をエディタQEDに導入した。彼はこの機能を UNIX のエディタ ed にも追加し、後に一般的な検索ツールであるgrepの正規表現へと受け継がれていった（grepは ed エディタの正規表現検索コマンド g/re/p から派生した単語である。re は正規表現（regular expression）の頭文字。）。これ以降、トンプソンの正規表現の適用にならい、多くのUNIX系のツールがこの方法を採用した（例えば expr、awk、Emacs、vi、lex、Perl など）。

Perl と Tcl の正規表現はヘンリー・スペンサーによって書かれたものから派生している（Perlは後にスペンサーの正規表現を拡張し、多くの機能を追加した）。フィリップ・ヘーゼルは Perl の正規表現とほぼ互換のものを実装する試みとしてPerl Compatible Regular Expressions（PCRE）を開発した。これはPHPや Apache などといった新しいツールで使用されている。Perl 6では、正規表現の機能を改善してその適用範囲や能力を高め、Parsing Expression Grammar を定義できるようにする努力がなされた。この結果として、Perl 6 文法の定義だけでなくプログラマのツールとしても使用できる、Perl 6 rules と呼ばれる小言語が生み出された。これらの規則は正規表現の機能のすべてを保持しながら、副規則を通して再帰下降構文解析のバッカス・ナウア記法の定義を行うことができる。

構造化情報標準における、文書やデータベースのモデル化に対する正規表現の使用は重要である。これは1960年代に始まり、ISO SGMLのような産業標準が確立された1980年代に拡大した。構造規定言語の標準の中核は正規表現である。より単純かつ明白な例としては、DTD要素グループの構文において正規表現が使われている。

構文

標準

The nice thing about standards is that you have so many to choose from. --Andrew S. Tanenbaum

Unixの標準であるPOSIXでは、"Simple Regular Expressions"・"Basic Regular Expression (BRE)"・"Extended Regular Expression (ERE)"の3種類の記法が示されている。このうち、Simple Regular Expressionsはhistoricalやlegacyと書かれており、backward compatibilityを提供するものとされ、標準の将来の版では"may be withdrawn"と注意されている。

Simple Regular Expressions

Simple Regular Expressionsの仕様は<regexp.h>のマニュアルページとして示されている。

Basic Regular Expression

ほとんどの正規表現を利用する UNIXのユーティリティ（grepやsed）のデフォルトはこれである。

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

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

特定の正規表現の実装では、一部のメタ文字の前のバックスラッシュを異なって解釈する。例えば egrep や perl は、バックスラッシュの付いていない 括弧や縦棒 "|" をメタ文字と解釈し、バックスラッシュの付いているものをリテラルに解釈する。古いバージョンの grepは選言演算子 "|" をサポートしていない。

例

".at" は hat、cat、bat のような三文字の文字列にマッチする

"[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]	印字文字
[:print:]	[^\t\n\r\f\v]	印字文字とスペース

例: [[:upper:]ab] は大文字と a と b のみにマッチする。

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

Extended Regular Expression

より現代的な拡張正規表現は多くの場合、現在の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" の .* はできるだけ長い文字列にマッチしようとする。このふるまいを「欲張り」（greedy）という。たとえば "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	空白文字、つまり大抵の制御文字クラス \f、\n、\r、\t や \v
\S	空白文字以外の文字 [^\s]

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

正規表現ライブラリ

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

• PCRE

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

• テンプレート:仮リンク

正規表現オブジェクトごとに異なる文字エンコーディングを指定できる特徴をもつ。Rubyの1.9系列やPHPの5系列に採用されている。

• テンプレート:仮リンク

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

• GNU Regex

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

形式言語理論における正規表現

アルファベット A = {a₁,...,a_n} 上の正規表現は次のように定義される。正規表現の表す集合が、その正規表現の表す言語である。

• ∅ は正規表現である。これは空集合 ∅ を表す。
• a_i（A の任意の要素）は正規表現である。これは a_i のみからなる集合 { a_i } を表す。
• X と Y が正規表現ならば、
  • X|Y も正規表現である。これは X の表す集合と Y の表す集合の和集合を表す。
  • XY も正規表現である。これは X に含まれる記号列に Y に含まれる記号列をつなげてできる記号列の集合 { ab | a ∊ X, b ∊ Y } を表す。
  • X* も正規表現である。これは X に含まれる記号列を 0 個以上つなげて出来る文字列の集合 ∪ { Xⁿ | n ≥ 0 } を表す。
• 上記の帰納的導出によって構成される記号列のみが正規表現である。

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

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

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

X|Y の代わりに X+Y と書くことや、XY の代わりに X·Y と書くこともある。また、「|」や「*」の優先順位を明確にするために括弧を使うこともある。

関連項目

• 文字列探索
• オートマトン
• Parsing Expression Grammar
• コンピュータ言語

参考文献

• テンプレート:Cite book
  • テンプレート:Cite book
  • テンプレート:Cite book
• テンプレート:Cite book

脚注

テンプレート:脚注ヘルプ

外部リンク

• 正規表現メモ - sed, grep, perlなど様々なソフトの正規表現がまとめられている
• 正規表現/文字コード最新リンク2005
• Regular Expression(Riue ちゃんの正規表現講座) - Index