簡易な正規表現エンジンを実装する

GA technologiesでソフトウェアエンジニアをしている中坂です。 先日社内で正規表現エンジンの実装の話題で盛り上がりました。ソフトウェアエンジニアであれば普段の開発の中では当たり前のように正規表現を使っていると思いますので、記法や挙動に関する知識はある程度持っているはずです。しかしながら、具体的に我々の書いた正規表現がいかにしてテキストにマッチするのか、その内部の仕組みまで理解している人は多くないと思います。 今回は「正規表現エンジン」の実装を実際に示しながら、普段当たり前のように書いている正規表現がどのように処理されているのかを深掘っていきます。 全体の流れ この記事は少々長いので、まず最初に正規表現エンジンを実装するまでの流れをザッと書いておきます。 はじめは正規表現エンジンを理解するために必要な基礎知識として有限オートマトンの概念を説明します。有限オートマトンには主に決定性

[razokulover]

バカデカ記事を書いてしまった...(誰が読むんだ)