Delimiterは語る
Program
Description
これは、あらかじめ学習したモデルを使用して、入力されたプログラミング言語を推定するプログラムである。
原理
プログラミング言語は構文解析を行うにあたって、しばしば字句解析によって構文解析の際に意味をもつ最小単位（token）に分解される。定義によって、tokenの実態はその言語の構文に大きく左右されるものの、例えば以下のようなものに分類できる。
identifier
- if
- while
- let
literal
- "foo"
- 'bar'
- 10
- 3.14
operator
- =
- +
- -
delimiter
- ,
- (
- )
- {
- }
ここで、経験則により次のことを仮定する。
identifierやliteralは主に英数字からなり言語に依らない。
operatorやdelimiterは主に記号からなり言語によって特徴がある。
あなたのお気に入りのプログラミング言語を思い浮かべてほしい。なでしこ等のような一部の例外を除いて概ね該当するに違いない。記号の使われ方こそが、プログラミング言語の構文上の特徴に大きく影響を与えているのである。
ここまでの議論を用いれば以下の手順で、プログラミング言語の推定ができることになる。
- あらかじめ、推定候補となる各言語\( lang \)に対して記号列の確率分布 \( q_{ lang } \) を求めておく。
- 入力されたデータに対して記号列の確率分布 \( p \) を求める。
- 交差エントロピー \( H(p, q_{ lang }) = - \sum p ( x ) \log q_{ lang } ( x ) \) が最小であるような言語\( lang \)がもっともらしい言語である。
ここで、交差エントロピーとは二つの確率分布の類似度として使用できる尺度である。
方法
以下のOpen-source softwareの一部を学習データとして使用した。
それぞれの学習データに対して、あらかじめ作成したtokenizerで記号列とその出現回数のjsonを生成した。
$ paren tokenize ../dataset/xxx > xxx-token-count.json
$ paren tokenize ../dataset/yyy > yyy-token-count.json
...
以下に各言語の上位20個の記号列を示す。いわゆるC-styleな言語を比べても言語ごとの特徴がしっかりと抽出できている。
Note
以前、ParenのSyntax highlightを作成した際に、Parenのコードを自動で検出してSyntax highlightを適用できないものかと思っていた。
ある入力がParenかどうかを判定させるだけならば、Paul Grahamがスパムメール対策でやったようにベイジアンフィルタで試行錯誤したものだが、あまりうまくいかなかった。そもそもベイズ統計が私にはあまり向いていないようだった。
それからしばらくして、たまたま見たAutomatic Caesar cipher breakerから着想を得て実装してみたところ思いのほかうまく動作した。Automatic Caesar cipher breakerでは、あらかじめわかっている文字の頻出度と、すべてのCaesar cipherの取りうる平分ごとの文字の頻出度との交差エントロピーを計算し、最も確からしい平文を推定するというものである。単一換字式暗号が十分な強度を持たないことが簡単に確認できる素晴らしいプログラムである。
Source Code
Token
Tokenizer
Classifier