日本ソフトウェア科学会第 35 回大会 (2018 年度) 講演論文集

Skip-Gram モデルを用いたプログラミング言語の文法推定に向けて
松永 智將

山崎 徹郎

Daniel Perez

千葉 滋

Skip-gram モデルを用いて獲得したベクトル表現を基に，既存のソースコード群からプログラミング言語の文法を推定する手法について述べる．近年では，オープンソースソフトウェアが増えたことで学習データとして大量のプログラミング言語のソースコードを活用できるようになった．これらのソースコード群から文法を獲得できれば，コーディングスタイル検査器等の応用先が考えられる．本研究では，自然言語処理の分野でよく用いられる Skip-gram モ
デルと，CYK 法に基づく生成規則の集合の更新手法によってプログラミング言語の文法を推定する方法を検討する．
We describe a method for inferring the grammar of programming languages using the Skip-gram model.
Recently, we became able to use a lot of source codes as training data because the number of open-source
softwares has increased. If we can generate the grammar from these codes, we can apply it to analysis tools
such as coding style checker. In this paper, we consider a method for inferring grammar using the Skip-grammodel and the CYK parsing algorithm.

1 はじめにEq→“=”

プログラミング言語の文法を既存のソースコードから獲得することは可能だろうか．近年では，GitHub†1

Lp→“(”Rp→“)”

等に公開されるオープンソースソフトウェアが増えた

Op→

“+”

ことで，学習データとして大量のソースコードが活V ar→[“a” − “z”] +用できるようになった．これらのソースコード群からExpr→V ar

文法を推定することができれば，コーディングスタイ|V ar Op Exprル検査器などの静的解析ツールへの応用が見込める．

|Lp Expr Rp→V arEqExpr

本研究では既存のソースコード群を用いて，プログラミング言語の文法を獲得するための汎用的な手法にStmt
図1

EBNF で記述された文法例ついて検討する．
び，左辺の非終端記号は右辺の記号列に置き換えるこ

2 プログラミング言語の文法推定とができる．生成規則の右辺は，非終端記号または終形式文法は，BNF や EBNF を用いて図 1 のよう端記号からなる記号列である．ここで終端記号とは，に「生成規則の集合」で表現することができる． 生

生成規則による置換をそれ以上行うことができない成規則の左辺に表れるような記号を非終端記号と呼文字を指す．開始記号と呼ばれる特定の非終端記号かGrammar Induction for Programming Languages using Skip-Gram model
Tomomasa Matsunaga, 東京大学大学院情報理工学系研究科創造情報学専攻, Graduate School Informationand Science Technology, The University of Tokyo.
†1 https://github.com

ら始めて，生成規則による置換を繰り返すことによって生成できる文字列の集合を言語と呼ぶ．
自然言語処理の分野では，自然言語の文法推定の研究が多く行われている．自然言語の文法はプログラミ
ング言語の文法と比べて，非終端記号の数がわずかで

図3

図2

本システムの概略図

文字列からトークンとトークンの型情報への変換

セットは特定のプログラミング言語で記述された複数のファイルから成り，前処理はデータセット内の全ある等の違いがある．
ある言語のソースコード群から非終端記号と生成規則に対応する構造を獲得することができれば，その言語の文法を推定することができたと見なせる．プロ
グラミング言語の場合は，言語設計者が定めた規則にてのファイルに対して行われる．3. 1. 1 節から 3. 1. 6
節で述べる処理を順に行うことで，「生成規則の集合」の初期値を決定する．

3. 1. 1 字句解析器を用いた文字列からトークン列への変換

従う文字列を使用者が記述するため，通常はトップダはじめに，データセット内の各ファイルに記述されウンに文法が決定される．ソースコードから文法を得た文字列を字句解析器を用いてトークン列に分割するために，ボトムアップに文法を解釈すると，文法とる．ここで使用する字句解析器は，学習の対象とするは交換可能な記号と連続して出現しやすい規則の集

