おはこんばんちは!! 尾藤 a.k.a. BTO です。
みなさん正規表現使ってますでしょうか? 正規表現はプログラムを書く時にも使いますが、エディタや grep で検索するときなど文字列検索をするときには非常にお世話になっていると思います。 正規表現を書くことはあっても、正規表現がどのように処理されているのかを知らない人も多いのではないでしょうか。
今回、正規表現エンジンがどのような仕組みでできているのかを社内勉強会でやったので、その内容をまとめてみます。
正規表現技術入門
正規表現エンジンに関しては、正規表現技術入門というとてもわかりやすい本が出ています。
技術評論社
売り上げランキング: 117,162
実は本ブログで書いた内容も、かなりの部分はこの本から得た知識になっています。 正規表現エンジンに興味のある方には、ぜひ読んでみてください!!
チョムスキー階層
ノーム・チョムスキーという著名な言語学者がいます(ご存命です)。 チョムスキーは、形式言語を定義する形式文法を階層化しました。 これをチョムスキー階層と呼びます。
チョムスキー階層は次の4つに分かれます。
- 制限のない文法
- 文脈依存文法
- 文脈自由文法
- 正規文法
上の階層ほど、言語としての自由度が高く、計算機で処理するのが難しくなります。 名前から想像できると思いますが、正規表現はこのチョムスキー階層で言うところの正規文法にあたります。
正規表現とは
では、正規表現とは一体何なんでしょうか?
先程のチョムスキー階層で出てきた正規文法で定義された言語が正規言語です。 そしてこの正規言語を表現するための記法が正規表現です。
このように元々は正規言語を表すために作られた正規表現ですが、みなさんご存知のように現在では文字列のパターンマッチングのために使用されるようになっています。
正規表現による文字列の検索はとても便利だったので、いろんなツールに導入されました。 より便利にするために様々な機能拡張がおこなわれてきました。 そのため現在では本来の正規表現の定義を超えた機能を実装とかも出てきています。
世界初の正規表現エンジン
世界初の正規表現エンジンは、QEDというテキストエディタの文字列検索機能として実装されました。 この世界初の正規表現エンジンを実装したのがケン・トンプソン(ご存命です)です。
ケン・トンプソンは知る人ぞ知る超有名な計算機科学者で、業績は多岐に渡ります。 彼の業績には次のようなものがあります。
- UNIX
- C言語
- 正規表現エンジン
- ed(ラインエディタ)
- UTF-8
- Plan 9
- golang
ちょっとやばいですね... レジェンド過ぎます...
正規表現の限界
とても便利な正規表現ですが、チョムスキー階層で最下層に分類されているところからも分かる通り、その能力には限界があります。良く出てくる例としては、正規表現は括弧の対応を処理することができません。
つまり、次のような文字列、左に現れた開き括弧と同じ数の閉じ括弧が右側に現れるような文字列を処理することができません。
((( ... ))) # このような文字列は正規表現で処理できない
括弧の対応が組み込まれている文字列はいろいろとあります。
- 四則演算
- プログラミング言語
- HTML, CSS のような形式言語
これらの言語を処理する能力は正規表現にはありません(もちろん部分文字列を処理する能力は当然あります)。
メールアドレスは正規表現で処理できるか?
よくある話として、メールアドレスは正規表現でできるかどうかという話があります。 結論から言うと、本来の定義での正規表現でメƒールアドレスを表現することはできません。
メールアドレスはネストしたコメントを持つことができます。 上記の ((( ... ))) のような正規表現で処理できない構造は、ネストした構造を持つために使われるものですので、正規表現では表現できないことになります。
ただし、現在の正規表現には様々な拡張が行われていて本来の正規表現の能力を超える処理を提供しているものがあります。 具体的には、再帰の機能を持った正規表現エンジンでは、ネストしたコメントを表現することができます。 Perl や Ruby で使われている正規表現は再帰の機能を持っているので、メールアドレスを正規表現で処理することができます。
正規表現の定義
ちょっと前置きが長いですが、正規表現の話を進めましょう。 そのために、まずは正規表現を定義します。 正規表現の定義は次のようになります。 このでの定義は文字列処理に使われる正規表現について考えています。
- 文字は正規表現である
- X, Y が正規表現とする
- XY は正規表現である(連接)
- X | Y は正規表現である(選択)
- X* は正規表現である(繰り返し)
本来の正規表現では、空集合も受け付けるので、空集合は正規表現であるという定義が入りますが、ここでは省略しています。 なぜなら文字列処理を目的とする場合は、空文字(空集合)を処理する必要がないからです。 実際、文字列処理の正規表現では空文字を表現する記法がありません。
正規表現3つの基本演算
上記の正規表現の定義を見ると、正規表現は基本的な演算の組み合わせで構成されていることがわかります。 その基本的な演算は次の3つになります。
- 連接
- 選択
- 繰り返し
正規表現はとても便利なものなので、様々な拡張機能が実装されてきましたが、この基本演算の組み合わせで表現することができます。
一部上記の基本演算では表現できない機能もあります。 メールアドレスのところで出てきた再帰がそれにあたります。 この様な機能は便利なものではあるのですが、同時に正規表現の定義から外れてしまっているので数理的な意味を失うことにもなってしまいます。
連接
連接は非常に単純で、正規表現を繋げたものになります。 例えば次のような正規表現が連接になります。
abcdef
選択
選択は複数の正規表現から選択する機能です。 複数の正規表現を | で区切ります。 例えば次のような正規表現は、a, b, ab のいずれかの文字列を表します。
a|b|ab
繰り返し
繰り返しは、正規表現の0回以上の繰り返しを表します。 繰り返しの記号は * です。 例えば次のような正規表現は、aの0回以上の繰り返しを表します。
a*
拡張演算
上記の3つの演算に加えて、現在の正規表現では様々な拡張機能を提供しています。 機能はいろいろありますが、どれも3つの基本演算の組み合わせで表現することが可能です。
全てではありませんが、拡張された演算には次のようなものがあります。
- プラス演算: 1回以上の繰り返し
- 疑問符演算: 0回か1回
- 範囲量指定: n から m回の繰り返し
正規表現エンジンの実装方法
では、正規表現エンジンの実装をみていきましょう。 正規表現エンジンの実装方法は大きく分けると2種類あります。
- DFA型
- VM型
では、実装の説明を... と思ったのですが、長くなってきたので次回以降で。
まとめ
正規表現エンジン入門と言いつつ、エンジンの説明までたどり着きませんでした... ですが、正規表現の基本的な概念は理解していただけたのではないかと思います。 正規表現エンジンの実装には、正規表現自体への理解は必要不可欠です。
次は有限オートマトンと呼ばれる DFA での実装について書いていきます。