正規表現から例を自動生成する

反響

k.inabaさんに煽られたので、OCamlでパーサ書いてたんですが、CGIはめんどさそうなのでRubyでブリッヂさせようかとか考えてたんですが、例の生成の前に飽きました。後方参照とかやっとられん。しばらくは時間を使う気になれないので、なんとなくなんか書いておく。

私なりにまとめると次のようになる。

  1. 正規表現って有限状態オートマトンだよね派
    1. ランダムウォークすればいいじゃない派(k.inabaさん)
    2. BFSしてからランダムに選べばいいじゃない派
  2. 正規表現正規表現であって有限状態オートマトンじゃないよ派
    1. ランダム生成すればいいじゃない派(私)
    2. BFSしてからランダムに選べばいいじゃない派(id:sumii先生さん)

それぞれを分析するとこんな感じかな?

オートマトン 正規表現
カタカナがなんかかっこいい 有限状態オートマトンじゃない正規表現も取り扱える
× 正規表現の意図を反映できない ad-hocな感じがする
BFS ランダムウォーク
長さとか例の数とかの処理がしやすそう 実装が死ぬほど簡単
× - 長さとか(ry

とりあえず、理論的(?)には、ランダムウォークするかBFSするかすれば良いということで決着が着いたような気がします(初めから付いてます)。例えばこういうのの応用と言えば、テストの他に、UIで例を出すのとかに使うことができると思うんですが、その場合は/red|blue|green|#[0-9A-Fa-f]{6}/みたいな正規表現だったら、redとかblueとかgreenとかは絶対出てきて欲しいですけど、そういうのを考慮すると正規表現のままの方がまだ取り扱いは楽だよね、みたいな。



研究室で「オートマトンから正規表現にするのってどうやるんだったっけ?」と言ってみたら、先生に「てんめぇーーー俺の授業でやったやろうがーーーー除籍だ除籍!!!このうすらボケ。学部からやりなおしてこい!」と怒られました。若干誇張が混ってます。

あーあと唐突に思い付いたんですけど、単語が出てきて欲しい場合はスペルチェッカ通すとかすれば良さそうだな、みたいな。