grepの話

正規表現によるパターンマッチングは、UNIX/Plan9プログラミング環境に浸透している。正規表現ツールとしてもっとも有名なのはgrepだが、UNIXにはegrep、fgrep、zgrepなどの派生コマンドがある。*1一方、Plan9に存在するのは、grep(1)だけで、拡張正規表現、UTF-8をサポートしている。古典的な拡張正規表現しかサポートしていないので、Perl互換正規表現(PCRE)にあるような、\d\D\s\S\w\Wなどはサポートしてない。実装したのはKen Thompsonだが、彼は今まで何回grepを書いているんでしょうねぇ。

正規表現エンジンの実装は、DFA(決定性有限オートマトン)とNFA(非決定性有限オートマトン)を用いた方法に分けることができる。egrepやPlan9のgrepはDFAベースである。GNU grepは、前方参照がない場合はDFA、ある場合はNFAと使い分けをするようだ。

grep、正規表現の実装に興味があれば、次のページがポインタになるでしょう。

「プログラミング作法」を読み返してみるかなぁ。100行もないgrepのサブセットの実装例が説明されている。

プログラミング作法

プログラミング作法

(追記：2008-02-09) O'ReillyのBeautiful codeが翻訳されるらしい。

*1:zgrepなんてあるんですねぇ。GNU grepの拡張については、以前「ソフトウェアの単純さ：本音と建前」でもちょっと触れた。ちなみに、grepは基本正規表現を、egrepは拡張正規表現をサポートしており、GNU grepでは、grepとegrep -G、grep -Eとegrepは等価である。