2011-11-16

正規表現ライブラリを書き直そう

組み込みの文字セットが完了したので、いよいよ本丸に取り掛かろう。
現在SagittariusではJavaから移植した正規表現を使っている。別にこれで問題はないと言えばないのだが、気になるのはその中で独自のASTを持っていること。
せっかくSchemeなんだしS式でASTを構築したほうがいいんじゃね?とちょっと思えてきた。
なぜそう思ったか?
世の中にはPCREとSREという正規表現のタイプがあるらしい。まぁ、もっとあるだろうが。っで、PCREは超有名なPerlの正規表現。SREはS式で書かれた正規表現らしい。Perl形式の正規表現をSREに置き換えて、ってやれば、PCREもSREも使えて一粒で2度おいしい感じがする。
と、こういうことをやっているのが、irregexというAlex Shinn氏が書いてるScheme用の正規表現ライブラリなわけだ。とりあえず、それを足がかりに文字列->SREなものを作って、ごにょごにょするか、もう少し資料をあさってみるか。(鬼車のソースを眺めてみるのもありか)

いろいろあさってみて、実装方針は大まかに分けて2つかなぁと。
  1. コンパイルはASTまでにして、MatcherはASTをたどってマッチさせる。(現状はこれ)
  2. Gaucheのように正規表現自体を一種の言語(なんだけど)に見立ててVMを作成、Matcherは一種の仮想マシンでインストラクションを実行してマッチさせる。
1の方法は実装が割りと簡単なんだけど、遅い。まぁ、僕の実装方法が悪いのかもしれないが。
2の方法はRubyでも使われている鬼車も取っていた。ということは高速に動かすには2の方がいいのか?
この辺の参考書籍とかWebとかないのだろうか?悩ましいなぁ。

No comments:

Post a Comment