プログラミング言語の字句解析器をそのまま用いる．

まりであると考えられる．交換可能な記号列の集合は

図 3 のように，「字句解析時に何であると認識された文法における非終端記号に対応し，それらの連続出現か」を示す型情報が各トークンに対して得られる (以度合いによって生成規則の右辺の並びが決定できる．

降，トークンの型と呼ぶこととする)．ここでは，図3 Skip-gram モデルを用いた文法の推定法のトークンとして分割される．トークンの型がスペー

本論文で提案する手法では，はじめに「生成規則のス，改行またはコメントのいずれかであると認識され3 の a, b のように，型が同じトークンであっても別々集合」の初期値を決定し，その「生成規則の集合」を更新していくことで最終的な文法を獲得する．本シスたトークンは，この段階で取り除く．

3. 1. 2 出現ファイル数に基づくトークンの置換

テム全体の概略図を図 2 に示す．図 2 のように，本次に，データセット内に出現する各トークンの出現

手法は初期の「生成規則の集合」を作成するまでの前ファイル数を数え上げる．出現ファイル数を数え上げ

処理 (3. 1 節) と，その時点の「生成規則の集合」をる対象はトークンの型ではなくトークン自身である．

用いて構文解析を行うことで「生成規則の集合」を更

出現回数がデータセットに用いたファイル数の 5%に新する処理 (3. 2 節) の二段階に分かれる．
「生成規則満たないトークンを，トークンの型で置き換える．図の集合」を更新する回数はパラメータとして指定し，4 の a, b, c, d のような変数名は，大半のファイルには指定回更新された「生成規則の集合」を最終的な文法同じ名前で現れないので，トークン自身をトークンとする．の型と同じ V ar に置換する．この処理は，「一般的に用いられていない出現度の低いトークン」を「同一の3. 1 「生成規則の集合」の初期値を決定するための前処理トークンの型を持つ場合には同一のトークンとして扱う」ことを目的として行っている．そのため，同じ

本節では，データセットから「生成規則の集合」のトークン名が一つのファイル内で多く用いられる場合初期値を決定するための処理について述べる．データにそのトークンを残してしまうのは目的に沿わない図4

トークンの出現ファイル数に基づくトークンの置き換え処理

図6

Skip-gram モデルによる左側の文脈のみを考慮した「トークンの三つ組」のベクトル表現の獲得

クトル表現の獲得

Neural network のモデルの一つである Skip-gram
モデル [2] を用いて各「トークンの三つ組」に対してベクトル表現を与える．
通常の Skip-gram モデルでは，注目している単語
図5

各トークンの三つ組への変換に対してその左右に出現する単語をラベルとするよ
うな教師あり学習を行う．この学習によって得られるので，総出現回数ではなく出現ファイル数によって置

neural netowork の重みベクトルを，単語に対するベき換えを行なっている．ここで，置き換えの有無に関クトル表現として扱う．本手法では，各「トークンわらずトークンの型はトークンと別に保持を続ける．の三つ組」に対して二種類のベクトル表現を与える．

3. 1. 3 トークンから「トークンの三つ組」への一種類目のベクトル表現を得るために，注目してい変換
前節で置換したトークン列の各トークンを，以下の三点を合わせた三つ組に変換する (図 5)．

る「トークンの三つ組」に対して，その左隣に出現する「トークンの三つ組」をラベルとして与えて学習を行う (図 6)．これにより，左側の文脈のみを考慮した(i) 注目しているトークンの左隣のトークンの型「トークンの三つ組」のベクトル表現が得られる．二(ii) 注目しているトークン種類目のベクトル表現は，考慮する文脈の向きを反対(iii) 注目しているトークンの右隣のトークンの型にして，各「トークンの三つ組」に対してその右隣に以降，「トークンと左右のトークンの型による三つ組」

