正規表現と正則表現は何が違うのかわかりません。

わかりません。


それはいいとして、オートマトン勉強してたのは(http://d.hatena.ne.jp/w_o/20070218#p4)、別に学歴コンプレックスなわけではなく、正規表現やろうとしてたからなのだった。
で、正規表現ライブラリを自作するのは面白いかもしれないね。と、思ったとかの話。
を、書こうと思ってたらもう大分飽きてたのだった。


まず、ネタとして、NFAシミュレータがネイティブ機械語になってたら速くなるんじゃないかー、とか、思ったのだけど、NFAはオーダーがヤバいので、あんまりコンパイルしても意味無いというのに気付いたというか、http://swtch.com/~rsc/regexp/regexp1.html ここ読んだとか、それ以前に、NFAとDFAの性能の違いは基本中の基本のような気が。


とにかく、NFAとDFAがあって、NFAは時間のオーダーがやばい。DFAは空間のオーダーがやばい、という話。が、基本。


なのだけど、実際には、もうちょっと色々あって

  • いわゆる正規表現は正規表現じゃないかも（オートマトンと等価じゃない）
  • いくつかパターンを決め打って最適化すればオーダーレベルで効果があるかも

というのがある。具体例は思い付かない。


つまり、正規表現といえども、そんなに単純じゃなくて、どういう状況で利用するのを想定してるのか？とか、考えて、実装する規模と最適化を考えないといけないなー、とか思ったのでした。
暇でヒマで時間がありあまってる人は、暇潰しに正規表現ライブラリを実装してみるのもよいかもしれないし、多分やめたほうがいい。


というわけで、正規表現の実装ぐらい一瞬だよ、と思ってたのだけど、壁が思ってたより大分高かったので、グダグダ。
けど、何もしないのも負けた気分なので、一応何か作った↓
http://morihyphen.hp.infoseek.co.jp/files/rejit.tar.gz


rejit（れじっと）は RE の JIT コンパイラです。正規表現をx86 NFAシミュレータに変換します。超基本的なところだけ実装してます。（+*?|）


あと、DynASMおもろい。昔書いた気がするけど。

static void
match_word( struct rejit_State *s, unsigned int c )
{
	| mov	edx, dword[INPUT_PTR]
	| add	INPUT_PTR, 4
	| cmp	INPUT_PTR, INPUT_STATE->end // inputptr >= end 
	| jg	->MATCH_FAILURE
	| cmp	edx, c
	| match_failure
}

こんな感じでJITコンパイラが書ける。