元になっているのは『プログラミング作法』に載っている、ロブ・パイクが書いたコード(以下「ロブ・パイク版」)ですが、40行以内で正規表現エンジンを構築 | POSTD の方を見て書いてみました。JavaScript の方が読み慣れているのと、リポジトリにテストコードが用意されていたためです。
def drop(text, n)
text.chars.drop(n).join()
end
def empty?(str)
str.nil? || str.empty?
end
def match_one(pattern_char, char)
return true if empty?(pattern_char)
return false if empty?(char)
pattern_char == "." || pattern_char == char
end
# ロブ・パイク版では match
def search(pattern, text)
if pattern[0] == "^"
match(drop(pattern, 1), text)
else
match(".*" + pattern, text)
end
end
# ロブ・パイク版では matchhere
def match(pattern, text)
return true if empty?(pattern)
return true if empty?(text) && pattern == "$"
case pattern[1]
# when "?"
# match_question(pattern, text)
when "*"
match_star(pattern, text)
else
match_one(pattern[0], text[0]) &&
match(drop(pattern, 1), drop(text, 1))
end
end
# def match_question(pattern, text)
# (
# match_one(pattern[0], text[0]) &&
# match(drop(pattern, 2), drop(text, 1))
# ) ||
# match(drop(pattern, 2), text)
# end
def match_star(pattern, text)
(
match_one(pattern[0], text[0]) &&
match(pattern, drop(text, 1))
) ||
match(drop(pattern, 2), text)
end
たったこれだけで正規表現の基本的な機能が実現できるのすごい&おもしろいですね。
ロブ・パイク版では .
^
$
*
だけをメタ文字としてサポートする最低限の実装をまず示し、演習問題で ?
などを追加する流れになっています(なので、上に貼ったコードでは ?
の部分をコメントアウトしてみました)。
書籍『ビューティフルコード』では「1章 正規表現マッチャ」をブライアン・カーニハンが書いており、ロブ・パイク版について解説しています。
このコードが生まれた経緯について書かれていて、ここもおもしろい。
1998年、ロブ・パイク(Rob Pike)と私は、『プログラミング作法』(原題『The Practice of Programming』、Addison-Wesley刊)という本を執筆していました。(略)
問題は、既存の正規表現パッケージはどれも大き過ぎたということでした。(略)それでは教育用に適しているとは到底言えません。
そこで私はロブに、正規表現の基本的な考え方が読み取れる最小限の、ただしそれでいて有用でつまらなくないパターンが書けるようなパッケージを探そうと提案しました。コードが本の1ページに納まるようなら理想的だと思いました。
ロブは自分の部屋に入って行きました。今思い返してみると、1〜2時間も経たないうちだったと思います。
彼は30行のCのコードを携えて部屋から出て来ました。そのコードが、『プログラミング作法』の第9章に掲載されているものです。(略)
Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。
また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?
コメント