出現する「トークンの三つ組」をラベルとした学習をを単に「トークンの三つ組」を呼ぶこととする．ファ行う．

イル内で最初に現れるトークンの左隣にはトークンがないので，字句解析器によって与えられる型とは別

3. 1. 5 「トークンの三つ組」のベクトルの距離によるクラスタリングに N one というトークンの型を導入して三つ組へ変ここまでの処理によって，各トークンの三つ組に対換することとする．同様に，ファイル内で最後のトーして「左側の文脈のみを考慮したベクトル表現」とクンも右隣のトークンの型として N one を指定する「右側の文脈のみを考慮したベクトル表現」が与えらことで三つ組に変換する．以降の処理は，ここで置きれている (図 7)．図 8 のように，「左側の文脈のみを換えた「トークンの三つ組」の列に対して行う．

考慮したベクトル表現」の距離でトークンの三つ組

3. 1. 4 「トークンの三つ組」に対する二種類のベをクラスタリングし，同様に「右側の文脈のみを考慮したベクトル表現」の距離でトークンの三つ組をク

図9A→α(1)A→BC(2)

チョムスキー標準形の表記法に対応する生成規則で「生成規則の集合」を表現す
る．本手法における終端記号は「トークンの三つ組」
なので，式 1 の右辺は「トークン列の三つ組」になる．式 1 のような生成規則の左辺に現れる非終端記
図7

トークンの三つ組に対応する 2 種類のベクトル表現

号を，本手法では 3. 1. 5 節で得た二種類のクラスタの名前の組み合わせてによって表す．式 3 に本手法で初期値として与える生成規則の例を示す⟨Ctl Ctr ⟩→t(3)

ここで，t は「トークンの三つ組」を表し，Ctl は，「トークンの三つ組」を「左側の文脈のみを考慮したベクトル表現」の距離でクラスタリングをした結果，t が属しているクラスタを表す (以降，t が属する左側クラスタと呼ぶこととする)．同様に，Ctr は「トークンの三つ組」を「右側の文脈のみを考慮したベクトル表現」の距離でクラスタリングをした結果，t が属し「トークンの三つ組」を「左側の文脈のみを考慮しているクラスタを表す (以降，t が属する右側クラスたベクトル表現」の距離と「右側の文脈のみを考慮したベタと呼ぶこととする)．データセットに現れる全てのクトル表現」の距離で別々にクラスタリング「トークンの三つ組」に対して式 3 のような生成規則

図8を生成し，これらを「生成規則の集合」の初期値としラスタリングする．ここで，クラスタリング手法にて扱う．

は X-means 法 [3] を用いた．X-means 法とは，初期クラスタ数を決めて k-means 法を適用することで得られるクラスタを 2 分割する，という処理を再帰的に行うアルゴリズムである．

3. 2 文法の更新最終的な文法を獲得するために，3. 1 節の前処理によって得られた初期値から始めて，「生成規則の集合」

3. 1. 6 「生成規則の集合」の初期値の決定の更新を指定回数行う．
「生成規則の集合」の更新の本手法では推定する文法として文脈自由文法を仮ために必要となる主な処理は，現在の生成規則で構文定し，チョムスキー標準形で表されるような「生成規解析を行うことで「連続する二つの非終端記号」の出則の集合」を獲得する．チョムスキー標準形では文脈現回数を数え上げることである．

自由文法は図 9 のような規則のみで表現される．こ「生成規則の集合」の更新時に行う構文解析には

こで，A, B, C は非終端記号であり，α は終端記号でCYK 法 [1] を用いた．CYK 法は，入力文字列内の全ある．全ての文脈自由文法はチョムスキー標準形で書ての隣り合う部分列の組み合わせに対して，生成規則き表すことができることが知られている．

