2009年10月30日金曜日

[Goose] プログラム解析技術 - 静的解析

解答されたプログラムをGooseが添削する際には、プログラムコードを分析する静的解析と、プログラムを実際に起動して動作を分析する動的解析の2種類の技術を組み合わせて利用します。今回は、実際にGooseが行っている静的解析技術について紹介します。

プログラム解析の流れ。解答されたプログラムに対して、静的解析と動的解析の2種類の解析を行っている。

静的解析技術はグルージェントがかねてより興味を持って取り組んできた分野で、Javaプログラムの静的解析を行う開発環境Irenkaや、静的解析技術を取り込んだ開発環境のYukara, Pirka'rなどの支援を行っています。

このうち、GooseにはIrenkaの技術が組み込まれており、入力された解答に対して、変数やクラスなどへの参照についての分析や、型情報の分析などの高度な静的解析が行えます。

解答の合成

静的解析では、まず空欄を含むプログラムと、それらの空欄に入力された解答を合成します。このとき、Gooseでは空欄を含むプログラムと、空欄に入力されたプログラムを別々に解析し、Javaの構文レベルでの合成を行っています。

これは次項の「プログラム構造の解析」を単純化するための措置で、たとえば次のようなJavaのブロック構造を無視した解答を検出することができます。

ブロック構造を無視した解答の例。クラスブロックの中にメソッドを書いてほしかったが、クラスブロックを強制的に閉じて、新しいクラスの宣言を開始している。

例では空欄に「クラスの内容」を記述することを期待していますが、解答にはクラスの終端と、新しいクラスの開始が記載されています。これは、テキスト全体としての構文は正しいものの、空欄の中だけで見ると不正な構文です。

このような解答は題意から外れていることが多く、また個別の解析を複雑にする要因となります。Gooseでは個々の空欄を個別に分析するため、このような解答を検出して不正解とすることもできます。

空欄に入力されたプログラム構造の解析

解答の合成が終わったら、静的解析の機能を持つIrenkaを利用してプログラム全体の意味を解析します。このとき、プログラムが外部ライブラリを利用する場合には併せて解析を行い、プログラム中に出現する型の情報や、変数などの宣言と参照に関する情報など、コンパイルに必要なあらゆる情報を生成します。

Gooseでは、ここで生成された情報をIrenkaから取得して、それぞれの空欄に入力されたプログラムの構造を検証します。この情報はツリー状のモデルで表現されており、Javaのプログラムから自由に参照できるようになっています。このため、個々の問題に合わせた静的解析のルールを自由に追加し、複雑な静的解析を行えます。

Irenkaの処理の流れ。ソースプログラムと静的解析のルールをIrenkaに渡すと、様々な情報を解析して取得できる。

たとえば、「このAPIを利用せずに解答せよ」という問題や、「このAPIを使って解答せよ」などの出題も容易に行えますし、より複雑には「プロジェクトのコーディング規約に従って解答せよ」などの出題も可能です。

0 件のコメント:

コメントを投稿