Rubyで正規表現エンジンを書いた

Rubyで正規表現エンジンを書いた

なぜかいたか

去年くらいに、Padrinoのルーティングエンジンを1から書き直す上で正規表現について色々と考えることになった。 その際に自分が本当に中途半端な理解のまま正規表現を使ってきたことを実感したので、理解を深めるため、というか学習のために実際に正規表現エンジンを書いてみた。

namusyaka/onibi

学習には@hirataraさんが昔連載していた正規表現エンジンを作ろうを使わせてもらった。 この連載をなぞっていくだけで正規表現エンジンができるので、そこに多少アレンジを加えて楽しむのが良いと思う。自分はそうした。 加えて自分は、参考資料として挙げられていた計算理論の基礎をたまたま持っていたので、並行して読み進めた。

元の実装と違うところ

連載に従って進めることで完成する正規表現エンジンよりも、サポートするメタ文字をいくつか増やしている。 といっても、正規表現として扱う文字列を字句解析する前に、解析可能なメタ文字を使った正規表現に変換するだけ。 例えばasdf+はasdff*と意味上は等価であり、変換することができる。 実装はonibi/ast/converter.rbの部分。 最小の実装で、サポートしていないメタ文字を表現することができるのは面白いと思った。当たり前ではあるのだけど。

感想

字句解析やオートマトンの生成、といった部分の実装については、基本的に元の連載の内容をなぞっただけ。 自分は実装時に、連載中に使用されるプログラミング言語(Python)ではなく、Rubyを使って書くだとか、実用する気はないんだからガンガンDSLにしてクールに書こう、みたいなところを意識した。 そのおかげか、部分集合構成法を用いて非決定性有限オートマトン(NFA)を決定性有限オートマトン(DFA)に変換するところなど、理解が難しかった部分を中心に頭をひねって、実際のコードに落とし込むフローを楽しめたと思う。 これに取り組む前と後では、正規表現に対する考え方がかなり変わったので、作ってみて正解だった。

おわり。