正規表現の起源
正規表現の起源は、神経生理学者たちの研究にある。
1940年代にさまざまな神経生理学者たちが、神経回路網を数学的に説明するために開発した方法が起源。
1956年、数学者であるクリーネ*1とチョムスキーが、その考え方に基づいて
論文をを著述し、そこで初めて正規表現の概念が紹介された。
ここで「正則集合の代数(the algebra of regular sets)」を説明するのに使用された式(expression)が
「正規表現(regular expression)」であり、現在の呼び名もこれに由来している。
クリーネが提唱した正規表現の考え方をごく大雑把に箇条書きすると、以下のとおり。
1. 何らかの文字の集合をΣとして考える
2. 0文字の文字列(空文字)は正規表現である
3. Σ内に含まれる任意の1文字は正規表現である
4. 正規表現を2つ連続させたもの(連接)は正規表現である
5. 2つの正規表現のいずれか(和)を示す概念は正規表現である
6. ある正規表現が0個以上連続したもの(閉包)は正規表現である
7. 上記2〜6までの考え方を繰り返し適用して導き出されるものは正規表現である
8. 演算の優先順位は閉包、連接、和の順に強い
1960年代、Unixの中心的な考案者であるトンプソンによって作られた
Unixのエディタ「qed」に、正規表現アルゴリズムが組み込まれることとなる。
その後、qedはUnixの標準エディタの地位を獲得する「ed」へと進化した。
edによって、その有用性が広く認知されるようになった正規表現は、
それをきっかけに、Unix系OSのツールに広く実装されるようになり、
現在ではMac、Windowsをはじめ、様々なフィールドにおいて重要な役割を担い続けている。
