redditから 正規表現： その理論、実装と歴史

「recursive backtracking」による実装のPerlをはじめとする近代言語の正規表現と古典的Unixのfinite automataによる実装の比較をする記事。正規表現に興味がある方にはお勧め。

http://swtch.com/~rsc/regexp/regexp1.html?

以下、ザっと目を通したインプレッション。時間のあるときに一日かけてジックリ読んでみたい文献だ。

Perlをはじめとするスクリプト言語系とgrep,awkなど伝統的Unixのregexの実装には決定的な違いがある。前者はbacktrackingを使い、後者はUnix創始者のKen Thompson氏が1960年代に発明したNFAベースのもの。実は「a?」や単独のキャラクタ「a」が繰り返されるような「特殊」な正規表現だと、Thompson NFA実装の方が桁違いに速い。

Ahoの本などで正規表現とかFinite Automataとか読んでみたが、NFA(non-deterministic finite automata)や正規表現とFinite Automataの関係をこの記事が一番わかりやす説明してくれる。

Perlが導入したがそのマニュアルがちゃんと定義してくれない「assertions」などもビシっと説明してくれる。何年間もモヤモヤしていたものがフッ飛んだ気がする。

さらに正規表現の歴史を50年代の理論から、60年代のThompson氏による実装、70-80年代のUnixにおける成長、90年代のPlan9における発展、そしてPerlを経て他の言語に広まるまでの経過を追って説明してくれる。非常に興味深い話だ。

こんなに知識があって歴史に精通している学者は髭もじゃらの仙人のような方かと思いきや、なんと、サッパリした好青年ではないか! どうやら、Plan9の研究者のようだ。

久し振りに読みごたえのある記事に出会えた。progitは最近、質が落ちたが今日は良しとしよう。