読者です 読者をやめる 読者になる 読者になる

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

Ruby

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

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

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

  • 作者: Brian Kernighan,Jon Bentley,まつもとゆきひろ,Andy Oram,Greg Wilson,久野禎子,久野靖
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2008/04/23
  • メディア: 大型本
  • 購入: 30人 クリック: 617回
  • この商品を含むブログ (191件) を見る

この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クラスを実装するとこまでいきたいなぁ.