を適用可能か考慮することで構文解析を行う手法で「トークンの三つ組」に与えられた二つのクラスタある．ここで，生成規則が適用可能な場合に，生成規を基に「生成規則の集合」の初期値を決定する．本手則の右辺を左辺の非終端記号で置き換えることを「還法では，チョムスキー標準形の生成規則 (図 9 の式 1)元する」という．CYK 法では，チョムスキー標準形

図 11
図 10「トークンの三つ組」の列の還元

非終端記号の組の数え上げ

3. 2. 2 「生成規則の集合」の更新で記述された文脈自由文法を動的計画法に基づいて構文解析することができる．

「生成規則の集合」の更新時には，「トークンの三つ組」の列を生成規則で還元することで，図 11 の A

3. 2. 1 初期状態の「生成規則の集合」の更新過程〜E のような非終端記号が得られる．ある非終端記「生成規則の集合」の更新過程を説明するために，号を得るまでに還元された「トークンの三つ組」の列初回の「生成規則の集合」の更新方法を述べる．初期を，「その非終端記号が表す区間」と呼ぶこととする．

状態では，出現し得る「トークンの三つ組」全てにまた，以下の二点を満たす非終端記号 X と非終端記ついて式 3 のような生成規則が定義されているため，

号 Y の組を「隣り合う非終端記号の組」とする．

各「トークンの三つ組」は一つの非終端記号に変換で(i) X と Y が表す区間が重ならない

きる (図 10)．この非終端記号の列に対して，「隣り合(ii) 「X が表す区間の最右端のトークンの三つ組」

う非終端記号の組」の出現回数を数え上げる．と「Y が表す区間の最左端のトークンの三つ組」「隣り合う非終端記号の組」の出現回数が数えられが「トークンの三つ組の列」において隣接するたら，出現回数の平均値を計算する．こうして得た出図 11 の「A と B 」や「A と E 」は「隣り合う非終端現回数の平均値よりも多く出現する「隣り合う非終端記号の組」であり，「A と C 」や「B と E 」，「D と E 」

記号の組」全てに対して，以下の式 4 のような新しは「隣り合う非終端記号の組」ではない．

い生成規則を作る．

⟨Ctli Ctri+1 ⟩→「生成規則の集合」の更新処理は，二回目以降も初⟨Ctli Ctri ⟩⟨Ctli+1 Ctri+1 ⟩ (4)ここで，「トークンの三つ組」の列の i 番目の「トークンの三つ組」を ti とし，ti が属する左側クラスタをCtli とする．また，ti が属する右側クラスタを Ctri とする．式 3 と同様に，右辺の非終端記号は「トークンの三つ組」が属する左側クラスタと右側クラスタの組み合わせで表される．また，式 4 では左辺の非終端記号が以下の二つの組み合わせで表現される．

(i) 左側の「トークンの三つ組」が属する左側クラスタ(ii) 右側の「トークンの三つ組」が属する右側クラスタ
新しく作られた式 4 のような「生成規則の集合」が，初期状態を更新した後の「生成規則の集合」となる．

回と同様に以下の手順が繰り返し行われる．

1. データセットの全ファイルに対して構文解析を行う．

(a) 3. 1. 3 節で得られた三つ組みの列を CYK法で構文解析する．

(b) 構文解析の過程で登場する「隣り合う非終端記号の組」の出現回数を全て数え上げる．

2. 「隣り合う非終端記号の組」の出現回数の平均値を計算する．

3. 手順 2 で計算した平均値より多く登場する「隣り合う非終端記号の組」全てに対して，右辺がそのような組み合わせとなる生成規則を生成する(後述)．
4. 手順 3 で得られた「生成規則の集合」を更新後トークンの型の情報も付与される．の「生成規則の集合」とする．

5. 更新回数が指定回数に満たなければ，手順 1 へ

2. 3. 1. 2 節と同様にトークンの置換処理を行う．
ここでは，「データセット内に一度も現れなかっ戻る．
通常の CYK 法とは異なり，本手法では考慮する文字たトークン」または「データセット内で出現ファ列の長さに上限を決めて構文解析を打ち切って学習をイル数が 5%に満たなかったトークン」をトーク行なっている．

