正規表現とは何か

正規表現について調べていたら正規言語、正規演算、正規表現、正規文法、有限オートマトン、文脈自由文法などの概念が出てきて混乱した。それで、分かったと思う分だけをまとめてみる。

まず有限オートマトンだが、これは、メモリの極端に少ないコンピュータのことだ。このコンピュータに文字列を入力すると、入力し終わった時にコンピュータは「受容」か「拒否」かの値を返す。正規言語とは、この有限オートマトンで受容の値が帰る文字列全ての集まりのことだ。一個の有限オートマトンで、複数の（無限の）文字列の集まりを定めることができる。このあつまりが、そのオートマトンによって定められる言語だ。

この正規言語を二つを合わせたものはやはり正規言語になる。もちろんこの正規言語に対する有限オートマトンは、二つの正規言語に対応する有限オートマトンとは異なるが、それらから合成することができる。

また、二つの正規言語の中からそれぞれ文字列を取り、その二つの文字列を連結させる。このような連結された文字列の全ての集まりもまた正規言語になる。

さらに正規言語の文字列を複数回連結した文字列を作ることができるが、これも正規言語になる。このように正規言語の和集合、連結、複数回の連結の繰り返しも正規言語を作る。このような正規言語に対する演算を正規演算という。

正規表現とは、要素的な文字列から選択、連結、繰り返しという３つの演算を使って作り出された文字列を定義する演算規則のことである。正規言語と、正規表現は発想が違うが、同じ文字列の集まりを表すことができる。

また、正規言語は正規文法を使って作ることができる。正規文法は形式文法の一つで、左側に非終端記号 S があり、右側には終端記号か、一つの非終端記号と一つの終端記号しか許されない文法だ。

形式文法は、非終端記号を別の非終端記号や終端記号に置き換えるためのルールを示した式だ。例えば、次の文法は正規文法だ。

1. S -> aS

2. S -> bA

3. A -> ε

4. A -> cA

ルール 1 から aaS が導出され、これにルール 2 を適用することで、aabA が導出される。これにルール 4 を２回適用すると aabccA が導出される。最後に、ルール 3 を適用して aabcc という文字列を導出できる。これは正規表現の a*bc* に相当する。

文脈自由文法とは上のような置き換えの規則で、左側に終端記号が１つだけ置くことが許されているものだ。次の文法は文脈自由文法の例だ。

1. S -> aSb

2. S -> ab

プログラミング言語は大半が文脈自由文法で記述できるので、プログラム言語を作る時の重要な作業は、そのプログラミング言語を記述できる文脈自由文法をプログラムすることだ。

文脈自由文法は正規文法を包含しており、文脈自由言語は、正規言語を含んでいる。また、正規言語を正規表現で記述するときには、選択、連結、繰り返しの３つしか使わない。プログラム言語の正規表現の多くの表現は、この三つの演算の組み合わせのシンタックスシュガーだ。

正規言語は、有限オートマトンで定義できる。また、文脈自由言語は、有限オートマトンにプッシュダウンスタックを追加した、プッシュダウン・オートマトンで定義できる。

文脈自由文法は、正規表現にスタックを加えたものと考えることができる。また、文脈自由文法は、正規文法に再帰的定義を追加したものと考えられる。

また、これらの言語の数学的議論では、文字列の先読みは出てこない。したがって、構文解析器の文法の設計に現れる「文字列の先読み」は、言語としての定義としてよりは、構文解析の効率を上げるための付加的な工夫のように思われる。

数学的な発想から生まれた正規表現がケン・トンプソンによってコンピュータのプログラミングに導入された後、その本来の意味は忘れられ、便利なパターンマッチ機械としての利用法のみが前面に出てきているのだろう。しかし、構文解析プログラムの文法をプログラムするときは、形式文法の本来の意味も考えておかなければならない。

例えば電卓のプログラムだが、文法規則だけを抜き出すと次のようになる。

expression -> term (+ term)*

term -> factor (* factor)*

factor -> number / ’(’ expression ’)’

expression の定義の term (+ term)* は正規表現の連接と繰り返しが適用されているのでこれは正規表現だ。文脈自由文法は正規表現を含むので、これは文脈自由文法にもかなっている。factor の定義の右項は number という終端記号と、expression という非終端記号の重みつき選択になっている。正規表現では右項には終端記号または非終端記号と終端記号の連接しか認められていないので、この定義は正規表現では表現できない。この部分が括弧の中の再帰的文法を定義している。したがって、再帰的な構造についての文法の適用は正規表現ではできないのがわかる。このような言語を導出するためには、文脈自由文法が必要なのだ。

上の文法で定義した再帰下降パーサでは expression 関数が呼ばれると、その関数から term 関数が呼ばれ、term 関数から factor 関数が呼ばれ、factor 関数で number 正規表現のマッチングが行われる。これは、形式文法の非終端記号の文法による置き換えを忠実に反映している。したがって、再帰下降パーサはトップダウンの生成文法の実装になっている。これは、パーサコンビネータの場合も一緒で。expression 関数が呼ばれるとその中から term 関数が呼ばれ、term 関数から factor 関数が呼ばれという再帰下降パーサと同じような非終端記号の置き換えが起こる。つまり、再帰下降型で記述したパーサと、パーサコンビネータで記述したパーサは同じものであるのが分かる。

パターンマッチャー P モジュールは、選択、連接、繰り返しのコンビネータしかないが、理論的にはこれだけで、文脈自由文法の言語は導出可能だ。他のパーサに習って、肯定先読みや、否定先読みのパーサも記述したが、これば、文法の問題というよりは、パーサの効率に関係するものだ。

P モジュールはマッチしたパターンの消費や、トラックバックの処理のオーバーヘッドがひどいのでプログラム言語のパーサの記述には向かないが、少なくとも、原理的にはそのような言語の記述も可能だと思われる。

ただ、ここで強調したいのは、データ型に関数型を持ち、正規表現の装備されたプログラム言語なら、本当に小さいライプラリで、パーサコンビネータ型の文脈自由文法を書くことができるということだ。動作の効率に関しても、正規表現を文字列のキャラクタポインタの位置から始めることができれば、問題ないはずだ。JavaScript の正規表現では g オプションを使った時に RegExp.prototype.exec() メソッドでそういうことができるが、これが String.prototype.match() メソッドでも行えるようになれば、十分実用的なパーサが書けるようになるはずだ。

手軽に文脈自由文法のパーサをかけるようになれば、自作のプログラムの関数に渡す引数などをもっと自由にコントロールできるようになるのではないだろうか。電卓のパーサくらいなら、単に慣れの問題だけで難しいところはないと感じられるようになる。正規表現とデータ型としての関数型の普及で、構文解析プログラムはプログラムの言語の開発者だけでなく、一般のプログラマも気軽に利用できるような環境になってきている気がする。