BeutifulCodeの正規表現エンジンをRubyに移植

今日，BeautifulCodeを読み始めたんだけど，1章目から正規表現エンジンを実装していたりして，かなり刺激的な内容だった．残りの章を読み進めていくのが楽しみ．

ビューティフルコード (THEORY/IN/PRACTICE)

この1章には，C言語で書かれた正規表現エンジンのコードが記載されている．この正規表現エンジンは，正規表現のうち

. ^ $ *

が使えるようなやつで，もともと，プログラミング書法に載っていたやつらしい．教育のために非常に簡潔できれいに書かれていて読みやすい．

そこで，せっかくなので，この正規表現エンジンをRubyに移植して理解を深めるなどしてみた．とりあえず，書いたコードをみたいひとはこちらへ．

追記: コードの簡単な説明

このコードはmatchとmatchhereとmatchstarという3つの関数で構成されている．ユーザが使うのはmatch関数になる．

match('a*x', 'aaaabaaaax')

このように正規表現，対象テキストの順番で引数に文字列を渡して使う．対象テキストが正規表現にマッチすればtrue，しなければfalseを返すようになってる．

matchhereはmatchの中で使われている関数．引数はmatchと同じなんだけど，対象テキストの先頭からのマッチしかみない．逆に，matchの中では先頭をずらしながらmatchhereを実行している．

matchstartは*を処理する関数で繰り返しを見つけて，そののこりをマッチさせるとかをやっている．ややこしいのでコードを参照．

このコードの中のDEBUG=trueにすると，マッチのようすとかが見れてちょっとおもしろい．いかにも大変そうなテキストとパターンをマッチさせると以下のように．

irb -r matcher
>> match('a*x', 'aaaabaaaax')
"aaaabaaaax" =~ /a*x/
"baaaax" =~ /x/
"abaaaax" =~ /x/
"aabaaaax" =~ /x/
"aaabaaaax" =~ /x/
"aaaabaaaax" =~ /x/
"aaabaaaax" =~ /a*x/
"baaaax" =~ /x/
"abaaaax" =~ /x/
"aabaaaax" =~ /x/
"aaabaaaax" =~ /x/
"aabaaaax" =~ /a*x/
"baaaax" =~ /x/
"abaaaax" =~ /x/
"aabaaaax" =~ /x/
"abaaaax" =~ /a*x/
"baaaax" =~ /x/
"abaaaax" =~ /x/
"baaaax" =~ /a*x/
"baaaax" =~ /x/
"aaaax" =~ /a*x/
"x" =~ /x/
"" =~ //

なげえ

サンプルのCのコードをRubyに移植するに当たっていくつか気づいたことがあったので，以下はそのメモ．正規表現エンジン自体への考察はないので，それが読みたい人はスルーしてね．

Ruby ひく 正規表現

まず，Rubyはそもそも正規表現をそなえている言語なので，正規表現をつかわずにプログラムを書こうとすると，少し大変になる．

もとのCのコードはポインタをうまく使って，かなり簡潔なコードになっている．たとえば，ある文字が連続する部分を見つけて，その後ののこりの文字列を見つけるためのコード(ある文字がcならccccccxyzという文字列のxyzを見つける)は，サンプルでは以下のようになっている．cが連続する文字，textが対象の文字列としたとき，

for (t = text; *t != '\0' && (*t == c || c == '.'); t++)
    ;

となる．tがもとめる文字列を指している．

で，これをRubyで書き下すと，

start = 0
text.each_byte do |tc|
    break if tc.chr != c && tc.chr != '.'
    start += 1
end
t = text[start..-1]

という感じになって，Rubyにしてはもっさりした感じになってしまう．いや，さすがにもう少しましな書き方があるはずだよ，

/#{c}*(.*)/ =~ text
$1

たしかに，これくらい簡潔だとRubyらしい．Rubyできる子じゃん！って，これ正規表現つかってるよorz

さすがに，Rubyで正規表現を使わないことにすると，文字列処理が若干大変になってしまう．少なくとも，ぱっとみわかりにくいコードになってしまう．簡潔な記述が強みのLLにとっては正規表現はかなり重要なパートナーなのだぁ．

String#[]

さらに，細かいことで，Ruby1.8.6の文字列に添え字でアクセスすると，

>> "hello"[0]
=> 104

なんか，文字コードが帰ってくる．twitterで聞いてみたところ，わりと常識っぽくて，

>> "hello"[0].chr
=> "h"
>> "hello"[0..0]
=> "h"

などとするのが良いらしい．さすがにこの挙動はだめな感じがすると思っていたら，1.9ではちゃんとStringが返るとのこと．twitterで答えてくださったみなさま，ありがちょー！

ソースコード

とりあえず，今日書いた正規表現エンジンをgitの練習もかねてgithubで公開してみた．

hakobe's practice-of-beautiful-code at master -- GitHub

最新の版では+が使えるようにしてあったり，ちょっとだけ改良してある．

他に，?を実装したり，処理をパターンのコンパイルとマッチングに分割するなど，改良するポイントはいろいろあるので，勉強ついでにちびちびコミットしていくかも．最終的には，PatternクラスとMatcherクラスを実装するとこまでいきたいなぁ．