ンの型で置き換える．

上記の処理の手順 3 では，次のようにして新しい生成規則を作る．トークンの三つ組」の列の i 番目の3. 3. 1. 3 節と同じ方法で，トークン列を「トークンの三つ組」の列に変換する．

「トークンの三つ組」を ti とし，ti が属する左側クラ

上記の処理によって入力文字列から得られる「トークスタを Ctli ，ti が属する右側クラスタを Ctri とする．

ンの三つ組」の列を，獲得した文法を基に CYK 法でj, k についても i と同様に定義する．ここで，隣り合構文解析する．

う非終端記号の組を ⟨Ctli Ctrk ⟩ と ⟨Ctlk+1 Ctrj ⟩ とする

4 「生成規則の集合」の獲得と構文解析結果と，作られる生成規則は⟨Ctli Ctrj ⟩→⟨Ctli Ctrk ⟩⟨Ctlk+1 Ctrj ⟩(5)

本手法を用いて，実際に文法の学習を行なった．今である．それぞれの非終端記号は「トークンの三つ回は Ruby 言語を対象としてプログラミング言語の組」の列を還元して得られるものである．本手法の生文法の獲得を試みた．本章では，学習時に用いた各種成規則の作り方では，非終端記号 ⟨Ctli Ctrk ⟩ は，還元パラメータ値と，獲得した「生成規則の集合」で構文前の「トークンの三つ組」の列の最左端 ti が属する左解析をした結果の例を示す．

側クラスタと最右端 tk が属する右側クラスタからなる．したがって，新しく作られる生成規則の左辺の非4. 1 Ruby 言語を対象とした文法の獲得

終端記号も，以下の二つの組み合わせで表現される．

学習データを集めるために，Ruby 言語のオープン(i) 左辺の非終端記号が表す区間で一番左の「トーソースソフトウェアとして GitHub 上に公開されてクンの三つ組」が属する左側クラスタ(ii) 左辺の非終端記号が表す区間で一番右の「トークンの三つ組」が属する右側クラスタ

いるリポジトリから，スター数の多い順に 100 リポ
ジトリ取得した．これらのリポジトリから，Ruby 言語で記述されたファイルのみを抜き出して学習データこうしてより長い「トークンの三つ組」の列を還元しとして使用した．実際に学習に用いられた Ruby 言て得られる非終端記号を作っていく．

語のファイル数は 44,742 である．

3. 1. 1 〜 3. 1. 3 節で述べた手順によって，上記の3. 3 獲得した文法による構文解析

データセットの各ファイルの文字列を「トークンの本手法で獲得した文法の終端記号は，通常の字句三つ組」の列に変換した．ここで，字句解析器と解析器によって得られるトークンではなく，そのトーして Ruby 言語の標準ライブラリに含まれているクンに一連の処理を施した「トークンの三つ組」であRipper クラスを用いた．Ripper によって与えられるる．そのため，獲得した文法で実際に入力文字列を構

トークンの型が on sp，on nl，on ignored nl また

文解析する際には，学習時と同様にあらかじめ入力文は on comment のいずれかであるようなトークンは字列を「トークンの三つ組」に変換する必要がある．

スペース，改行，コメントを表すので，字句解析を以下に，新しく与えられる入力文字列を「トークンの行った段階でこれらを取り除いた．出現ファイル数三つ組」の列に変換するための処理を示す．

が全体の 5%に満たないトークンをトークンの型で置き換えたところ，class，require，describe(RSpec†2

1. 3. 1. 1 節で用いた字句解析器と同じ字句解析器を用いて，入力文字列からトークン列への変換処理を行う．学習時と同様に，各トークンに対する†2 Ruby 言 語 の テ ス ト 用 フ レ ー ム ワ ー ク．http://rspec.info

で多く用いられているようである) など，一般的に広class ClassName < SuperClassName

