2023-03-01

VM vs. 拡張NFA

やったこと

• ナンを焼いて食べた
• 『ライリー・ノース -復讐の女神-』を観た
• 正規表現の勉強

ナン

きのう無印で買ってきたナンのホットケーキミックス的なやつでナンを作って焼き、食べた。 ポールマッカートニーみたいな名前のカレーと、ほうれん草がなんとかのカレーも食べた。おいしかった。

ナンみたいなやつって中身がほぼ小麦粉かとうもろこし粉なのは分かってるけど、やっぱりミックスとして売られているやつは「これがあればナンを作れます！！！」と言ってくれるお手軽さが非常にいい。調べるの面倒だもん。

ライリー・ノース

映画を観た。 主人公は一般市民で善良なママ。麻薬組織に家族を殺されてしまい、いろいろ鍛えて復讐する話。 主人公が基本的に最強だから、何も考えずに観られるのがよかった。

あと、リチャードカブラルが麻薬組織の一人で出てきた。この人やっぱこういう役似合いすぎだよな。

正規表現

昨日に引き続き Russ Cox の記事を読んでいる。同時に翻訳をしているのもあり時間がかかっていて、翻訳自体の難しさも感じている。技術翻訳をやっているひとがいたら話を聞いてみたい。

以下は正規表現関連で考えたことを書きなぐる。とりあえずメモで、あとからちゃんと考える。

記事で紹介されている実装（Thompsonが提唱したやつ）は一般的にはDFA型と呼ばれるやつなんだろうけど、正規表現への対応の関係で実際に考えているのはNFA、でもNFAの非決定性に起因するパフォーマンス上の問題をカバーするために拡張NFAを考えて実装した結果、DFA的な挙動をするようになる、というほうが近い感じがした。

詳説正規表現でのDFA型の動作の説明は理論的なDFAのシミュレーションとは異なっていて、読んだときは「オートマトンの説明をしてないからそういう説明にもなるかー」くらいに思っていたのだけど、Thompsonのやり方を指しているとしたらあの説明も正しそうだなと思った。

すると、Thompsonのやり方をDFA型と呼ぶかNFA型と呼ぶかはどこに着目するかが問題になってくる。プログラム的にはNFAを考えてるからNFA型かもしれないし、拡張してしまってるからNFAじゃない、マッチの挙動的にはDFAだろと考えればDFA型とも言える。

もしエンジンの挙動に注目するならば、結局はバックトラックするかどうかが問題になるんだろうな。オートマトンとしてどういう形かどうかよりもランタイムで必要になるバックトラックという挙動が問題だから、Perlとかの正規表現エンジンをNFA型ではなくVM型と呼ぶのかなあとも思ったりした。

あとおもしろかったのは詳説正規表現とRuss Coxの態度の違い。 詳説正規表現では（NFA型は遅くなりうるし難しいと触れながらも）DFA型は退屈だと評しているのに対し、 Russ CoxはいわゆるVM型の正規表現エンジンについて、理論を無視することでいかに悪いプログラムつながるかを示す輝かしい例だ、と評している。こういうの面白いね。 俺はどちらかというと Russ Cox寄りかなあ。