ファイル解析して遊ぶ - Scala で TAPLを勉強しつつ LLVM コンパイラを作る日記

とつぜん、pxtoneコラージュのデータを解析し始めてしまった。
たまに、謎のデータの解析をやりたくなってしまう。

なんで、人間は解析できるのか、不思議だ。
前提知識がいろいろあるからだけど。

プロジェクトを２倍の長さにするってことがとりあえずできた。
でもまぁ、非公開ってことだから、D言語の仕様といっしょでいろいろ変わるんだろうなと。
そんなことは結構どうでも良くて、良くないんだけど。
バイナリエディタでファイルを開くと、右横にこんなのが見れる。

PTCOLLAGE-060930
5...evenMAST....
................
ﾀ.....textNAME..
..no namematePVT
 >...........2..
.PTVOICE-ﾏ.2."..
......Z@@.......
..ﾈ....0ﾇﾐd.....

ぱっと見て、これはもう、

PTCOLLAGE-060930

これはヘッダだろうし。

evenMAST,textNAME,matePVT

あたりはシグネチャで、

PTVOICE

あたりは、きっと埋め込みデータのことだろうなぁと、予想がつく。
これが凄いことなんだろうなぁと思う。
最初はわけがわからなかったけど、結局見方を知ってると案外分かるものだ。
blogのテキストマイニングのやり方とかは、タグ内の日付等から予想していくらしいけど
これはシグネチャから予想していく。

うーと、つまり、ちょっと複雑なテキストマイニング的なプログラムを作れば
自動解析できたってよさそうって話。
できたわけじゃないけど、いずれ、出来るようになるでしょう。
もう、出来てるかもしれないし。

プログラムは最初、バイナリエディタを立ち上げたときと同じように情報を得る。
つまり、読める文字列を探せってことだ。
対外の場合は文字列はシグネチャと呼ばれる４文字の文字で区切られる。
しかし、それは場合によって異なる。ここがあいまいなところ。
また、データの中にはいくつかのサイズが１，２，４バイトで格納されている。
順番は異なる可能性がある。
ファイルはヘッダ部分とそれ以外を持つ。
さらなる構造を持つ場合もある。

とかいうような結構あいまいな情報を入れといて解析するプログラムをprologあたりではかけるんだろうか。
ってのと、そういう、あいまいな情報を元にあいまいにunifyしてって、あいまいな結論から
成功とエラーが出てきて、その成功の確率が限りなく高ければ満足なわけだよなぁと。

その辺モンテカルロ的にアレしてコレして、解析できるようになったとする。
で、これはバイナリファイルにしか適用できないけど、ここで、出来たプログラムがやっている
ノウハウとテストケースとあいまいunifyとかを自動生成したりなんか、するための最小セットというか、
将棋でいうところの、序盤戦の定石さえ分かってしまえば、結構、いろいろとうまーなんじゃなかろうかと。

そういうのがETが目指すところなんだろうなぁとか思うのだった。

うーむ。これはすなわち、エラーの回復とか、そういうのを自動でやってこう的な発想。
謎のプログラム言語を使って、コンピュータと会話してると、プログラムが出来上がるみたいな話になるのかも。

我々プログラマは結局コンパイラとプログラミング言語で会話しながら、
プログラムを作ってるというような発想でアレだ。

あんまり、うまく教える方法ばっかり考えると、コンピュータは自分で考えないから、
じっくり悩んでもらいましょうよ。ってなかんじ。

悩むってのはどうしようもなく大量な場合わけがあって、
いくら計算しても良さそうな答えが得られない状態なような気がする。

ああ、やっぱり、どうしても必要な基礎知識ってのはあるんだなぁ。
それが、正規化だか形式化されたうんぬんてやつだな。

例えば、c言語文字列。0終端。これは、もう、そう決めたからそうなんであって、そうなんだよ。
というしかないってのが１つの答えだけど。たくさんの例があれば、理解できるようになるはず。
data(cstring,
in ["ab\0","cd\0","ddeeff\0","\0","ffffda\0","fdada\0","fafda\0","fdafda\0"],
out["ab","cd","ddeeff","","ffffda","fdada","fafda","fdafda"],reg[?])
こんなんで、c言語文字列のパーサを予想させる。結局、構造を理解する＝パーサを作る。
ってことでもあるだろうけど。これってのは、/^[^\0]*\0/ということを理解できればＯＫと。
理解ってことは、この正規表現を作れるということだわな。
というか、c言語の文字列は [^\0]*\0なんだな。
この例だけだと、[a-f]*\0と理解されてもしかたない。範囲があるわけだ。
最大だと、.*\0かもしれん。てことは、例えば、次のような質問がコンピュータからされるといいな。
"\0\0"は何だ？とか。""とか、["",""]とかと答える。
つまり、

data(cstring,
  in ["ab\0","cd\0","ddeeff\0","\0","ffffda\0","fdada\0","fafda\0","fdafda\0"],
  out["ab","cd","ddeeff","","ffffda","fdada","fafda","fdafda"],
  reg[ /[a-f]*\0/ | /.*\0/ | ... ? ])

what is this? "\0\0"

コンピュータはこんな感じに理解する。
で、

>add(cstring, in["\0\0"], out[error])

とかすると、

data(cstring,
  in ["ab\0","cd\0","ddeeff\0","\0","ffffda\0","fdada\0","fafda\0","fdafda\0","\0\0"],
  out["ab","cd","ddeeff","","ffffda","fdada","fafda","fdafda", error],
  reg[ /[^\0]*\0/ & /[([^\0]|[a-f])*\0/ | ... ? ])
)
what is this? "ghijklmnopqrstuvwxyz\0"

とかで、

>add(cstring, in["ghijklmnopqrstuvwxyz\0"], out["ghijklmnopqrstuvwxyz"])

とか入力すると。

data(cstring,
  in ["ab\0","cd\0","ddeeff\0","\0","ffffda\0","fdada\0","fafda\0","fdafda\0","\0\0","ghijklmnopqrstuvwxyz\0"],
  out["ab","cd","ddeeff","","ffffda","fdada","fafda","fdafda", error,"ghijklmnopqrstuvwxyz"],
  reg[ /[^\0]*\0/ | /([^\0]|[a-z])*\0/ | ... ? ])
)
what is this? "ABCDEFGHIJKLMNOPQRSTUVWXYZ\0"

なかんじ。最大と最小＋アルファして範囲を狭めてくと。
この場合はこうやって、覚えられるはずだと。
正規表現を会話の中から作るくらいなら、出来そうだと思うんだけど。
こんな感じのものはないのかなぁ。
テストケース自動生成と、正規表現自動生成を会話から作成するっての。

そして、次に問題なのが文脈自由文法次に問題なのが、文脈依存文法ってなってくんだと思ふ。