く用いられているトークンは置換されずに残った．こdef self.foo

れらの処理によって得られるデータセット内の「トーa = b + (c + d)

クンの三つ組」は 5,780 種類となった．

end

次に，「トークンの三つ組」に対して「左側の文脈endのみを考慮したベクトル表現」と「右側の文脈のみを考慮したベクトル表現」を与えた．この二種類のベ

図 12獲得した文法での構文解析に成功する Ruby 言語

クトル表現のどちらを学習する場合にも，Skip-gramの文法として正しいソースコード例

モデルのウィンドウサイズは 1 で epoch 数を 100 回として学習を行なった．また，どちらのベクトル表現

class ClassName < SuperClassName

も次元数は 100 次元として埋め込みをした．

def self.foo「左側の文脈のみを考慮したベクトル表現」の距

a = b + (c + d)

離でトークンの三つ組をクラスタリングする際，X-

endmeans 法のクラスタ数の初期値として「トークンの三つ組」の種類数の半数である 2,890 を指定した．その図 13

結果，実際に得られたクラスタ数も 2,890 であった．

獲得した文法での構文解析に失敗する Ruby 言語の文法として正しくないソースコード例「右側の文脈のみを考慮したベクトル表現」の距離でトークンの三つ組をクラスタリングする場合も同様

class ClassName < SuperClassNameに 2,890 を指定して同じクラスタ数に分割された．

self.foo「トークンの三つ組」の種類数が 5,780 であったた

a = b + (c + d)

め，「生成規則の集合」の初期値も 5,780 個の生成規end則が生成された．この「生成規則の集合」の更新時にendは，CYK 法の深さ (非終端記号が表す区間として考慮する最長の長さ) を 10 として学習を行った．更新
回数は上限を 100 回として学習を行なったが，実際に図 14獲得した文法での構文解析に成功する Ruby 言語の文法として正しくないソースコード例

はその時点での「生成規則の集合」で更新を行なった
結果が同じ「生成規則の集合」となった時点で，それに行う必要がある．

以上は更新が行われないので処理を打ち切っている．

5 まとめ
4. 2 獲得した文法による構文解析

既存のソースコード群からプログラミング言語の実際に獲得した文法でいくつかのソースコードを文法を獲得するための手法について検討をした．本

対象に構文解析を行った．現在，獲得した文法を解析手法では，Skip-gram モデルによって獲得したベクトし，本論文で提案した手法の改善を進めている．例えル表現を基にした「生成規則の集合」の初期値の決ば，獲得した文法を用いて図 12 を構文解析すると成定と，CYK 法に基づく「生成規則の集合」の更新に功する．これは，Ruby 言語としても正しい文法であよって最終的な文法を獲得した．本論文で述べた文法る．また，図 13 のソースコードを獲得した文法で構獲得手法の改善を今後続けていく．

文解析すると，end が抜けているので構文解析に失敗する．しかし，図 14 のソースコードは Ruby 言語の参 考 文 献

文法としては正しくないが，今回獲得した文法では構[1] Earley, J.: An Eﬃcient Context-free Parsing Algorithm, Commun. ACM, Vol. 13, No. 2(1970),

文解析に成功してしまう．今後，手法の改善を継続的pp. 94–102.
[2] Mikolov, T., Sutskever, I., Chen, K., Corrado,G., and Dean, J.: Distributed Representations ofWords and Phrases and Their Compositionality,
Proceedings of the 26th International Conference
on Neural Information Processing Systems - Volume 2, NIPS’13, USA, Curran Associates Inc., 2013,

pp. 3111–3119.
[3] Pelleg, D. and Moore, A.: X-means: Extending
K-means with Eﬃcient Estimation of the Numberof Clusters, In Proceedings of the 17th InternationalConf. on Machine Learning, Morgan Kaufmann,2000, pp. 727–734.