正規表現と数学
正規表現は、プログラマーから見ると文字列処理における強力なプログラミングツールの一つと言えます。しかし、この概念の大本にはしっかりとした数学の理論体型が存在します。正規表現の数学的な側面を理解すると、正規表現を実装する場合の助けとなります。
正規表現の定義
正規表現は元々は数学的な概念であり、厳密な定義が存在します。この定義を大まかに説明すると、以下のようになります。
「任意の文字（空文字を含む）を、以下の3つの規則を繰り返し適用して組み合わせた表現を、正規表現とする」
| 表記 | 説明 |
| A|B | 文字列の和集合(A or B) |
| AB | 文字列の連結 |
| A* | 文字列の繰り返し |
例
例えば、以下の例は、全て上記の定義による正規表現となります
- x|y
- perl
- ab*c
- perl|ruby
- (p(erl|ython|hp)|java)*
実用上の正規表現との関係
実用上の正規表現は、数学的な正規表現をベースに作られています。ここでは、その関係を見てみましょう。
定義で書き換え可能なもの
通常、プログラミング言語から利用される正規表現には、この数学的な定義以外の記法が多数含まれますが、その大部分は数学的な3つの定義で書き換えが可能です。以下に、書き換えができる例を載せておきます。
| 実用上の表現 | 数学的な定義 |
| a+ | aa* |
| a? | a| |
| a{1,2} | a|aa |
| [abc] | (a|b|c) |
部分一致によるマッチング
数学的な正規表現は、その正規表現から作られる文字列の集合を表しています。ある文字列が、正規表現が表す文字列集合に含まれるかを判定することは、そのまま全文一致（java.util.regex.Matcher#matches()など）マッチングとなります。しかしほとんどの場合、プログラミング言語で使える正規表現で行うことは、長い文字列の一部分に対するマッチ（java.util.regex.Matcher#find()など）をさせるということです。
部分一致をさせるためには、入力文字列を細かく切った部分文字列に対してマッチングを行う必要があります。部分一致は、前方一致と後方一致を併せたものと考えることができますので、それぞれを別々に見てみましょう。
前方一致
まず前方一致は、正規表現エンジンが文字列を1文字ずつ受けて判定を進めて行く性質を利用します。詳しくは後述しますが、正規表現の内部状態は、1文字入力するごとに「受理状態」と呼ばれる状態とそうでない状態との間を都度変化します。そして、最終的に「受理状態」となることが、マッチした、と言う状態に該当します。
そこで、文字列を一度に最後まで入力をせずに、受理状態となった時点で処理を終了させてみます。例えば、正規表現「cat|rat」に「catch」をマッチさせる場合を考えます。マッチングの際、正規表現エンジンには文字が一文字ずつ「c」「a」「t」「c」「h」と順に入れられていきます。全文一致の場合は、最後の「h」を入れ終わった後に、この内部状態が受理状態にあるかをチェックします。これに対し、前方一致をさせたい場合には、文字を入力する度に内部状態の判定を行います。この例だと、「c」、「a」、「t」 の3文字まで入れた時点で、正規表現は受理状態となります。そして、残りの 「ch」を切り捨ててマッチ成功と返せば、前方一致を実現できます（ただし、最長マッチさせる必要がある場合は、最も後に現れた受理状態を使います）。
後方一致
一方、後方一致のマッチは、正規表現にマッチさせる文字列を一文字ずつ短くしながら検査を繰り返すことで実現できます。例えば、正規表現「cat|rat」が「autocrat」に後方一致でマッチするかを調べる場合、autocrat → utocrat → tocrat → …… とマッチ対象を短くしていきます。そして、 入力文字列が rat となった時点で、 この正規表現とマッチします。
位置にマッチする表現
正規表現の中には、文字列中の位置にマッチするものがあります。このような正規表現は、マッチした時点の文字列位置を判定させることで実現可能です。例えば、以下のようなものがあります。
| 表記 | 説明 |
| ^ 行頭 | マッチした箇所が先頭かを判定 |
| $ 行末 | マッチした箇所が行末かを判定 |
| \b 単語区切り | マッチした箇所が区切り位置かを判定 |
数学的な定義を超えたもの
プログラミング言語上の正規表現エンジンのほとんどは、後方参照と言う機能を使えます。これは、正規表現のマッチング中にマッチしたある部分と同じ文字列にマッチさせる機能で、文字列の繰り返しを表現するのに利用できます。
foreach my $str ('hogehoge', 'foofoo', 'hogefoo'){
if($str =~ /^([a-z]*)\1$/){
print "match: $str\n";
}
}
# 結果
match: hogehoge
match: foofoo
残念なことに、数学的な3つの定義ではこの正規表現が表す文字列集合を表現できません。このことは数学的に証明も可能です。つまり、現在広くプログラミング言語で使用されている正規表現は、厳密には数学的な正規表現にはなっていません。
