正規表現



正規表現 (Regular Expression)について

正規表現とは

正規表現とは、数学者であるスティーヴン・コール・クリーネ(Stephen Cole Kleene)によって考案された、文字列の集合を一つの文字列で表現する方法です。コマンド(grep, sed awk, viなど)に正規表現を用いると、文字列の検索・置換・消去が容易となります。


正規表現における基本記法


メタ文字 (meta-character)

正規表現では、特別な意味を持つ文字を「メタ文字」と呼びます。

メタ文字を単なる文字として扱いたい場合は、それらメタ文字の前に「\(バックスラッシュ)」を付加します。

なお、メタ文字の意味はシステムや処理系によって若干異なります。以下に挙げるのは利用頻度が高く、一般的に用いられるメタ文字です。

*      直前の文字の0回以上に一致
+      直前の文字の1回以上に一致
.      1つの任意文字(A, B, Cなど、ただし\nを除く)
?      直前の文字の0回または1回に一致
{n}    直前の文字がちょうどn回に一致
{n,}   直前の文字がn回以上に一致
{n,m}  直前の文字がn回以上,m回以下に一致
[xyz]  x,y,zの何れか1文字に一致
[^A]   否定:A以外の文字
x|y    選択:xまたはyに一致
()     グループ化
\w     英数文字かアンダーバーを表す(a-z,A-Z,0?9,_)
\d     数値文字を表す(0-9)
^      行の最初
$      行の最後
\s     空白,タブ
\S     空白文字以外
\d     数値文字
\D     \d以外
\w     英数文字かアンダーバー
\W     \w以外の文字
\b     単語の境界

正規表現とオートマトン

正規表現におけるパターンマッチの基本的な動作原理は、有限オートマトンという仕組みを用いて実装されています。現在のシステムで用いられる正規表現は、クリーネが考案した正規表現よりも遥かに複雑化していますが、動作原理の基本が有限オートマトンという点は変わりません。


有限オートマトン (Finite Automaton)とは

有限オートマトンとは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」です。つまり、ある入力に対し、ある処理を自動的に実行し、ある出力を出すシステムのことです。


正規表現が特定の文字列にパターンマッチするかどうかは、有限オートマトンによって判定することができます。正規表現を有限オートマトン、つまり状態遷移図(State Transition Diagram:オートマトンを図形的に表現したもの)に変換し、調べたい文字列を与えて内部の状態を遷移させていき、入力文字列が受理される確認します。遷移結果が受理状態に達すれば、その正規表現は入力として受け取った文字列にマッチしたと判断することができます。


有限オートマトンには以下の二種類があり、どちらで実装されているかによって正規表現の挙動が大きく異なってきます。DFAは表を作るのに多少時間がかかるものの、NFAに比べてマッチしているかどうかを調べるスピードが非常に速いのが特徴です。




関連ページ



スポンサード リンク